一种基于图匹配的求解可满足性问题的算法  

An Algorithm for Solving The Satisfiability Problem Based on Graph Matching

作　　者：于千城[1] 

机构地区：[1]北方民族大学计算机学院,宁夏银川750021

出　　处：《电脑知识与技术（过刊）》2015年第2X期209-212,共4页Computer Knowledge and Technology

摘　　要：信息传播算法求解可满足性问题时具有良好的有效性,能使难解区域变窄。在信息传播算法的设计中,是将变量的联合概率分布分解为变量子集上的局部函数的乘积形式。称局部函数为因子(factor),每一个因子依赖于一个变量子集,将变量联合分布的这一因子形式表示为图模型——因子图(factor graph)。信息传播算法是通过因子图上的边传递概率消息,这种消息传递有两种方式:变量结点传递给因子结点的消息和因子结点传递给变量结点的消息。从每个结点传出的消息由传入该结点的消息决定,通过某种迭代策略对消息进行更新。当这种消息迭代过程收敛到某一固定点时,利用某种规则(如,最小熵、最大积、最大匹配)对问题进行求解。本文提出一种利用最大匹配规则求解因子图上的信息传播算法的收敛性及算法迭代步数的上界估计方法,根据对算法的收敛性分析,在对问题解的精确性影响不大的前提下,仅需要给出算法合理的迭代步数或者强迫算法终止,使得算法提前结束,有助于求解可满足性问题算法性能的更进一步优化。Message passing algorithms are very effective in finding satisfying assignments for SAT instances, and hard region be-come narrower. In the design of the Message passing algorithms, the joint probability distribution of the variables is decomposed in-to the product form of the local function of the variable quantum set. The local function is a factor, and each factor is dependent ona variable subset, which is represented as a graph model factor.Message passing algorithms is a kind of message passing through afactor graph, which has two ways: the variable node is passed to the message and the factor node of the node. The message fromeach node is determined by the decision of the incoming message, and the message is updated by an iterative strategy. When theconvergence of this kind of message is fixed to a fixed point, the problem is solved by using some rules(e.g., minimum entropy,maximum product and maximum matching). In this paper, we propose a method to estimate the convergence and the upper bound ofthe algorithm. Based on the convergence analysis of the algorithm, we only need to give a reasonable number of iteration steps orforced the algorithm to terminate.

关 键 词：信息传播算法 可满足性问题 收敛性 因子图 最大匹配 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]