摘要
因果图的精确推理算法是NP难的,因此寻找高效的推理方法是值得研究的问题。介绍了因果关系研究进展,对经典因果图推理过程作了进一步分析,在此基础上提出了复杂因果图的并行推理算法,并对算法的时间复杂度进行了分析,最后用一个实例验证了算法的推理效果。研究表明,该复杂因果图并行推理算法有效地降低了时间复杂度,特别是在有环且处理机数量足够的情况下和无环且处理机有限的情况下,算法的复杂度是一个多项式时间复杂度,这为因果图提供了一种可行的新的推理方法。
As the accurate reasoning algorithm of causality diagram (CD) is NP hard, it’s worth to propose an effi-cient 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.
出处
《计算机科学与探索》
CSCD
2014年第4期483-493,共11页
Journal of Frontiers of Computer Science and Technology
基金
国家自然科学基金Grant No.60574024
重庆市自然科学基金Grant No.CSTC2010BB2259
重庆市教委科学技术研究项目Grant No.KJ120718~~
关键词
复杂
因果图
并行
推理
计算时间复杂度
complex
causality diagram
parallel
reasoning
computation time complexity