摘 要：信息傳播算法來自統(tǒng)計(jì)物理，被廣泛應(yīng)用于人工智能各個(gè)領(lǐng)域，特別是求解組合優(yōu)化問題時(shí)，具有良好的有效性。通過對信息傳播算法的相關(guān)文獻(xiàn)進(jìn)行分析，綜述了信息傳播算法以及其相關(guān)應(yīng)用的發(fā)展史，根據(jù)信息傳播算法的發(fā)展，介紹了求解可滿足性問題的信息傳播算法相關(guān)概念，主要涉及到警示傳播算法、置信傳播算法和調(diào)查傳播算法，描述了三種算法發(fā)展中出現(xiàn)的收斂性、有效性研究，分別綜述了各個(gè)算法在相關(guān)領(lǐng)域的應(yīng)用情況，并總結(jié)了信息傳播算法的研究路徑和應(yīng)用方向。

關(guān)鍵詞：信息傳播算法； 組合優(yōu)化； 可滿足性問題； 警示傳播； 置信傳播； 調(diào)查傳播

中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2022）07-002-1933-08

doi：10.19734/j.issn.1001-3695.2021.10.0644

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（62062001，61762019，61862051，61962002）；北方民族大學(xué)重大專項(xiàng)資助項(xiàng)目（ZDZX201901）；寧夏自然科學(xué)基金資助項(xiàng)目（2020AAC03214，2020AAC03219，2019AAC03120，2019AAC03119）

作者簡介：謝志新（1997-），男，陜西渭南人，碩士研究生，主要研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)；王曉峰（1980-），男（通信作者），甘肅會寧人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)槿斯ぶ悄埽▁fwang@nmu.edu.cn）；曹澤軒（1998-），男，寧夏中衛(wèi)人，碩士研究生，主要研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)；于卓（1997-），男，寧夏銀川人，碩士研究生，主要研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)；莫淳惠（1994-），女，重慶人，碩士研究生，主要研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)；吳宇翔（1997-），男，寧夏銀川人，碩士研究生，主要研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì).

Overview of message propagation algorithm for satisfiability problems

Xie Zhixina， Wang Xiaofeng^a，b?， Cao Zexuana， Yu Zhuoa， Mo Chunhuia， Wu Yuxianga

（a.School of Computer Science amp; Engineering， b.Key Laboratory of Image amp; Graphics Intelligent Processing of State Ethnic Affairs Commission， North Minzu University， Yinchuan 750021， China）

Abstract：Message propagation algorithms from statistical physics are widely used in various fields of artificial intelligence， especially in solving combinatorial optimization problems. According to the related literatures of message propagation algorithm， this paper summarized the history of message propagation algorithm and its related application. According to the deve-lopment of message propagation algorithm， it introduced the concepts of information propagation algorithm for solving the satisfiability problem， which mainly involved the warning propagation algorithm， the belief propagation algorithm and the survey propagation algorithm. This paper described the convergence and effectiveness research of the three kind of algorithms， summarized the application of each algorithm in related fields， and summarized the research path and application direction of message propagation algorithm.

Key words：message propagation algorithm; combinatorial optimization; satisfiability problems; warning propagation; belief propagation; survey propagation

約束滿足問題（constraint satisfiability problems，CSP）是計(jì)算機(jī)科學(xué)、數(shù)學(xué)和物理學(xué)等多個(gè)學(xué)科的熱點(diǎn)研究問題，CSP在電路設(shè)計(jì)、模型診斷、模式識別、定理證明、人工智能和機(jī)器學(xué)習(xí)等諸多領(lǐng)域都有非常廣泛的應(yīng)用^［1］，受到諸多學(xué)者的關(guān)注。在實(shí)際生活中有許多問題可以歸約到CSP上，如TSP^［2］、圖著色問題、調(diào)度問題、圖像識別等，因此研究CSP有重要的理論和實(shí)際意義。

可滿足性判定問題（satisfiability，SAT）是典型的約束滿足問題，已經(jīng)被證明是NP完全的^［3］，并且其NP完全特性被廣泛地應(yīng)用在對其他領(lǐng)域NP完全問題的探究。對于SAT問題的判定求解存在著完備性算法和非完備性算法兩類，完備性算法主要基于回溯和窮舉的思想，非完備性算法則基于局部搜索和啟發(fā)式的思想。完備性算法在求最優(yōu)解和證明無解上表現(xiàn)十分有效，但其求解的時(shí)間和空間消耗也同樣龐大，往往出現(xiàn)對問題的求解無法在給定時(shí)間內(nèi)完成；非完備性算法在求解時(shí)間上優(yōu)勢十分明顯，但其在求解SAT問題上仍存在失效問題，求解SAT問題的信息傳播算法^［4］在K-SAT問題的難解區(qū)域非常有效，特別在隨機(jī)3-SAT實(shí)例求解上相對于其他非完備性算法效果顯著。

信息傳播算法是一種基于因子圖計(jì)算貝葉斯網(wǎng)路和馬爾可夫隨機(jī)場邊集分布的消息傳遞算法，Braunstein等人^［5］提出警示傳播算法（warning propagation，WP）、置信傳播算法（belief propagation，BP）和調(diào)查傳播算法（survey propagation，SP）三種信息傳播算法用于求解SAT問題。對于信息傳播算法求解SAT問題存在一些難點(diǎn)，主要在于：a）算法的收斂情況，信息傳播算法通過算法迭代收斂的信息構(gòu)造一個(gè)滿足SAT問題的指派，隨著問題規(guī)模和求解難度的增加算法收斂性就難以保證，對問題求解的有效性有很大影響；b）圖模型結(jié)構(gòu)，信息傳播算法在樹型結(jié)構(gòu)因子圖上能夠有效收斂，但因子圖結(jié)構(gòu)中隨著環(huán)的數(shù)目增加，算法的有效性和收斂性會受到很大影響。

本文將從三種信息傳播算法收斂性分析與相關(guān)應(yīng)用改進(jìn)展開綜述，首先介紹相關(guān)知識，其次對三種信息傳播算法的原理、收斂性和相關(guān)應(yīng)用進(jìn)行介紹，最后指出信息傳播算法需要進(jìn)一步研究的工作和關(guān)鍵問題。

1 相關(guān)知識

1.1 因子圖（factor graph）

因子圖是一個(gè)二部圖，表示許多變量的全局函數(shù)分解成局部函數(shù)的乘積^［6］。因子圖中包含變元節(jié)點(diǎn)及子句節(jié)點(diǎn)兩類節(jié)點(diǎn)。變元節(jié)點(diǎn)由圓表示，子句節(jié)點(diǎn)由方框表示，實(shí)邊表示變元在子句中正出現(xiàn)，虛邊表示變元在子句中負(fù)出現(xiàn)。對于一個(gè)CNF公式：

F=（?x1∨x2∨x3）∧（?x1∨x2∨?x4）∧

（x2∨?x3∨?x5）∧（x2∨?x4∨?x5）=a1，a2，a3，a4

其因子圖如圖1所示。

信息傳播算法迭代過程在因子圖上進(jìn)行，因子圖結(jié)構(gòu)對算法求解有著重要影響。已經(jīng)證明當(dāng)因子圖為樹型結(jié)構(gòu)時(shí)，信息傳播算法可以有效收斂，對于因子圖含有多個(gè)回路結(jié)構(gòu)的實(shí)例，信息傳播算法不總是有效，常表現(xiàn)為不收斂^［5］。

1.2 SAT問題

CSP由N個(gè)彼此互不相同的變量和M個(gè)彼此互不相同的約束組成，這 N 個(gè)變量可以在各自的定義域 D中隨機(jī)取值，每個(gè)約束Ci是由從這N個(gè)變量中選擇出的k個(gè)變量組成，對每個(gè)Ci都有一個(gè)不協(xié)調(diào)賦值集Qc控制這些變量，使得這些變量的部分賦值為不可滿足賦值^［7］。SAT問題是典型的CSP，當(dāng)給定一個(gè)合取范式公式（conjunctive normal form，CNF）F，可滿足性判定問題是指是否存在一組指派使得合取范式F為真^［8］。在特殊結(jié)構(gòu)SAT問題研究中，3-SAT問題是當(dāng)前K-SAT問題研究中的重要領(lǐng)域。

