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

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

算 sup || | f ′ ( ) | 1λ < ,则可以得到判定算法收敛的条件.由前文第 1 节可知,V u ( )j ∩ V s ( )j =∅ .下面分两种情形
λ∈\ D a a
进行讨论.
• 情形 1:设 bV∈ a u ()j ,根据公式(13),有:
∂ λ
f ′ (λ ) = a→ i
a→
j
, i b→
∂ λ b→ j
⎛ x ⎞ ′ 1 ⎛ x ⎞
= 2⎜ j ⎟ ⎜ ∏ k ⎟
⎜ x + ⎟ 1tanh λ kV a x +
−
∈
2
()\ , i j
⎝ j x j ⎠ a→ i ⎝ k y k ⎠
− xy′ ⎛ x ⎞
= 2 j j ⎜ ∏ k . ⎟
−
(x + j y j ) (1 tanh λ a→ i ) kV a ⎝ x + k y k ⎠
2
∈
()\ , i j
2
1 1
(1 tanhλ −
由于 y′ =− (1 tanh λ − 2 b→ j ) ∏ u (1 tanhλ c→ j ) =− + b→ j ) ,
y
j
j
2 cV∈ a ()\b 2
j
所以,
∂ λ a→ i = xy j (1 tanhλ+ b→ j ) ⎛ ⎜ ∏ x k ⎞
j
∂ λ b→ j 2 (x + j y j ) (1 tanh λ 2 − 2 a→ i ) kV a∈ ()\ , i j ⎝ x + k y k ⎠ ⎟
y (1 tanhλ + b→ )(1 tanhλ + a→ )
= j j i
(x + j y j )(1 tanh λ a→ i )
2
−
+
y 1tanhλ
= j b→ j .
x + j y j 1tanhλ a→ i
−
由公式(13)可知:
⎛ x ⎞ ⎛ x ⎞ ⎛ x ⎞
tanhλ a→ i = 2 ∏ jVa ⎜ j ⎟ ⎟ − 1 2⎜ = ⎜ j ⎟ k V a ⎜ ∏ k ⎟ − ⎟ 1,
()\i ⎜
∈
∈
( )\ , i j
⎝ x + j y j ⎠ ⎝ x + j y j ⎠ ⎝ x + k y k ⎠
⎛ x ⎞
其中, 0≤ ⎜ ∏ k ⎟ ≤ 1,
∈
()\ , i j
kV a x + y
⎝ k k ⎠
⎛ x ⎞
所以, tanhλ a→ i ≤ 2⎜ ⎜ j ⎟ ⎟ − 1.
⎝ x + y j ⎠
j
进一步有:
y 1tanhλ λ + b→ ∂ y 1 tanhλ + y 1tanhλ + 1
a→ i = j j j b→ j = j b→ j = ≤ (1 tanhλ+ ) 1,<
∂ λ x + y 1tanhλ − x + y ⎛ x ⎞ x + y y j 2 b→ j
a→
b→
j
i
j
j
1− j j 2 j − ⎜ 1⎟ j j 2
⎜ x + ⎟ x + y
⎝ j y j ⎠ j j
∂ λ
因此, a→ i < 1.
∂ λ b→ j
• 情形 2:设 bV∈ s ()j ,根据公式(13)有:
a
∂ λ
f ′ (λ ) = a→ i
a→
, i b→
j
∂ λ b→ j
⎛ x ⎞ ′ 1 ⎛ x ⎞
= 2⎜ j ⎟ ⎜ ∏ k ⎟
⎜ x + x ⎟ 1tanh λ kV a x + y
−
2
∈
()\ , i j
⎝ j j ⎠ a→ i ⎝ k k ⎠
xy ′ ⎛ x ⎞
= 2 j j ⎜ ∏ k . ⎟
∈
(x + j y j ) (1 tanh λ a→ i ) kV a ⎝ x + k y k ⎠
−
2
2
()\ , i j
(1 tanhλ −
x
由于 x′ =− 1 (1 tanh λ − 2 j ∏ 1 (1 tanhλ ) =− + ) ,
)
s
j 2 b→ cV∈ a j 2 c→ j b→ j j
()\b