CAJ | 학술논문

因果图的精确推理算法是NP难的，因此寻找高效的推理方法是值得研究的问题。介绍了因果关系研究进展，对经典因果图推理过程作了进一步分析，在此基础上提出了复杂因果图的并行推理算法，并对算法的时间复杂度进行了分析，最后用一个实例验证了算法的推理效果。研究表明，该复杂因果图并行推理算法有效地降低了时间复杂度，特别是在有环且处理机数量足够的情况下和无环且处理机有限的情况下，算法的复杂度是一个多项式时间复杂度，这为因果图提供了一种可行的新的推理方法。
인과도적정학추리산법시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.