Journal of Frontiers of Computer Science and Technology ›› 2014, Vol. 8 ›› Issue (4): 483-493.DOI: 10.3778/j.issn.1673-9418.1310041

Previous Articles     Next Articles

Parallel Reasoning Algorithm of Complex Causality Diagram

LIANG Xinyuan1,2+   

  1. 1. School of Computer Science and Information Engineering, Chongqing Technology and Business University, Chongqing 400067, China
    2. Chongqing Key Laboratory of Electronic Commerce and Supply Chain System, Chongqing 400067, China
  • Online:2014-04-01 Published:2014-04-03

复杂因果图并行推理算法研究

梁新元1,2+   

  1. 1. 重庆工商大学 计算机科学与信息工程学院,重庆 400067
    2. 电子商务及供应链系统重庆市重点实验室,重庆 400067

Abstract: As the accurate reasoning algorithm of causality diagram (CD) is NP hard, it’s worth to propose an efficient reasoning method. This paper firstly introduces the research development of causal relationship, and makes a further analysis on the reasoning process of classical causality diagram. Furthermore, this paper proposes a parallel reasoning algorithm of complex causality diagram to improve reasoning efficiency and analyzes its time complexity. Finally, this paper uses an example to show the reasoning efficiency of this algorithm. The research shows that the parallel reasoning algorithm of complex causality diagram proposed in this paper can effectively reduce the time complexity. Especially in the case of adequate processors with loop and limited processors without loop, the algorithm complexity is a polynomial time complexity, which provides a new feasible reasoning method for causality diagram.

Key words: complex, causality diagram, parallel, reasoning, computation time complexity

摘要: 因果图的精确推理算法是NP难的,因此寻找高效的推理方法是值得研究的问题。介绍了因果关系研究进展,对经典因果图推理过程作了进一步分析,在此基础上提出了复杂因果图的并行推理算法,并对算法的时间复杂度进行了分析,最后用一个实例验证了算法的推理效果。研究表明,该复杂因果图并行推理算法有效地降低了时间复杂度,特别是在有环且处理机数量足够的情况下和无环且处理机有限的情况下,算法的复杂度是一个多项式时间复杂度,这为因果图提供了一种可行的新的推理方法。

关键词: 复杂, 因果图, 并行, 推理, 计算时间复杂度