隨機(jī)K-SAT問題的實(shí)例產(chǎn)生模型G（n，k，m）中，n為布爾變量個(gè)數(shù)，m為子句個(gè)數(shù)，k為每個(gè)子句中文字的個(gè)數(shù)。將m替換為p引入模型G（n，k， p），n表示布爾變元的個(gè)數(shù)，k表示子句中文字的數(shù)目，p表示每個(gè)子句出現(xiàn)在公式中的概率^［9］。子句的數(shù)目為以概率p在子句集中選取子句構(gòu)成K-SAT實(shí)例。研究表明當(dāng)K為1、2時(shí)，1-SAT和2-SAT問題在多項(xiàng)式時(shí)間內(nèi)可解的，當(dāng)K≥3時(shí)，SAT問題就是一個(gè)NP完全問題。隨機(jī)3-SAT實(shí)例產(chǎn)生模型中研究發(fā)現(xiàn)在相變點(diǎn)附近，3-SAT問題求解困難。

3-SAT問題中有滿足與不可滿足之間的臨界現(xiàn)象，對于3-SAT問題可滿足相變點(diǎn)αd，當(dāng)αlt;αd時(shí)實(shí)例高概率滿足，反之高概率不滿足。在SAT-UNSAT相變區(qū)域，解空間會分裂成指數(shù)級的小解簇，即聚類相變^{［10，11］}。當(dāng)αlt;αd時(shí)，每個(gè)變量沒有太多的約束，解集之間彼此連通；當(dāng)αgt;αd時(shí)，解集分裂成不連通的聚類。研究表明αd至少為3.52^［12］至多為4.489 8^［13］。研究證明BP算法可以有效地求解α＜3.95區(qū)域內(nèi)的隨機(jī)3-SAT實(shí)例，SP算法可以有效地求解α＜4.26的隨機(jī)3-SAT實(shí)例。SP算法是求解3-SAT問題最有效的算法，在具有10⁷變量規(guī)模的難解SAT實(shí)例上，SP算法能夠在稍高于線性時(shí)間求解，并且?guī)缀跄軌蛴行У厍蠼饨咏韵嘧凕c(diǎn)的可滿足性實(shí)例^{［14～16］}。

2 警示傳播（WP）算法

2.1 基本算法

警示傳播算法將子句節(jié)點(diǎn)傳遞給變元節(jié)點(diǎn)的消息稱為警示信息，記為ua→i。當(dāng)ua→i值可取0/1時(shí)，值為1時(shí)表示子句a的可滿足性由變元xi的取值決定，值為0時(shí)表示變元xi的取值無法對子句a的可滿足性起到?jīng)Q定性作用。WP算法的信息更新迭代方程如下：

其中：V（a）表示子句a中出現(xiàn)的變元集合；V（a）＼i表示句a中除變元后剩余的變元集合；Jaj表示變元在子句中的正負(fù)出現(xiàn)情況，正出現(xiàn)值為-1，負(fù)出現(xiàn)值為1；t表示迭代次數(shù)；θ（x）表示截尾函數(shù)，當(dāng)x＞0時(shí)，其值為1，否則為0。

若子句a中僅包含變元xi時(shí)，說明子句a的可滿足性由變元xi決定，則將ua→i的值記為1。在WP算法收斂的情況下，可以根據(jù)警示信息來固定變元xi的值：

Hi＜0時(shí)，xi賦值為0，Hi＞0時(shí)，xi賦值為1；否則暫時(shí)不對xi進(jìn)行賦值。一般情況下，將式（1）改寫為變元xj正負(fù)出現(xiàn)的子句集合之差的形式如下：

其中：V+（j）＼a表示變元xj以正文字出現(xiàn)，并且不包含子句a的子句集合，當(dāng)xj在此集合中，Jaj值為-1；V－（j）＼a表示xj變元以負(fù)文字出現(xiàn)，并且不包含子句a的子句集合，當(dāng)xj在此集合中，Jaj值為1；hj→a表示腔域，當(dāng)變元xj只出現(xiàn)在子句a中，賦值為1。

算法1 WP算法

輸入：CNF公式;迭代終止步數(shù)tf。

輸出：警示信息或未收斂。

a） 根據(jù)CNF公式構(gòu)造相應(yīng)的因子圖;

b） 初始化迭代次數(shù)t=0，對因子圖上的每條邊，即對于ua→i以均等概率從{0，1}選擇一個(gè)進(jìn)行賦值;

c） for t=1 to tf

對因子圖的邊進(jìn)行隨機(jī)排列，根據(jù)隨機(jī)排列的順序，利用式（1）對警示信息u*a→i進(jìn)行更新;

d） if ua→i（t）=ua→i（t－1）

u*a→i=ua→i（t）;

返回u*a→i;

退出循環(huán);

e）" t==tf 返回未收斂。

2.2 收斂性

警示傳播算法收斂性對SAT問題求解有著重要意義，當(dāng)WP算法收斂，根據(jù)收斂的警示信息便可以得到一組滿足CNF公式指派。文獻(xiàn)［17］在隨機(jī)可滿足實(shí)例集上研究了警示傳播算法的收斂，提出在隨機(jī)3-SAT實(shí)例產(chǎn)生模型G（n，3，p），當(dāng)p≤1/8n²時(shí)產(chǎn)生的3-SAT實(shí)例集高概率收斂。文獻(xiàn)［18］在植入指派的隨機(jī)可滿足實(shí)例產(chǎn)生模型Ρ^plantn，p上利用指派在滿足指派的子句中以概率p隨機(jī)選擇構(gòu)成實(shí)例分析WP算法的收斂性。

命題公式結(jié)構(gòu)影響著信息傳播算法的收斂性，文獻(xiàn)［19］引入結(jié)構(gòu)熵度量命題公式復(fù)雜性，利用因子圖轉(zhuǎn)換模型在無向連通圖上構(gòu)造分割樹并計(jì)算其中節(jié)點(diǎn)的熵值，相加得到CNF公式結(jié)構(gòu)熵。實(shí)驗(yàn)給出不同規(guī)模圖結(jié)構(gòu)上的WP算法收斂充分條件，并可擴(kuò)展到其他規(guī)模求解。文獻(xiàn)［8］將WP算法的信息取值從{0，1}松弛到［0，1］，利用向量空間中壓縮函數(shù)的性質(zhì)給出當(dāng)方陣M的譜半徑ρ（M）嚴(yán)格小于1，WP算法收斂且與初始信息無關(guān)。

針對WP算法當(dāng)子句變元比大于3.9時(shí)在3-SAT實(shí)例集上高概率不收斂的情況，文獻(xiàn)［20］提出一種將3-SAT轉(zhuǎn)換為等價(jià)（3，4）-SAT的轉(zhuǎn)換規(guī)則，在子句變元比大于3.9的情況下，轉(zhuǎn)換后的（3，4）-SAT規(guī)則實(shí)例集在WP算法上高概率收斂，并且轉(zhuǎn)換過程在多項(xiàng)式時(shí)間內(nèi)可完成。研究人員發(fā)現(xiàn)公式中存在一種特殊結(jié)構(gòu)骨干集和后門集，影響著公式的求解難度。文獻(xiàn)［21］利用骨干集和后門集變量之間的關(guān)系，提出一種WP可解公式，證明得出當(dāng)隨機(jī)3-CNF的公式F為WP可解公式時(shí)，WP算法高概率收斂。

2.3 相關(guān)改進(jìn)及應(yīng)用

WP算法在SAT問題的求解上有著不錯(cuò)的表現(xiàn)，但仍存在一些不足，如對圖模型的要求、迭代次數(shù)高等問題，這里選擇幾種具有代表性的改進(jìn)和一些具體問題求解進(jìn)行論述。

WP算法特性限制其只能在因子圖上對問題進(jìn)行迭代求解，當(dāng)問題圖結(jié)構(gòu)非因子圖時(shí)需要進(jìn)行圖結(jié)構(gòu)的轉(zhuǎn)換。文獻(xiàn)［22］將WP算法應(yīng)用于求解雙目標(biāo)最小生成樹，利用限制Boltzman機(jī)（restricted Boltzmann machine，RBM）模型將無向圖轉(zhuǎn)換為因子圖，并對WP算法的信息迭代方程進(jìn)行了修改，修改的方程如下：

