电脑知识与技术
電腦知識與技術
전뇌지식여기술
Computer Knowledge and Technology
2015年
5期
209-212
,共4页
信息传播算法%可满足性问题%收敛性%因子图%最大匹配
信息傳播算法%可滿足性問題%收斂性%因子圖%最大匹配
신식전파산법%가만족성문제%수렴성%인자도%최대필배
Message Passing Algorithms%Satisfiability Problem%Convergence%Factor Graph%Maximum Matching
信息传播算法求解可满足性问题时具有良好的有效性，能使难解区域变窄。在信息传播算法的设计中，是将变量的联合概率分布分解为变量子集上的局部函数的乘积形式。称局部函数为因子(factor)，每一个因子依赖于一个变量子集，将变量联合分布的这一因子形式表示为图模型——因子图(factor graph)。信息传播算法是通过因子图上的边传递概率消息，这种消息传递有两种方式：变量结点传递给因子结点的消息和因子结点传递给变量结点的消息。从每个结点传出的消息由传入该结点的消息决定，通过某种迭代策略对消息进行更新。当这种消息迭代过程收敛到某一固定点时，利用某种规则（如，最小熵、最大积、最大匹配）对问题进行求解。本文提出一种利用最大匹配规则求解因子图上的信息传播算法的收敛性及算法迭代步数的上界估计方法，根据对算法的收敛性分析，在对问题解的精确性影响不大的前提下，仅需要给出算法合理的迭代步数或者强迫算法终止，使得算法提前结束，有助于求解可满足性问题算法性能的更进一步优化。
信息傳播算法求解可滿足性問題時具有良好的有效性，能使難解區域變窄。在信息傳播算法的設計中，是將變量的聯閤概率分佈分解為變量子集上的跼部函數的乘積形式。稱跼部函數為因子(factor)，每一箇因子依賴于一箇變量子集，將變量聯閤分佈的這一因子形式錶示為圖模型——因子圖(factor graph)。信息傳播算法是通過因子圖上的邊傳遞概率消息，這種消息傳遞有兩種方式：變量結點傳遞給因子結點的消息和因子結點傳遞給變量結點的消息。從每箇結點傳齣的消息由傳入該結點的消息決定，通過某種迭代策略對消息進行更新。噹這種消息迭代過程收斂到某一固定點時，利用某種規則（如，最小熵、最大積、最大匹配）對問題進行求解。本文提齣一種利用最大匹配規則求解因子圖上的信息傳播算法的收斂性及算法迭代步數的上界估計方法，根據對算法的收斂性分析，在對問題解的精確性影響不大的前提下，僅需要給齣算法閤理的迭代步數或者彊迫算法終止，使得算法提前結束，有助于求解可滿足性問題算法性能的更進一步優化。
신식전파산법구해가만족성문제시구유량호적유효성，능사난해구역변착。재신식전파산법적설계중，시장변량적연합개솔분포분해위변양자집상적국부함수적승적형식。칭국부함수위인자(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 on a variable subset, which is represented as a graph model factor.Message passing algorithms is a kind of message passing through a factor graph, which has two ways:the variable node is passed to the message and the factor node of the node. The message from each node is determined by the decision of the incoming message, and the message is updated by an iterative strategy. When the convergence 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 of the algorithm. Based on the convergence analysis of the algorithm, we only need to give a reasonable number of iteration steps or forced the algorithm to terminate.
