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

摘要：

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

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

分类号：TP181(自动化基础理论)

资助基金：The National Natural Science Foundation of China under Grant No.60574024;the Natural Science Foundation of Chongqing under Grant No. CSTC2010BB2259;the Science and Technology Project of Chongqing Educa-tion Committee under Grant No. KJ120718

在线出版日期：2014-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：483-493