在算法中，將兩次相鄰迭代警示信息之差小于設(shè)定閾值的節(jié)點(diǎn)納入結(jié)果集。實(shí)驗(yàn)證明算法在求解精度和范圍上優(yōu)于動(dòng)態(tài)粒子群算法，在求解速度上優(yōu)于MACS和枚舉法。文獻(xiàn)［23］借助隱馬爾可夫模型將無向圖轉(zhuǎn)換為因子圖，將最小割問題在因子圖上求解，提出一種求解最小割的WP算法，通過對WP算法收斂方向限制，保證算法在相鄰節(jié)點(diǎn)的權(quán)值較小方向收斂，當(dāng)跳數(shù)為3且算法收斂時(shí)，計(jì)算得到解。實(shí)驗(yàn)表明，在若干小實(shí)例集平均求解時(shí)間優(yōu)于K、L等啟發(fā)式算法。

研究發(fā)現(xiàn)，關(guān)鍵文字集影響布爾公式可滿足性判定的難度，利用關(guān)鍵文字對公式化簡，在可滿足公式求解器設(shè)計(jì)中很有意義。文獻(xiàn)［24］通過對WP算法原理研究分析，提出了一種求解公式關(guān)鍵文字集算法，利用 WP算法警示信息ua→i為1，對應(yīng)變元取值唯一的特征，WP算法收斂時(shí)，輸入的可滿足CNF公式F中滿足ua→i=1的變元集合構(gòu)成一個(gè)關(guān)鍵文字子集。

算法的迭代次數(shù)與運(yùn)行時(shí)間是算法評價(jià)的一個(gè)重要指標(biāo)，針對WP算法迭代次數(shù)和運(yùn)行時(shí)間過高的情況，文獻(xiàn)［25］提出一種改進(jìn)的WP算法。通過對t=0步的隨機(jī)賦值策略進(jìn)行修改，當(dāng)圖中存在子句節(jié)點(diǎn)和變元節(jié)點(diǎn)為葉節(jié)點(diǎn)時(shí)，根據(jù)單位子句變元特性對部分警示信息賦值，然后利用得到的警示信息對其他警示信息及變元進(jìn)行賦值。在Bart可滿足實(shí)例集與Homer不可滿足實(shí)例集與WP算法相比得到迭代次數(shù)和時(shí)間更優(yōu)。WP算法雖在正則（3，4）-SAT實(shí)例上高概率收斂，但因?yàn)樗惴ǖ^程得到的警示信息僅能固定少量變元，導(dǎo)致對公式可滿足性的判定常常失效。佘光偉等人^［26］提出了一種基于變元正負(fù)出現(xiàn)次數(shù)的修正WP算法，當(dāng)?shù)唤M警示信息u*a→i=ua→i（t）并且未達(dá)到最大迭代次數(shù)時(shí)，根據(jù)變元出現(xiàn)的正 負(fù)次數(shù)之差定義規(guī)則固定變元的值并進(jìn)行圖清洗得到新圖，在新圖上重置迭代次數(shù)，繼續(xù)進(jìn)行迭代，直至圖中變元集未賦值為空，返回一組可滿足指派。實(shí)驗(yàn)結(jié)果表明該算法在（3，4）-SAT實(shí)例集上有效。

WP算法在RB模型產(chǎn)生的大部分實(shí)例集上無法收斂，文獻(xiàn)［27］提出一種改進(jìn)的警示傳播算法與DPLL算法結(jié)合的啟發(fā)式?jīng)Q策性算法求解RB實(shí)例，對t=0時(shí)隨機(jī)賦值規(guī)則進(jìn)行了修改，通過設(shè)置初始警示信息降低了算法的迭代次數(shù)，算法收斂速度得到提高。在WP算法不收斂時(shí)，利用得到的局部警示信息給出一組近似賦值，將其作為DPLL算法調(diào)用的賦值進(jìn)行求解。該算法大大降低了回溯的次數(shù)，彌補(bǔ)了WP算法的不足，在RB實(shí)例集上有著較好的求解效果。

當(dāng)子句變量比α＞3.5時(shí)，WP算法經(jīng)常不收斂，文獻(xiàn)［28］提出以WP算法為基礎(chǔ)的WPY算法，能夠更加有效地求解MAX-3-SAT問題。當(dāng)WP算法不收斂，WPY算法先計(jì)算出警示信息變化最小的時(shí)刻t，利用t時(shí)刻警示信息對變元進(jìn)行固定，刪除已滿足子句，完成公式簡化。實(shí)驗(yàn)結(jié)果顯示與UBCSAT^［29］對比，當(dāng)4.1≤α≤4.5時(shí)，WPY算法表現(xiàn)更優(yōu)，并且WPY算法結(jié)果中違反約束的子句數(shù)目更少。

最小頂點(diǎn)覆蓋問題屬于圖論中最困難的一類優(yōu)化問題^［30］，當(dāng)圖規(guī)模增大時(shí)，算法求解時(shí)間呈指數(shù)型增長，確定型算法也只適用于點(diǎn)規(guī)模為數(shù)百個(gè)的圖，求解能力有限。文獻(xiàn)［31］利用信息傳播算法求解頂點(diǎn)覆蓋問題，定義警示信息：頂點(diǎn)u和v為圖中相鄰頂點(diǎn)，當(dāng)u在MVC（最小頂點(diǎn)覆蓋集）時(shí)，值為0警示信息從u到v，否則從u到v的警示信息為1。警示信息更新規(guī)則為當(dāng)所有到u的警示信息為0時(shí)，將u到v的警示信息賦值為1。實(shí)驗(yàn)顯示當(dāng)圖的平均度不超過e時(shí)，WP算法收斂，結(jié)果精確且與圖規(guī)模無關(guān)，但算法的警示傳播迭代不是線性時(shí)間。針對此問題，文獻(xiàn)［32］提出一種改進(jìn)的線性時(shí)空復(fù)雜度警示傳播算法MVC-WP解決最小頂點(diǎn)覆蓋問題。MVC-WP算法在從頂點(diǎn)u到v更新消息時(shí)，添加數(shù)組計(jì)數(shù)器追蹤傳入v警示信息為1的消息數(shù)量，從而將警示傳播迭代時(shí)間降低為線性；同時(shí)算法在警示信息迭代過程前后引入預(yù)處理和后處理步驟，智能地初始化消息；在警示信息迭代之前利用剪葉算法確定必然存在某個(gè)MVC中的頂點(diǎn)，對輸入圖進(jìn)行修改。通過在四組實(shí)例上測試，MVC-WP算法優(yōu)于大多數(shù)線性時(shí)空MVC求解算法。

WP算法的相關(guān)應(yīng)用改進(jìn)對比如表1所示。

3 置信傳播（BP）算法

3.1 基本算法

置信傳播算法中定義兩類消息類型μa→i（xi）和μi→a（xi）。在因子圖邊（a，i）上，μa→i（xi）是指子句節(jié)點(diǎn)傳遞給變元節(jié)點(diǎn)的消息，同時(shí)也表示變元i的取值xi為使得子句a滿足的概率；μi→a（xi）是指變元節(jié)點(diǎn)傳遞給字句節(jié)點(diǎn)的消息，同時(shí)也表示在不受子句a的影響下變元i取值為xi的概率^{［33，34］}。

BP算法的迭代方程如下：

其中：Ci→a/Ca→i是歸一化因子，保證得到的最終結(jié)果是一個(gè)概率值；fa（X）是標(biāo)志函數(shù)，X={xi}使得子句a滿足時(shí)，fa（X）為1，否則為0。為了將μi→a（xi）的表示參數(shù)化，引入γi→a∈［0，1］，表示變元xi的取值不滿足子句a的概率。將式（5）改寫為

其中：δ（xi，{0，1}）為xi取值為0或1的事件。子句中非變元i的其他變元不滿足子句a的概率由式（9）計(jì)算。

算法2 BP算法

輸入：CNF公式;迭代終止步數(shù)tf。

輸出：未收斂或偏置信息。

a） 根據(jù)CNF公式構(gòu)建相應(yīng)的因子圖；

b） 將迭代次數(shù)t初始化為0，并對因子圖的每條邊隨機(jī)賦值為δa→i（t=0）∈［0，1］；

c） t=1 while t≤ tf

對所有的消息邊進(jìn)行隨機(jī)排序，利用BP迭代方程進(jìn)行δa→i的更新；

if |δa→i（t）－δa→i（t－1）|lt;ε

返回算法收斂；

break while

d） if t=tf

返回算法未收斂；

else δa→i=δa→i（t）。

3.2 收斂性

