求解公式关键文字集的信息传播算法-山东大学学报工学版.pdf

　第４１卷　第３期 山　东　大　学　学　报　（工　学　版） ２０１１年６月　 　 　　 Ｖｏｌ．４１　 Ｎｏ．３　　 　ＪＯＵＲＮＡＬＯＦＳＨＡＮＤＯＮＧＵＮＩＶＥＲＳＩＴＹ（ＥＮＧＩＮＥＥＲＩＮＧＳＣＩＥＮＣＥ） Ｊｕｎ．２０１１　 　文章编号：１６７２３９６１（２０１１）０３０００１０６ 求解公式关键文字集的信息传播算法 王晓峰，许道云，秦永彬 （贵州大学计算机科学系，贵州 贵阳５５００２５） 摘要：关键文字集影响判定布尔公式可满足性的判定难度。如果能找到公式的关键文字集或关键文字集的子集， 就可使公式的可满足性判定变得容易。通过对警示传播算法的原理分析，发现高概率决定的部分变元对公式的 求解难度有一定的影响。当某个子句与变元之间的警示信息具有一致性时，表明该子句的可满足性完全由该变 元的取值决定，其它变元的取值都不能使得该子句可满足。进一步研究发现，当该算法收敛时，具有一致性的警 示信息对应的变元集合是关键文字集的子集，这就佐证了警示传播算法可用于求解公式的关键文字集。基于该 算法的特征，给出了一个寻找公式关键文字集的信息传播算法。 关键词：信息传递；警示传播算法；原理分析；关键文字 中图分类号：ＴＰ３０１　　　文献标志码：Ａ Ａｍｅｓｓａｇｅｐｒｏｐａｇａｔｉｏｎａｌｇｏｒｉｔｈｍｃｏｍｐｕｔｉｎｇｓｅｔｏｆｋｅｙｌｉｔｅｒａｌｓｏｆａｆｏｒｍｕｌａ ＷＡＮＧＸｉａｏｆｅｎｇ，ＸＵＤａｏｙｕｎ，ＱＩＮＹｏｎｇｂｉｎ （ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＧｕｉｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｇｕｉｙａｎｇ５５００２５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＴｈｅｄｉｆｆｉｃｕｌｔｙｏｆｓｏｌｖｉｎｇＢｏｏｌｅａｎｆｏｒｍｕｌａｅｉｓｍａｉｎｌｙｄｅｃｉｄｅｄｂｙｔｈｅｋｅｙｌｉｔｅｒａｌｓ．Ｉｆｔｈｅｋｅｙｌｉｔｅｒａｌｓｏｒｓｕｂｓｅｔ ｏｆｆｏｒｍｕｌａｓｃｏｕｌｄｂｅｆｏｕｎｄ，ｔｈｅｙｗｏｕｌｄｂｅｔｒａｃｔａｂｌｅｔｏｓｏｌｖｅｔｈｅｆｏｒｍｕｌａ．Ｔｈｅｐｒｉｎｃｉｐｌｅｏｆｔｈｅｗａｒｎｉｎｇｐｒｏｐａｇａｔｉｏｎｗａｓ ｓｔｕｄｉｅｄ，ａｎｄｉｔｗａｓｆｏｕｎｄｔｈａｔｔｈｅｄｅｃｉｓｉｏｎｐａｒｔｖａｒｉａｂｌｅｓｏｆｈｉｇｈｐｒｏｂａｂｉｌｉｔｙｗｅｒｅｉｍｐｏｒｔａｎｔｆｏｒｓｏｌｖｉｎｇｔｈｅＢｏｏｌｅａｎｆｏｒ ｍｕｌａｅ．Ｉｔｗａｓａｌｓｏｆｏｕｎｄｔｈａｔｉｆｔｈｅｗａｒｎｉｎｇｍｅｓｓａｇｅｈａｄｃｏｎｓｉｓｔｅｎｃｙｂｅｔｗｅｅｎｔｈｅｃｌａｕｓｅａｎｄｖａｒｉａｂｌｅ，ｔｈｅｖａｒｉａｂｌｅｃｏｕｌｄ ｄｅｃｉｄｅｔｈｅｃｌａｕｓｅｓａｔｉｓｆｉａｂｉｌｉｔｙ，ｗｈｉｌｅｏｔｈｅｒｖａｒｉａｂｌｅｓｄｉｄｎｏｔｃｏｎｔｒｉｂｕｔｅｔｏｓａｔｉｓｆｉａｂｉｌｉｔｙｏｆｔｈｅｃｌａｕｓｅ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｉｔｗａｓ ｐｒｏｖｅｄｔｈａｔｔｈｅｐａｒｔｖａｒｉａｂｌｅｓｗｅｒｅｔｈｅｓｕｂｓｅｔｏｆｔｈｅｋｅｙｌｉｔｅｒａｌｓｗｈｅｎｔｈｅｗａｒｎｉｎｇｐｒｏｐａｇａｔｉｏｎｗａｓｃｏｎｖｅｒｇｅｎｔ，ｗｈｉｃｈ ｓｈｏｗｅｄｔｈａｔｔｈｅｗａｒｎｉｎｇｐｒｏｐａｇａｔｉｏｎｃｏｕｌｄｂｅｕｓｅｄｔｏｆｉｎｄｔｈｅｋｅｙｌｉｔｅｒａｌｓｆｏｒｔｈｅｆｏｒｍｕｌａｅ．Ｆｉｎａｌｌｙ，ｔｈｅｍａｓｓａｇｅｐａｓｓ ｉｎｇａｌｇｏｒｉｔｈｍｔｏｆｉｎｄｔｈｅｋｅｙｌｉｔｅｒａｌｓｗａｓｇｉｖｅｎｂｙｔｈｅｗａｒｎｉｎｇｐｒｏｐａｇａｔｉｏｎｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ． Ｋｅｙｗｏｒｄｓ：ｍｅｓｓａｇｅｐａｓｓｉｎｇ；ｗａｒｎｉｎｇｐｒｏｐａｇａｔｉｏｎａｌｇｏｒｉｔｈｍ；ａｎａｌｙｓｉｓｏｆｐｒｉｎｃｉｐｌｅ；ｋｅｙｌｉｔｅｒａｌ 用使回溯计算次数有较大降低。警示传播（ｗａｒｎｉｎｇ ０　引言