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

1364 Journal of Software 软件学报 Vol.32, No.5, May 2021

子句不可满足的概率信息.若 BP 算法进行若干次迭代后能够收敛,则可以利用全局信息引导可满足指派的搜索
过程,这种方法被证明是非常有效的 [30] .然而,对于因子图含有回路的 SAT 实例,BP 算法有时候表现为不收敛,
因此无法返回 SAT 实例的可满足性结果.是什么原因导致 BP 算法不收敛,目前还未给出理论解释.因此,仍然有
必要对 BP 算法的收敛性从理论上做更为深入的研究.

2 主要结论及证明
N
设(V,||⋅||)为一个有限维实向量空间,\ 上的A 1 -范数定义为 [44]
1 ∑
|| ||x = N i= 1 | x i | (4)
N
\ 上的A ∞ -范数定义为
||x|| ∞ =max i∈{1,2,…,N} |x i | (5)
向量空间 V 上的范数可诱导一个 V 上的度量 d(v,w)=||v−w||,v,w∈V.显然,度量空间(V,d)是完备的.
设函数 f :V→V,当 0≤K<1,任意 v,w∈V,都有 d(f(v)−f(w))≤Kd(v,w),那么 f 为压缩函数.函数的压缩原理是指:
如果函数 f :V→V 是完备度量空间(V,d)中的压缩函数,对于∀x∈V,f 收敛到唯一点 x ∞ .设(V,||⋅||)是一个赋范空间,
映射 A:V→V 的矩阵范数:
||A||=sup v∈V ||Av|| (6)
N
\ 上的 A 1 -范数定义为
|| A = max j∈ {1,2,..., }∑ N i= 1 | A ij | (7)
||
1
N
N
\ 上的 A ∞ -范数定义为
|| A || = max i∈ {1,2,..., }∑ N j= 1 | A ij | (8)
∞
N
引理 1 [54] . 设(V,||⋅||)是赋范空间,函数 f :V→V 可微,那么对于任意的 x,y∈V,则可以得到
||f (x)−f (y)||≤||x−y||⋅sup z∈V |f ′(z)| (9)
由上述引理以及函数压缩映射可以知道,若 sup z∈V |f ′(z)|<1,则函数 f 能够收敛到 x ∞ .如果函数 f :V→V 是可微
的,那么通过函数 f 的雅可比矩阵 f ′(z)来构造矩阵范数 A.
为了分析方便,假设δ a→i ∈(0,1).更进一步,为了利用实向量空间中的压缩映射原理,我们将(0,1)扩展为(−∞,
1
+∞),利用双曲正切函数进行参数化, (1 tanhλ+ a→ i ) δ= a→ i ,参数λ a→i ∈\.BP 算法的迭代公式(1)被写成如下形式:
2
⎛ P u ⎞
tanhλ a→ i = 2 jV a ⎜ ∏ P j→ ⎝ u a j→ a P j→ s a ⎠ ⎟ ⎟ − 1 (10)
()\i ⎜
∈
+
其中,
1
P j→ u a = bV a s () j 2 (1 tanhλ− ∏ b→ j ) (11)
∈
1
P j→ s a = bV a u () j 2 (1 tanhλ− ∏ b→ j ) (12)
∈
为了书写方便,假设
x = j ∏ bV∈ a s () j 1 (1 tanhλ − b→ j ), y = j ∏ b V∈ a u () j 1 2 (1 tanhλ − b→ j ) .
2
因此,
⎛ x ⎞
tanhλ a→ i = 2 ∏ jV a ⎜ j ⎟ ⎟ − 1 (13)
()\i ⎜
∈
⎝ x + y j ⎠
j
|D|
|D|
将 CNF 公式对应的因子图的消息边进行随机排序,构造序列集合 D={a→i:(a,i)∈E},定义函数 f:\ →\ ,
则其分量为 f(λ) a→i =λ a→i .那么函数 f 的迭代过程能够表示为算法中的消息并行更新过程.因此,由引理 1 可知,计