置信傳播算法已經(jīng)被證明在無循環(huán)圖中表現(xiàn)最優(yōu)，通過仿真實(shí)驗(yàn)證明即使在含有環(huán)的情況下，依然能保證接近最優(yōu)的性能^［35］。文獻(xiàn)［36］分析得出信息傳播算法在高斯模型上總可以正確收斂；文獻(xiàn)［37］將BP算法中的信息迭代方程取雙曲正切，將迭代方程的取值從（0，1）擴(kuò)展到（-∞，+∞），利用壓縮函數(shù)性質(zhì)，給出BP算法收斂的一個(gè)判定條件。構(gòu)造的方陣M譜半徑小于1，BP算法一定能達(dá)到收斂點(diǎn)，且不依賴于初始條件。

文獻(xiàn)［38］給出一種適用性更普遍的高斯BP算法收斂條件，利用提出的基于分布線性高斯模型因式分解方法，證明了因子圖是一個(gè)環(huán)和森林的并集時(shí)高斯BP總是收斂的。文獻(xiàn)［39］研究了高斯BP算法的收斂速度，在廣義對角占優(yōu)的條件下，給出邊界均值指數(shù)收斂速度的一個(gè)簡單界。文獻(xiàn)［40］利用二維結(jié)構(gòu)熵與基于警示傳播的社區(qū)發(fā)現(xiàn)算法（WPLPA）建立命題公式的二維結(jié)構(gòu)熵度量模型，對BP算法收斂性進(jìn)行了分析并給出收斂性判定的條件。通過實(shí)驗(yàn)對比發(fā)現(xiàn)WPLPA算法對因子圖的社區(qū)劃分效果顯著，在變元n=10和n=20、結(jié)構(gòu)熵分別小于2.425 6和2.498 2時(shí)，BP算法高概率收斂;當(dāng)n=60和n=80、結(jié)構(gòu)熵分別大于5.493 6和6.367 5時(shí)，BP算法高概率不收斂，可以發(fā)現(xiàn)BP算法的性能隨著結(jié)構(gòu)熵持續(xù)增加而無法保證。

3.3 相關(guān)改進(jìn)及應(yīng)用

BP算法求解組合優(yōu)化問題有著優(yōu)秀的表現(xiàn)，有著豐富的改進(jìn)和應(yīng)用。文獻(xiàn)［41］指出隨著節(jié)點(diǎn)的邊增加超過閾值，BP算法的計(jì)算量呈指數(shù)級上升，提出一種迭代用戶分組檢測的BP算法，通過IMUD（迭代用戶分組檢測）降低了每個(gè)功能節(jié)點(diǎn)的計(jì)算復(fù)雜度。實(shí)驗(yàn)結(jié)果顯示該算法比最佳BP算法快了三倍以上。

循環(huán)置信傳播（loopy belief propagation，LBP）算法是在帶圈圖上的一種迭代算法。文獻(xiàn)［42］在深度圖恢復(fù)中使用LBP，在深度圖中利用LBP可以將信息從高可信深度值像素傳播到具有低可信深度值像素，在成對MRF框架中，像素被建模為具有四個(gè)連通鄰居節(jié)點(diǎn)，使用LBP迭代地計(jì)算每個(gè)像素的每個(gè)深度值的置信概率，實(shí)驗(yàn)結(jié)果表明比使用分層表示的深度圖恢復(fù)有更好的效果。文獻(xiàn)［43］提出一種利用多層超像素圖和循環(huán)信念傳播進(jìn)行高光譜圖像分類方法，利用偽小波系數(shù)對因子圖上像素與相鄰像素之間的成對關(guān)系進(jìn)行建模，通過LBP傳播近似圖像概率;方法中結(jié)合了超像素中的光譜和空間信息，LBP在多層圖中傳播的信息用來平滑分類結(jié)果，與僅使用光譜的分類方法相比，效果顯著。

文獻(xiàn)［44］提出了一種加權(quán)循環(huán)置信傳播算法（WLBP），在分布式無線認(rèn)知網(wǎng)絡(luò)中的數(shù)據(jù)融合中，將二級用戶網(wǎng)絡(luò)建模為馬爾可夫隨機(jī)場，利用WLBP促進(jìn)分布式?jīng)Q策融合。WLBP對陰影衰落節(jié)點(diǎn)和惡意節(jié)點(diǎn)賦予較小的權(quán)重值，降低了這些節(jié)點(diǎn)的影響，實(shí)驗(yàn)結(jié)果表明在陰影衰落節(jié)點(diǎn)或惡意節(jié)點(diǎn)較多時(shí)，WLBP穩(wěn)定性優(yōu)于LBP。

傳統(tǒng)BP算法在低密度奇偶校驗(yàn)碼（LDPC）譯碼效果顯著，但在RS碼這種高密度奇偶校驗(yàn)碼（HDPC）上效果一般。自適應(yīng)置信傳播（ABP）算法將二進(jìn)制奇偶校驗(yàn)矩陣的子矩陣簡化為稀疏性質(zhì)，幾何上可以解釋為具有自適應(yīng)勢函數(shù)的兩階段梯度下降算法，這種自適應(yīng)過程對梯度下降算法的收斂行為至關(guān)重要，因此可以顯著提高性能^［45］。ABP算法在RS解碼上具有優(yōu)異的性能，但在實(shí)際應(yīng)用中難以低復(fù)雜度實(shí)現(xiàn)。文獻(xiàn)［46］提出一種結(jié)合Chase算法^［47］的ABP-Chase算法，在每次ABP迭代中級聯(lián)一個(gè)Chase解碼器作為算法一種有效終止準(zhǔn)則。新的準(zhǔn)則中，算法運(yùn)行之前運(yùn)行一個(gè)Chase型解碼器，當(dāng)成功地找到一個(gè)有效碼字，便避免了ABP迭代，并節(jié)省了大量計(jì)算；第二個(gè)Chase型解碼器在每次ABP更新后運(yùn)行，結(jié)果比ABP-BM^{［45，48］}算法的迭代次數(shù)更少，尤其在高信噪比區(qū)域，復(fù)雜度顯著降低。ABP算法在Turbo解碼中也有著良好的表現(xiàn)，但同樣存在解碼復(fù)雜度和迭代次數(shù)過高的問題。文獻(xiàn)［49］提出一種簡化的m-ABP算法，在算法迭代循環(huán)中消去自適應(yīng)，只保留初始化階段的自適應(yīng)，即消去矩陣稀疏化。由于矩陣的更新階段和比特可靠性階段不同于標(biāo)準(zhǔn)ABP算法處于迭代循環(huán)中，ABP算法的復(fù)雜度明顯降低。通過仿真實(shí)驗(yàn)顯示，m-ABP算法在解碼復(fù)雜度和迭代次數(shù)上優(yōu)于標(biāo)準(zhǔn)ABP算法，誤碼率與經(jīng)典的Chase-Pyndiah^［50］算法的性能相似，并且在高數(shù)據(jù)速率的應(yīng)用上有著高度的并行性。

文獻(xiàn)［51］將并行思想與BP算法結(jié)合，在速率兼容調(diào)制（RCM）^{［52，53］}應(yīng)用中效果顯著。在符號節(jié)點(diǎn)中，RCM-PBP采用幾個(gè)低復(fù)雜度的子處理器來獨(dú)立解碼子比特向量，處理器之間不存在交叉連接。當(dāng)映射矩陣的權(quán)重集設(shè)置為{±1，±2，±4，±4}，與原始的RCM-BP算法相比在符號節(jié)點(diǎn)處，所需的乘法和加法至少減少了80%和85%，并且解碼的性能沒有下降。文獻(xiàn)還提出將RCM-PBP算法與文獻(xiàn)［54，55］提出的對數(shù)域解碼算法相結(jié)合，實(shí)現(xiàn)減少加法和查找表的目標(biāo)。

立體匹配是計(jì)算機(jī)視覺的重要研究領(lǐng)域之一，其利用置信傳播作為馬爾可夫隨機(jī)場模型的全局能量最小化方法。文獻(xiàn)［56］提出基于模糊度梯度的分層信任傳播立體匹配方法，像素的信念沿著模糊度梯度傳遞到鄰域，信念在每次迭代傳播中改變了模糊度梯度和分割約束，這種方式能使視差平面更快地收斂和更好地細(xì)化，利用改變信念傳播強(qiáng)度有效處理了無紋理和不連續(xù)區(qū)域。實(shí)驗(yàn)表明，該方法能夠正確地估計(jì)大遮擋區(qū)域和無紋理區(qū)域等硬區(qū)域的視差。在立體匹配中全局方法和局部方法各自有著優(yōu)缺點(diǎn)，文獻(xiàn)［57］提出了一種結(jié)合交叉聚合和分層信念傳播的立體匹配方法，將全局方法和局部方法相結(jié)合，利用局部方法對全局方法所存在的視差結(jié)果進(jìn)行優(yōu)化，利用亞像素增強(qiáng)來細(xì)化視差結(jié)果的左右一致性檢查。通過實(shí)驗(yàn)與AD方法^［58］對比，圖像邊緣明顯改善。

