Page 139 - 《软件学报》2021年第5期

王晓峰 等:可满足性问题中信念传播算法的收敛性分析 1363

u
()
a Vk
a V u () j

s
a V s () j j k a Vk
()

a

i

Fig.2 Part of factor graph
图 2 局部因子图
1.2 信念传播算法
基于消息传递而设计的信念传播算法,求解可满足性问题时有良好的有效性.文献[30]给出了求解可满足
性问题的 BP 算法,其特征是基于因子图的消息传递过程.具体地讲,在因子图的每条边(a,i)上定义消息δ a→i ∈
[0,1],消息更新方程为
⎛ P u ⎞
=
a
δ a→ ∏ jV a ⎜ P u j→ ⎝ a j→ P j→ s a ⎠ ⎟ ⎟ (1)
()\i ⎜
i
+
∈
其中,
P j→ u a = bV a s () j (1 δ− ∏ b→ j ) (2)
∈
P j→ s a = bV a u () j (1 δ− ∏ b→ j ) (3)
∈
求解 CNF 公式的 BP 算法如算法 1 所示.
算法 1. BP algorithm.
Input: factor graph G, max step t max , precision ε.
*
Output: fix message δ a→ i .
1. t=0, initialize δ a→i (t=0)∈[0,1] for random order;
2. For t=1 to t=t max :
2.1. call BP-UPDATE to generating new message δ a→i (t);
2.2. If |δ a→i (t)−δ a→i (t−1)|<ε, set δ * a→ i = δ a→ i ()t ,
go to Step 3;
3. If t=t max
return UN-CONVERGENCE.
Else if t<t max
return δ a→ * i = δ a→ i ()t ;
算法 2. BP-UPDATE.
Input: variable node j∈V(a)\i.
Output: δ a→i .
1. compute P u j→ a ,P j→ s a ;
u
If V a s ()j =∅, set P j→ a =1;
2. return δ a→i by formula (1);
在信息传播算法中,因子图上的信息δ a→i 定义为:子句结点向变元结点发送的一个概率值,即变元的取值使