Computer Engineering and Applications ›› 2015, Vol. 51 ›› Issue (18): 229-232.

Previous Articles     Next Articles

Causality diagram?reasoning by using binary decision diagram improvement

LIANG Fan, WANG Hongchun   

  1. College of Mathematics, Chongqing Normal University, Chongqing 401331, China
  • Online:2015-09-15 Published:2015-10-13


梁  帆,王洪春   

  1. 重庆师范大学 数学学院,重庆 401331

Abstract: As the accurate reasoning algorithm of causality diagram is NP hard, it’s worth proposing an efficient reasoning method. This paper improves the binary decision diagram and proposes a method that transforms causality diagram into binary decision diagram, avoiding the process of disjoint cut sets. It can effectively reduce the reasoning complexity.

Key words: causality diagram, binary decision diagram, cut sets, disjoint cut sets

摘要: 因果图的经典推理算法是NP难的,因此需要寻找高效的推理算法。对二元决策图进行改进,并提出一种因果图向改进的二元决策图转换的方法。利用改进的二元决策图推理省略了割集不交化的过程,得到不交化割集,减小推理复杂度。

关键词: 因果图, 二元决策图, 割集, 不交化割集