網(wǎng)絡(luò)最大流問題屬于NP難問題，目標(biāo)求解在約束條件下使得網(wǎng)絡(luò)中流量最大。文獻(xiàn)［59］結(jié)合BP傳遞方程與最大流問題線性規(guī)劃方程提出一種求解網(wǎng)絡(luò)最大流算法BP-MF，將問題的帶權(quán)有向圖轉(zhuǎn)換為因子圖，隨之利用信息迭代方程進(jìn)行信息值的迭代循環(huán)完成最大流、節(jié)點(diǎn)信息和各邊流量值的計(jì)算。實(shí)驗(yàn)表明，隨著問題規(guī)模增大，BP-MF算法在時(shí)間復(fù)雜度、收斂性和數(shù)據(jù)溢出性能上優(yōu)于EK、Ford-Fulkerson算法，但算法僅研究了流量值為整數(shù)時(shí)的情況，在問題規(guī)模較小的情況下，BP-MP性能不占優(yōu)。文獻(xiàn)［60］提出BP-MCMF算法求解最小費(fèi)用最大網(wǎng)絡(luò)流問題，問題需要考慮流量和費(fèi)用兩個(gè)因素，即在保證網(wǎng)絡(luò)最大流的基礎(chǔ)上使得網(wǎng)絡(luò)中流量費(fèi)用最小^［61］。利用迭代方程計(jì)算得出最大流并設(shè)置最大流閾值，然后計(jì)算最小費(fèi)用，通過數(shù)值實(shí)驗(yàn)證明BP-MCMF算法在尋優(yōu)表現(xiàn)和迭代時(shí)間優(yōu)于負(fù)回路和最小費(fèi)用路算法，但在網(wǎng)絡(luò)規(guī)模較大的情況下存在著計(jì)算數(shù)據(jù)溢出問題。

BP算法的相關(guān)應(yīng)用改進(jìn)對比如表2所示。

4 調(diào)查傳播（SP）算法

4.1 基本算法

調(diào)查傳播算法是一種基于統(tǒng)計(jì)的非完備算法。SP算法在因子圖上進(jìn)行信息迭代，根據(jù)迭代信息來確定變量的取值傾向，完成對部分變量的賦值；利用部分變量賦值對原問題進(jìn)行簡化，然后利用局部搜索策略完成對問題的求解。

算法3 SP算法

輸入：CNF公式的因子圖;迭代終止步數(shù)tf;要求的精度ε。

輸出：未收斂或偏置信息。

a） 初始化t=0，對于公式的因子圖上的每一條a→i的邊，隨機(jī)初始化信息ηa→i（t=0）∈［0，1］；

b） while t≤tf

對因子圖上的消息邊進(jìn)行隨機(jī)排序，按照順序更新警告信息，利用SP-UPDATE程序更新ηa→i（t）；

如果在所有的邊上都有|ηa→i（t）－ηa→i（t－1）|lt;ε，那么迭代收斂并且賦值η*a→i=ηa→i（t），退出循環(huán)；

c） if t==tf

返回算法未收斂；

else

返回η*a→i=ηa→i（t）。

算法4 SP-UPDATE

輸入：集合j∈V（a）/i的每個(gè)變量節(jié)點(diǎn)的消息集合。

輸出：更新后的ηa→i。

a） 對j∈V（a）/i計(jì)算下列值：

如果集合Vsa（j）是空集，則將相應(yīng)的乘積賦值為1；

b） 利用a）的計(jì)算結(jié)果計(jì)算新的調(diào)查信息：

如果集合V（a）/i為空集，那么ηa→i=1;

對因子圖上的消息邊進(jìn)行隨機(jī)排序，按照順序更新警告信息，利用SP-UPDATE程序更新ηa→i（t）;

如果在所有的邊上都有|ηa→i（t）－ηa→i（t－1）|lt;ε，那么迭代收斂并且賦值η*a→i=ηa→i（t），退出循環(huán);

c） if t==tf

返回算法未收斂;

else

返回η*a→i=ηa→i（t）。

4.2 收斂性

文獻(xiàn)［62］提出一種利用步長來研究SP算法的時(shí)間耗費(fèi)和有效性，這里的步長是指每次迭代之后根據(jù)賦值傾向確定的賦值個(gè)數(shù)，通過實(shí)驗(yàn)對比可得出，步長增加SP算法的時(shí)間耗費(fèi)先快速遞減，然后逐漸平緩，SP算法的有效性隨著步長增加近似地單調(diào)遞減，但文中未對該現(xiàn)象進(jìn)行理論上的分析。文獻(xiàn)［63］在理論的角度上對SP算法的收斂性進(jìn)行了分析，利用向量空間中壓縮函數(shù)的性質(zhì)，在信息更新方程上取雙曲正切，信息的取值從［0，1］松弛為（-∞，+∞），給出了一個(gè)SP算法收斂的條件。在實(shí)驗(yàn)中利用隨機(jī)3-SAT模型測試了當(dāng)方陣M的譜半徑嚴(yán)格小于1時(shí)，SP算法收斂，且與初始信息無關(guān)。文獻(xiàn)［64］引入K維結(jié)構(gòu)熵對不同規(guī)模SAT實(shí)例進(jìn)行度量，從因子圖的結(jié)構(gòu)角度對SP算法收斂性進(jìn)行分析并給出SP算法收斂的充分條件。

4.3 相關(guān)改進(jìn)及應(yīng)用

SP算法是目前求解隨機(jī)SAT最有效的算法，與智能優(yōu)化算法結(jié)合在問題的求解上非常有效。SP算法求解變量個(gè)數(shù)較小的問題時(shí)，在臨界區(qū)極不易收斂，文獻(xiàn)［65］針對此問題提出了一種結(jié)合蟻群與SP結(jié)合的算法。利用SP算法迭代一次產(chǎn)生的信息作為蟻群算法上每一條邊上的信息素，然后進(jìn)行蟻群算法迭代。在沒有得到更優(yōu)解的情況下，對啟發(fā)因子進(jìn)行更新完成迭代，實(shí)驗(yàn)結(jié)果顯示，在選取接近臨界區(qū)的實(shí)例集中，該算法求解效率和成功率更高，對于一些SP無法求解的實(shí)例也能求到解，大多數(shù)實(shí)例能夠很快地找到解。

文獻(xiàn)［66］對于節(jié)點(diǎn)規(guī)模大的隨機(jī)3-SAT，α在4.252 5和4.266 7的問題求解提出了一種回溯調(diào)查傳播算法（BSP），幾乎能夠在線性時(shí)間內(nèi)、在任何其他算法無法達(dá)到的區(qū)域內(nèi)找到非常接近閾值的解。BSP算法中所有找到的解都不包含凍結(jié)變量，保證在線性時(shí)間內(nèi)只能找到未凍結(jié)的解。調(diào)查傳播強(qiáng)化（SPR）算法中一旦增強(qiáng)字段很大，任何變元的重新分配都變得不可行，而BSP中變元可以被重新分配到更好的值。啟發(fā)式調(diào)查抽?。⊿ID）在困難問題中容易出現(xiàn)在分配一些相鄰變元后才能發(fā)現(xiàn)一個(gè)變元分配了錯(cuò)誤的值，BSP中引入新的回溯步驟，將已配變元重新釋放，變元最終可以在未來抽取步驟中重新分配，過程中不回溯以前的非最優(yōu)選擇。

文獻(xiàn)［67］提出一種SP-Y算法來求解最大可滿足性問題（MAX-SAT），與SP算法相比，在求解MAX-SAT問題上允許子句違反約束。在迭代過程中SP-Y給予一個(gè)回溯概率r，當(dāng)SP-Y算法收斂的情況下，產(chǎn)生一個(gè)隨機(jī)數(shù)q，當(dāng)qgt;r時(shí)，根據(jù)相關(guān)公式固定前k個(gè)偏差最大的變量，否則根據(jù)相關(guān)公式刪除前k個(gè)偏差最大的變量，SP-Y算法能夠在其相變時(shí)解決大型MAX-3-SAT實(shí)例。對于加權(quán)MAX-SAT問題，文獻(xiàn)［68］提出一種松弛調(diào)查傳播算法（RSP），與SP-Y相比，RSP在每個(gè)因子向變量傳遞信息的時(shí)候給予一個(gè)懲罰值，同時(shí)違反子句的變量一定會被傳遞信息，并且當(dāng)RSP收斂時(shí)，Y值越大性能越好。通過測試隨機(jī)MAX-3-SAT和隨機(jī)加權(quán)MAX-3-SAT實(shí)驗(yàn)顯示，當(dāng)子句變量比α≥4.7，RSP相比于SP-Y，違反的子句數(shù)目更少。對于限定子句長度的MAX-E-3-SAT問題，文獻(xiàn)［69］提出一種結(jié)合深度學(xué)習(xí)方法的新算法DeepSP求解MAX-E-3-SAT問題的近似解，算法中將SP方法中計(jì)算出的不動(dòng)點(diǎn)信息提供給神經(jīng)網(wǎng)絡(luò)，利用監(jiān)督學(xué)習(xí)的方法對隨機(jī)3SAT實(shí)例上獲得的目標(biāo)值使用調(diào)查啟發(fā)式抽取進(jìn)行優(yōu)化并輸出結(jié)果。同時(shí)也證明了在SP算法的非數(shù)值不穩(wěn)定區(qū)域DeepSP算法可以找到優(yōu)于隨機(jī)分配閾值的近似解，算法求解極限的子句密度為4.67。雖然其性能仍不能與最先進(jìn)的MAX-SAT求解器相比，但與深度學(xué)習(xí)結(jié)合求解研究較少，未來值得深入研究。

文獻(xiàn)［70］利用SP算法作為DPLL算法的啟發(fā)式引導(dǎo)，根據(jù)SP算法迭代過程中產(chǎn)生的調(diào)查信息進(jìn)行解的分支選擇。在求解過程中記錄沖突分支并進(jìn)行剪枝，同時(shí)根據(jù)記錄滿足的分支，遇到后不再進(jìn)行搜索，減小搜索空間。通過實(shí)驗(yàn)對比發(fā)現(xiàn)與原DPLL算法相比，在分支選擇技術(shù)和沖突學(xué)習(xí)等分支處理方法上效率提高顯著;同時(shí)在此算法的基礎(chǔ)上設(shè)計(jì)了一種QBF（quantified boolean formulae）求解器，有效地提高了QBF問題的求解效率。

SP算法的相關(guān)應(yīng)用改進(jìn)對比如表3所示。

5 未來的研究方向

隨著對求解可滿足性問題的信息傳播算法深入研究，信息傳播算法在收斂時(shí)十分有效，但仍存在許多值得深入研究的問題，主要有以下幾點(diǎn)：

a）信息傳播算法在因子圖結(jié)構(gòu)相對簡單的情況下，算法收斂保證了其有效性，但隨著可滿足性問題實(shí)例子句的個(gè)數(shù)增加，其因子圖結(jié)構(gòu)變得復(fù)雜，算法往往不收斂。因此，未來對信息傳播算法收斂性還需要深入研究。

b）目前信息傳播算法與智能優(yōu)化算法、深度神經(jīng)網(wǎng)絡(luò)等相結(jié)合求解相關(guān)問題十分有效，利用信息傳播算法對難解問題求解有效的特征，結(jié)合相關(guān)領(lǐng)域算法用于問題求解引起了越來越多的關(guān)注。例如，文獻(xiàn)［71］結(jié)合BP算法與模擬退火算法求解TSP，利用模擬退火有效防止局部最優(yōu)和全局搜索的特性，對BP算法求解的結(jié)構(gòu)進(jìn)行優(yōu)化，效果十分顯著。文獻(xiàn)［72］在BP譯碼算法添加殘差神經(jīng)網(wǎng)絡(luò)對接收信號處理，譯碼效果明顯增強(qiáng)。與其他算法策略的結(jié)合改進(jìn)顯著提高了信息傳播算法在相關(guān)問題上的求解性能。因此，將信息傳播算法與其他算法相結(jié)合是一個(gè)重要的研究內(nèi)容。

c）信息傳播算法的收斂性與命題公式的結(jié)構(gòu)具有密切關(guān)系，命題公式的結(jié)構(gòu)特征決定了信息傳播算法的性能。目前已有從骨干集、結(jié)構(gòu)熵角度研究其結(jié)構(gòu)特征的成果，但未來仍需要從不同的角度深入研究命題公式的結(jié)構(gòu)特征，探索結(jié)構(gòu)特征與算法性能之間的聯(lián)系。

d）對于限定命題變元次數(shù)與子句長度的正則（d，k）-SAT問題，雖然基于一階矩和二階矩方法給出一些相變的研究成果，但二階矩方法應(yīng)用過程中的復(fù)雜性導(dǎo)致了大量開放問題，未獲得嚴(yán)格的相變點(diǎn)。正則（d，k）-SAT問題對應(yīng)的因子圖具有正則二部圖的特點(diǎn)，可以從正則二部圖中具有的一些特殊條件性質(zhì)研究相變點(diǎn)，進(jìn)而優(yōu)化信息傳播算法。

e）對于SAT問題的優(yōu)化問題MAX-SAT以及多文字SAT問題，信息傳播算法的性能并不優(yōu)越。因此，設(shè)計(jì)求解優(yōu)化問題的信息傳播算法是未來研究的熱點(diǎn)。

f）三種信息傳播算法性能與可滿足性問題相變現(xiàn)象關(guān)系緊密，目前對相變現(xiàn)象研究已經(jīng)進(jìn)入了深水區(qū)，研究越來越困難。未來對相變現(xiàn)象的繼續(xù)深入研究、對信息傳播算法性能的分析十分重要。

6 結(jié)束語

SAT問題是著名的NP-完全問題，人工智能領(lǐng)域中許多問題通過編碼轉(zhuǎn)換為SAT問題。近年來，信息傳播算法被應(yīng)用于人工智能研究，在SAT問題求解上十分有效，受到研究人員的廣泛關(guān)注。本文對三種求解可滿足性問題的信息傳播算法進(jìn)行了概述，并對算法應(yīng)用及改進(jìn)進(jìn)行了總結(jié)。最后對求解可滿足性問題的信息傳播算法未來的研究方向進(jìn)行了展望，可以從收斂性、命題公式結(jié)構(gòu)等方向不斷地進(jìn)行創(chuàng)新。

參考文獻(xiàn)：

[1]Russel S， Norvig P. Artificial intelligence： a modern approach［M］.Upper Saddle River，NJ： Prentice-Hall Inc.，2013.

［2]Gunduz M， Aslan M. DJAYA： a discrete Jaya algorithm for solving traveling salesman problem［J］.Applied Soft Computing，2021，105（7）：107275.

［3]Aiello A， Burattini E， Massarotti A. The complexity of theorem proving procedures［J］.Rairo Informat Théor，1977，11（1）：75-82.

［4]Park S， Shin J. Convergence and correctness of max-product belief propagation for linear programming［J］.SIAM Journal on Discrete Mathematics，2017，31（3）：2228-2246.

［5]Braunstein A， Mezard M， Zecchina R. Survey propagation： an algorithm for satisfiability［J］.Random Structures amp; Algorithms，2005，27（2）：201-226.

［6]Kschischang F R， Frey B J， Loeliger H A. Factor graphs and the sum-product algorithm［J］.IEEE Trans on Information Theory，2001，47（2）：498-519.

［7]M′ezard M， Montanari A. Information， physics and computation［M］.New York：Oxford University Press，2009.

［8]王曉峰，許道云.警示傳播算法收斂的充分條件［J］.軟件學(xué)報(bào)，2016，27（12）：3003-3013.（Wang Xiaofeng， Xu Daoyun. Sufficient conditions for convergence of the warning propagation algorithm［J］.Journal of Software，2016，27（12）：3003-3013.）

［9]Friedgut E， Bourgain J. Sharp thresholds of graph proprties， and the K-SAT problem［J］.Journal of the American Mathematical Society，1999，12（4）：1017-1054.

［10]Mézard M， Parisi G， Zecchina R. Analytic and algorithmic solution of random satisfiability problems［J］.Science，2002，297（5582）：812-815.

［11]Mézard M. Passing messages between disciplines［J］.Science，2003，301（5640）：1685-1686.

［12]Kaporis A C， Kirousis L M， Lalas E G. The probabilistic analysis of a greedy satisfiability algorithm［J］.Random Structures amp; Algorithms，2006，28（4）：444-480.

［13]Díaz J， Kirousis L M， Mitsche D， et al. On the satisfiability thre-shold of formulas with three literals per clause［J］.Theoretical Computer Science，2009，410（30-32）：2920-2934.

［14]Maneva E， Mossel E， Wainwright M J. A new look at survey propagation and its generalizations［J］.Journal of the ACM，2007，54（4）：article No.17.

［15]Yedidia J S， Freeman W T， Weiss Y. Understanding belief propagation and its generalizations［C］//Proc of Exploring Artificial Intelligence in the New Millennium. San Fransciso，CA：Morgan Kaufmann Publishers Inc.，2003：239-269.

［16]Braunstein A， Zecchina R. Survey and belief propagation on random K-SAT［C］//Proc of the 6th International Conference on Theory and Applications of Satisfiability Testing.Berlin：Springer，2003：519-528.

［17]王曉峰，許道云，韋立.隨機(jī)可滿足實(shí)例集上警示傳播算法的收斂性［J］.軟件學(xué)報(bào)，2013，24（1）：1-11.（Wang Xiaofeng， Xu Daoyun， Wei Li. Convergence of warning propagation algorithms for random satisfiable instances［J］.Journal of Software，2013，24（1）：1-11.）

［18]Feige U， Mossel E， Vilenchik D. Complete convergence of message passing algorithms for some satisfiability problems［J］.Theory of Computing，2013，9（1）：617-651.

［19]牛進(jìn)，王曉峰，林青文.基于結(jié)構(gòu)熵的警示傳播算法收斂性分析［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（3）：760-763，776.（Niu Jin， Wang Xiaofeng， Lin Qinwen. Convergence analysis of warning propagation algorithm based on structural entropy［J］.Application Research of Computers，2021，38（3）：760-763，776.）

［20]王曉峰，李強(qiáng)，丁紅勝.規(guī)則實(shí)例集上警示傳播算法的收斂性［J］.計(jì)算機(jī)科學(xué)，2015，42（1）：279-284.（Wang Xiaofeng， Li Qiang， Ding Hongsheng. Convergence of warning propagation algorithm for regular structure instances［J］.Computer Science，2015，42（1）：279-284.）

［21]崔立，王曉峰，牛進(jìn).WP可解公式上警示傳播算法收斂的有效條件［J］.計(jì)算機(jī)應(yīng)用研究，2020，37（5）：1406-1410.（Cui Li， Wang Xiangfeng， Niu Jin. Effective conditions for warning propagation algorithm convergence on WP solvable formula［J］.Application Research of Computers，2020，37（5）：1406-1410.）

［22]王辛，王曉峰，許道云，等.一種求解雙目標(biāo)最小生成樹的警示傳播算法［J］.中國科學(xué)：信息科學(xué)，2020，50（10）：1501-1510.（Wang Xin， Wang Xiaofeng， Xu Daoyun， et al. A warning propagation algorithm to solve the double-objective minimum spanning tree［J］.Science in China：Information Sciences，2020，50（10）：1501-1510.）

［23]王辛，王曉峰，李衛(wèi)民.一種求解最小割的警示傳播算法［J］.電子學(xué)報(bào)，2019，47（11）：2386-2391.（Wang Xin， Wang Xiaofeng， Li Weimin. A warning propagation algorithm for solving minimum cut［J］.Acta Electronica Sinica，2019，47（11）：2386-2391.）

［24]王曉峰，許道云，秦永彬.求解公式關(guān)鍵文字集的信息傳播算法［J］.山東大學(xué)學(xué)報(bào)：工學(xué)版，2011，41（3）：1-6.（Wang Xiaofeng， Xu Daoyun， Qin Yongbin. A message propagation algorithm computing set of key literals of a formula［J］.Journal of Shandong University：Engineering Science，2011，41（3）：1-6.）

［25]秦永彬，許道云.警示傳播算法的原理分析及算法改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（19）：1-6，54.（Qin Yongbin， Xu Daoyun. Analysis and improvement of warning propagation algorithm［J］.Computer Engineering amp; Applications，2010，46（19）：1-6，54.）

［26]佘光偉，許道云.用于求解正則（3，4）-SAT實(shí)例集的修正警示傳播算法［J］.計(jì)算機(jī)科學(xué)，2018，45（11）：312-317.（She Guangwei， Xu Daoyun. Modified warning propagation algorithm for solving regular（3，4）-SAT instance sets［J］.Computer Science，2018，45（11）：312-317.）

［27]秦永彬，許道云，王曉峰.基于警示傳播與DPLL算法的啟發(fā)式極性決策算法［J］.計(jì)算機(jī)科學(xué)，2010，37（12）：178-181，185.（Qin Yongbin， Xu Daoyun， Wang Xiaofeng. Heuristic polarity decision making algorithm based on warning propagation and DPLL algorithm［J］.Computer Science， 2010，37（12）：178-181，185.）

［28]Wang Xiaofeng， Jiang Jiulei. Warning propagation algorithm for the MAX-3-SAT problem［J］.IEEE Trans on Emerging Topics in Computing，2017，7（4）：578-584.

［29]Alexander E， Anna R， Achim T， et al. Efficient maximum likelihood estimation for pedigree data with the sum-product algorithm［J］.Human Heredity，2016，82（1-2）：1-15.

［30]Garey M R， Johnson D S. Computers and Intractability：a guide to the theory of NP-completeness［M］.New York：W.H.Freeman amp; Co.，1990.

［31]Weigt M， Zhou Haijun. Message passing for vertex covers［J］.Physical Review E，2006，74（4）：046110.

［32]Xu Hong， Sun Kexuan， Koenig S， et al. A warning propagation-based linear-time-and-space algorithm for the minimum vertex cover problem on giant graphs［C］//Proc of International Conference on the Integration of Constraint Programming， Artificial Intelligence， and Operations Research. Cham： Springer， 2018： 567-584.

［33]Engelhardt A， Rieger A， Tresch A， et al. Efficient maximum likelihood estimation for pedigree data with the sum-product algorithm［J］.Human Heredity，2016，82（1-2）：1-15.

［34]Weiss Y， Freeman W T. On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs［J］.IEEE Trans on Information Theory，2001，47（2）：736-744.

［35]Colavolpe G， Germi G. On the application of factor graphs and the sum-product algorithm to ISI channels［J］.IEEE Trans on Communications，2005，53（5）：818-825.

［36]Weiss Y. Correctness of local probability propagation in graphical models with loops［J］.Neural Computation，2000，12（1）：1-41.

［37]王曉峰，許道云，楊德仁，等.可滿足性問題中信念傳播算法的收斂性分析［J］.軟件學(xué)報(bào)，2021，32（5）：1360-1372.（Wang Xiao-feng， Xu Daoyun， Yang Deren， et al. Convergence analysis of belief propagation algorithm for satisfiability problem［J］.Journal of Software，2021，32（5）：1360-1372.）

［38]Du Jian， Ma Shaodan， Wu Y C， et al. Convergence analysis of distributed inference with vector-valued Gaussian belief propagation［J］.Journal of Machine Learning Research，2017，18（1）：6302-6339.

［39]Zhang Zhaorong， Fu Minyue. Convergence rate analysis of Gaussian belief propagation for Markov networks［J］.IEEE/CAA Journal of Automatica Sinica，2020，7（3）：668-673.

［40]牛進(jìn)，王曉峰，左逢源，等.基于二維結(jié)構(gòu)熵的置信傳播算法收斂性分析［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（7）：2032-2036，2043.（Niu Jin， Wang Xiaofeng， Zuo Fengyuan， et al. Convergence analysis of belief propagation algorithm based on two-dimensional structural entropy［J］.Application Research of Computers，2021，38（7）：2032-2036，2043.）

［41]Bavarian S， Cavers J K. Reduced complexity belief propagation algorithm based on iterative groupwise multiuser detection［C］//Proc of Canadian Conference on Electrical and Computer Engineering.Pisca-taway，NJ：IEEE Press，2007：466-468.

［42]Li Tao， Ji Xiangyang， Dai Qionghai. Depth map recovery for multi-view using belief propagation［C］//Proc of 3DTV Conference： the True Vision-Capture，Transmission and Display of 3D Video.Pisca-taway，NJ：IEEE Press，2009.

［43]Zhan Tianming， Xu Yang， Sun Le， et al. Hyperspectral image classification using multilayer superpixel graph and loopy belief propagation［C］//Proc of IEEE International Geoscience and Remote Sensing Symposium.Piscataway，NJ：IEEE Press，2015：1690-1693.

［44]Fan Xiang， Shi Zhiping. Loopy belief propagation algorithm in distributed wireless cooperative spectrum sensing［C］//Proc of the 3rd International Conference on Communications and Mobile Computing.Washington DC：IEEE Computer Society，2011：282-285.

［45]Jiang J， Narayanan K R. Iterative soft-input soft-output decoding of Reed-Solomon codes by adapting the parity-check matrix［J］.IEEE Trans on Information Theory，2006，52（8）：3746-3756.

［46]Yang Yushan， Jiang Ming， Wu Xiaofu. An investigation in iterative decoding of Reed-Solomon codes based on adaptive belief propagation［C］//Proc of International Conference on Wireless Communications amp; Signal Processing.Piscataway，NJ：IEEE Press，2009：1-5.

［47]孫怡寧，黃秋，胡劍浩.Reed-Solomon碼概率軟譯碼算法增強(qiáng)技術(shù)［J］.中國科學(xué)：信息科學(xué)，2021，51（8）：1331-1344.（Sun Yining， Huang Qiu， Hu Jianhao. Enhanced stochastic soft decoding algorithm for Reed-Solomon codes［J］.Science in China： Information Sciences，2021，51（8）：1331-1344.

［48]Koetter R， Vardy A. Algebraic soft-decision decoding of Reed-Solomon codes［J］.IEEE Trans on Information Theory，2003，49（11）：2809-2825.

［49]Jego C， Gross W J. Turbo decoding of product codes based on the modified adaptive belief propagation algorithm［C］//Proc of IEEE International Symposium on Information Theory.Piscataway，NJ：IEEE Press，2007：641-644.

［50]Sheikh A， Amat A G， Liva G. Binary message passing decoding of product codes based on generalized minimum distance decoding［C］//Proc of the 53rd Annual Conference on Information Sciences and Systems.Piscataway，NJ：IEEE Press，2019：1-5.

［51]Lu Fang， Dong Yan， Rao Wengui. A parallel belief propagation decoding algorithm for rate compatible modulation［J］.IEEE Communications Letters，2017，21（8）：1735-1738.

［52]Cui Hao， Luo Chong， Wu Jun， et al. Compressive coded modulation for seamless rate adaptation［J］.IEEE Trans on Wireless Communications，2013，12（10）：4892-4904.

［53]Cui Hao， Luo Chong， Kun Tan， et al. Seamless rate adaptation for wireless networking［C］//Proc of the 14th ACM International Confe-rence on Modeling， Analysis and Simulation of Wireless and Mobile Systems.New York：ACM Press，2011：437-446.

［54]Rao Wengui， Dong Yan， Lu Fang， et al. Log-likelihood ratio algorithm for rate compatible modulation［C］//Proc of IEEE International Symposium on Circuits and Systems.Piscataway，NJ：IEEE Press，2013：1938-1941.

［55]Wang Min， Wu Jun， Shi Saifeng， et al. Fast decoding and hardware design for binary-input compressive sensing［J］.IEEE Journal on Emerging and Selected Topics in Circuits and Systems，2012，2（3）：591-603.

［56]Srivastava S， Ha S J， Lee S H， et al. Stereo matching using hierarchical belief propagation along ambiguity gradient［C］//Proc of the 16th IEEE International Conference on Image Processing.Piscataway，NJ：IEEE Press，2009：2061-2064.

［57]Yang Tianyu， He Qing， Wei Ning， et al. A new stereo matching method with combination of cross-based aggregation and hierarchical belief propagation［C］//Proc of IEEE International Conference on Information and Automation.Piscataway，NJ：IEEE Press，2012：379-383.

［58]Zhang Ke， Lu Jiangbo， Lafruit G. Cross-based local stereo matching using orthogonal integral images［J］.IEEE Trans on Circuits and Systems for Video Technology，2009，19（7）：1073-1079.

［59]左逢源，王曉峰，任雪嬌，等.求解網(wǎng)絡(luò)最大流問題的信念傳播算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2021，42（5）：1346-1352.（Zuo Fengyuan， Wang Xiaofeng， Ren Xuejiao， et al. Belief algorithm propagation for net work maximum flow problem［J］.Computer Engineering and Design，2021，42（5）：1345-1352.）

［60]左逢源，王曉峰，牛進(jìn)，等.求解最小費(fèi)用最大流問題的信念傳播算法［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（7）：1998-2002，2024.（Zuo Fengyuan， Wang Xiaofeng， Niu Jin， et al. Belief propagation algorithm for solving minimum cost maximum flow problem［J］.Application Research of Computers，2021，38（7）：1998-2002，2024.）

［61]Ding Jie， Wen Changyun， Li Guoqi， et al. Target controllability in multilayer networks via minimum-cost maximum-flow method［J］.IEEE Trans on Neural Networks and Learning Systems，2020，32（5）：1949-1962.

［62]邵明，李光輝，李曉維.求解可滿足問題的調(diào)查傳播算法以及步長的影響規(guī)律［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28（5）：849-855.（Shao Ming， Li Guanghui， Li Xiaowei. Survey propagation algorithm for SAT and its performance dominated by step length［J］.Chinese Journal of Computers，2005，28（5）：849-855.）

［63]王曉峰，許道云，姜久雷，等.調(diào)查傳播算法收斂的一個(gè)充分條件［J］.中國科學(xué)：信息科學(xué)，2017，47（12）：1646-1661.（Wang Xiao-feng， Xu Daoyun， Jiang Jiulei， et al. Sufficient conditions for convergence of the survey propagation algorithm［J］.Science in China： Information Sciences，2017，47（12）：1646-1661.）

［64]梁晨，王曉峰，劉子琳，等.基于K維結(jié)構(gòu)熵的調(diào)查傳播算法收斂性分析［J］.計(jì)算機(jī)應(yīng)用研究，2022，39（5）：1432-1436.（Liang Chen， Wang Xiaofeng， Liu Zilin， et al. Convergence analysis of survey propagation algorithm based on K-dimensional structure entropy［J］.Application Research of Computers，2022，39（5）：1432-1436.）

［65]王芙，周育人，葉立.調(diào)查傳播算法和蟻群算法相結(jié)合求解可滿足性問題［J］.計(jì)算機(jī)科學(xué)，2012，39（4）：227-231.（Wang Fu， Zhou Yunren， Ye Li. Ant colony algorithm combined with survey propagation for satisfiability problem［J］.Computer Science，2012，39（4）：227-231.）

［66]Marino R， Parisi G， Ricci-Tersenghi F. The backtracking survey propagation algorithm for solving random K-SAT problems［J］.Nature Communications，2016，7（1）：article No.12996.

［67]Battaglia D， Kolárˇ M， Zecchina R. Minimizing energy below the glass thresholds［J］.Physical Review E，2004，70（3）：036107.

［68]Chieu H L， Lee W S. Relaxed survey propagation for the weighted maximum satisfiability problem［J］.Journal of Artificial Intelligence Research，2009，36（1）：229-266.

［69]Marino R. Learning from survey propagation： a neural network for MAX-E-3-SAT［J］.Machine Learning： Science and Techno-logy，2021，2（3）：035032.

［70]殷明浩，周俊萍，孫吉貴，等.求解QBF問題的啟發(fā)式調(diào)查傳播算法［J］.軟件學(xué)報(bào)，2011，22（7）：1538-1550.（Yin Minghao， Zhou Junping， Sun Jigui， et al. Heuristic survey propagation algorithm for solving QBF problem［J］.Journal of Software，2011，22（7）：1538-1550.）

［71]程亞南，王曉峰，劉凇佐，等.一種求解旅行商問題的信息傳播算法［J/OL］.鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2022，54（3）：52-58.（Cheng Yanan， Wang Xiaofeng， Liu Songzuo， et al. An information propagation algorithm for solving traveling salesman problem［J］.Journal of Zhengzhou University： Natural Science Edition，2022，54（3）：52-58.）

［72]王華華，徐勇軍，秦紅，等.殘差擾動(dòng)網(wǎng)絡(luò)輔助的BP譯碼算法［J/OL］.電訊技術(shù).［2022-01-21］.http：//kns.cnki.net/kcms/detail/51.1267.TN.20211230.1813.010.html.（Wang Huahua， Xu Yongjun， Qin Hong， et al. BP decoding algorithm aided by residual perturbation network［J/OL］.Telecommunication Engineering.［2022-01-21］.http：//kns.cnki.net/kcms/detail/51.1267.TN.20211230.1813.010.html.）