一種改進的警示傳播算法求解Max-SAT問題

摘要：Max-SAT問題是SAT問題的優化版本，目標是在給定的子句集中找到一組變元賦值，使得滿足子句數最多，該問題是典型的NP-hard問題。隨著大數據和人工智能的深度發展，過去原有的算法已不再適用，設計新的求解算法或對已有的求解算法進行優化是目前研究的熱點。針對警示傳播算法求解隨機Max-3-SAT問題的局限性，提出了一種基于變元權值計算的警示傳播算法，結合隨機游走算法，給出一種新型算法WWP+WalkSAT，通過改進求解的局限性，更好地得到一組有效的初始解，從而提高算法的局部搜索能力。利用2016年Max-SAT國際競賽部分基準實例，將WWP+WalkSAT算法與八種局部搜索算法進行精度方面的對比實驗。實驗結果表明，WWP+WalkSAT算法有較好的性能。

關鍵詞：可滿足性問題；最大可滿足性問題；警示傳播算法；局部搜索算法

中圖分類號：TP301文獻標志碼：A

文章編號：1001-3695（2022）08-008-2290-05

doi：10.19734/j.issn.1001-3695.2022.01.0023

Improved warning propagation algorithm for solving Max-SAT problem

Wu Yuxianga，Wang Xiaofenga，b，Ding Hongshenga，Yu Zhuoa

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

Abstract：The Max-SAT problem is an optimized version of the SAT problem.The goal is to find a set of variable assignments in a given set of clauses so that the maximum number of clauses is satisfied.This problem is a typical NP-hard problem.With the in-depth development of big data and artificial intelligence，the original algorithms in the past are no longer applicable.Designing a new solution algorithm or optimizing the existing solution algorithm is the current research hotspot.Aiming at the limitations of the information dissemination algorithm for solving the random Max-3-SAT problem，this paper proposed a warning dissemination algorithm based on the calculation of variable weights.Combined with the random walk algorithm，it formed a new algorithm WWP+WalkSAT，which was solved by improvement of the limitation，it was better to get a set of effective initial solutions，thereby improving the local search ability of the algorithm.Using some benchmark examples of the Max-SAT international competition in 2016，it used the WWP+WalkSAT algorithm and 8 local search algorithms for accuracy comparison experiments.The experimental results show that the WWP+WalkSAT algorithm has good performance.

Key words：satisfiability problem；Max-SAT problem；warning propagation algorithm；local search algorithm

0引言

組合優化問題在運籌學、離散數學和計算機科學中都有著非常重要的作用，并在國防、交通、醫療、通信等領域有著廣泛的應用，其中常見的組合優化問題包括背包問題（knapsack）、旅行商問題（travelling salesman problem，TSP）、車輛路徑規劃問題（vehicle routing problem，VRP）、最大團問題（maximum clique problem，MCP）、最小頂點覆蓋問題（minimum vertex co-ver，MVC）、最大可滿足性問題（maximum satisfiability，Max-SAT）[1～6]等。而最大可滿足性問題是一個典型的NP難問題，是可滿足性問題（satisfiability，SAT）[7]的優化版本。給定一個命題合取范式（CNF）， CNF是由一組子句合取構成，每一個子句由一組變元析取構成，Max-SAT問題是尋找一組賦值使得滿足子句數目最多。Max-SAT在組合拍賣、車輛調度、排課安排等現實問題中有著廣泛的應用，同時圖論中的最大團問題和頂點支配集也可以轉換成Max-SAT問題進行求解。

為了解決Max-SAT問題，研究人員提出許多有效算法，主要分為完備性算法和非完備性算法兩種。完備性算法是可以找到問題的精確解，但在求解大規模問題時，由于其復雜度是指數級，很難在合理時間找到結果。近年來，人們主要在分支策略、推理規則、下界估計[8～10]三方面進行改進，進而出現了許多有效的算法，具有代表性的有WmaxSatz[11]、MiniMaxSat[12]等。相對于完備算法而言，非完備性算法則是能短時間內找到大規模問題的最優解，從而提高了求解效率，但缺點是不能保證解的準確性。主流的非完備性算法是近似算法、信息傳播算法、局部搜索算法[13～15]。

信息傳播算法是一種啟發式信息傳遞算法，起源于統計物理學，該類算法通過邊緣概率計算的方法，已應用在許多領域。特別是對于命題公式的可滿足性問題，有三種基于因子圖的信息傳播算法，即警示傳播算法（warning propagation，WP）、信念傳播算法（belief propagation，BP）和調查傳播算法（survey propagation，SP）。目前，在求解隨機SAT問題上信息傳播算法是最為有效的方法，并且在圖著色、最大流、LDPC編碼等許多組合優化問題中取得了不錯的成果。

然而，信息傳播算法的收斂性和有效性一直是研究的重點。收斂性是指信息傳播算法兩次的信息迭代值不發生變化；有效性是指信息傳播算法能夠有效地求解問題。文獻[16～18]分析了信息傳播算法的收斂性和有效性，并給出了算法收斂的充分條件。文獻[19]則是基于具體的實例產生模型分析了信息傳播算法的收斂性，并給出了算法收斂的概率條件。

進一步研究發現，在隨機3-SAT問題中，子句個數m和變元個數n的比值稱約束密度α，即α=m/n，它不僅對公式的可滿足性產生影響，還對可滿足性公式的求解難易程度有著非常重要的影響。隨著約束密度α的增大，當3.52lt;αlt;4.48時，會發生相變。在相變范圍以外的可滿足性實例均為易解實例，高概率是可滿足的；在相變點附近的實例屬于難解實例，高概率是不可滿足的。雖然信息傳播算法對于求解難解實例十分有效，但在求解相變點以外的易解實例方面，信息傳播算法不能收斂。

針對此問題，文本設計了一種新型變元權值計算的警示傳播算法WWP+WalkSAT，通過變元權值計算對警示傳播算法進行改進，可以得到一組有效的初始解，再結合隨機游走算法進行局部搜索。對該算法的性能表現進行實驗分析，在相變點附近實例和相變點以外實例均與其余局部搜索算法進行實驗對比。

1基礎知識

最大可滿足性問題是指：給定一組命題變元xi∈X，由這些變元形成一組子句，構成CNF公式，使得CNF公式中滿足子句的個數最多，即，使得不滿足的子句個數最少。Max-SAT問題的數學模型如式（1）（2）所示。

maximize：∑a∈Fwa·za（1）

subject to：a∈F：∑i∈S+axi+∑i∈S-a（1-xi）≥zaza∈{0，1}，xi∈{0，1}（2）

文字的集合（literal） X={x1，x2，x3，…，xn}：每一個布爾變元xi∈X，變元xi取正時表示正文字；變元xi取反時表示負文字。

子句的集合（clause）C={C1，C2，C3，…，Cm}：對m個不同的子句形成一個子句集合，每一個子句由一個或多個文字組成，子句與子句之間通過析取運算連接，且僅當子句中至少有一個文字為1時，該子句滿足，反之子句不滿足。每一個子句中文字的個數叫做這個子句的長度。當子句中只有一個文字出現時，稱該子句為單子句。

合取范式（CNF公式）：由若干個子句合取構成，即C1∧C2∧C3∧…∧Cm ，當且僅當CNF公式的每一個子句都滿足時，稱合取范式CNF可滿足。

因子圖（factor graph）：因子圖也稱二部圖，圖中包含兩類節點，一類是變元節點（圖中用圓環表示，記做（1，2，3，4；…）），另一類是函數節點（圖中用方框表示，記做（a，b，c；…））。給定一個CNF公式F={C1，C2，C3，…，Cm}，公式中由x1，x2，x3，…，xn個變元構成，其中所有變元對應的是變元節點，變元析取構成的子句對應的是函數節點。圖中出現的虛邊和實邊代表著CNF公式的兩種不同的含義：實邊，子句中代表正文字xj；虛邊，子句中代表負文字xj。

例1F={（x1∨x2∨x3）∧（x1∨x2∨x4）∧（x1∨x3∨x5）∧（x3∨x4∨x5）}={a∧b∧c∧d}其對應的因子圖如圖1所示。

V（a）=V+（a）+V-（a）表示子句a中出現的變元集合V（a）=V+（a）+V-（a）。其中：V+（a）表示子句a中變元為正的集合；V-（a）表示子句a中變元為負的集合；V（a）＼i表示子句a中除變元i以外其余變元的集合；在圖1中，V（a）={x1，x2，x3}，V+（a）={x1}，V-（a）={x2，x3}。

V（j）表示含有變元xj的子句集合V（j）=V+（j）+V-（j）。其中：V+（j）表示變元xj為正的子句集合；V-（j）表示變元xj為負的子句集合；V（j）＼a表示除了子句a以外，其余含有變元xj的子句集合。在圖1中，V（1）={a，b，c}，V+（1）={a}，V-（1）={b，c}。

JaJ表示對于子句a中的變元xj的標識符，變元在子句中的取值表示為

Jaj=-1xj∈a

1xj∈a（3）

定義兩個一致性集合Vua（j）和Vsa（j）。Vua（j）表示除子句a以外，含有變元xj且變元xj的取值方向與其子句a中取值不一致的子句集；Vsa（j）表示除子句a以外，含有變元xj且變元xj的取值方向與其子句a中取值一致的子句集。集合Vua（j）和Vsa（j）如圖2所示。

2基于變元權值計算的警示傳播算法

基于變元權值計算的警示傳播算法WWP+WalkSAT是在警示傳播算法[20]上進行改進，文獻[16]分析警示傳播算法的收斂性，通過引入參數將算法中的信息取值從{0，1}松弛為[0，1]，利用向量空間中壓縮函數的性質，給出警示傳播算法收斂的一個充分條件，并為警示傳播算法性能提供了理論依據。WWP+WalkSAT是在此理論基礎上引入了變元權值計算[21]，從中得到一組有效的初始解，其目的是選出權值最高的文字，使得滿足子句個數最多，從而減少無效的子句傳播，加快搜索過程。原本的警示傳播算法在求解難解實例十分有效，但對于易解實例會出現不收斂現象。對于此問題，該算法在迭代次數結束時，計算局部警示信息變化最小時的警示值，再進行變元權值計算。最后對其初始解采用隨機游走的局部搜索算法，可得到更優解，從而提高其算法性能。WWP+WalkSAT打破了原先警示傳播算法求解Max-SAT問題的局限性，可用于求解任何區域的實例，同時在求解精度上也有所提高。

2.1警示傳播算法（warning propagation）

通過信息傳遞而設計的信息傳播算法，對于求解可滿足性問題具有良好的有效性，警示傳播算法是一個迭代運算的算法，在每一次迭代過程中，對于因子圖的每條邊（a，i），都會獲得一個警示信息，表示在因子圖中一個函數節點a傳遞給變元i一個布爾信息，記做ua→i∈{0，1}。ua→i的迭代方程如式（4）所示。

ua→i（t+1）=∏j∈V（a）＼iθ（-Jaj（∑b∈V（j）＼aJajub→j（t）））（4）

其中：t是迭代次數；θ（x）是一個截尾函數，定義為θ（x）=1xgt;0

-1x≤0。由此公式可以說明，當ua→i=1表示對于子句a的滿足性由變元xi來決定；當ua→i=0表示子句a的滿足性不能完全由變元xi決定，即子句a的滿足性由其余變元的取值來決定。

對于每一個變元xi，需要計算一個局部腔域Hi和一個沖突域ci∈{0，1}，其中局部腔域和沖突域如式（5）（6）所示。

Hi=-∑b∈V（i）Jbiub→i=∑b∈V+（i）ub→i-∑b∈V-（i）ub→i（5）

ci=1if （∑b∈V+（i）ub→i）（∑b∈V-（i）ub→i）gt;0

0otherwise（6）

當沖突域ci=1時，即（∑b∈V+（i）ub→i）（∑b∈V-（i）ub→i）gt;0，則表示對于變元xi，受到了兩個子句的約束，變元xi在兩個子句中的取值不一致，因此變元xi的取值發生了沖突。如子句a告訴變元xi取1，子句b告訴變元xi取0。當沖突域ci=0時，即（∑b∈V+（i）ub→i）（∑b∈V-（i）ub→i）=0，則表示對于變元xi的取值沒有沖突發生，變元xi的具體取值可以通過局部腔域來決定，如式（7）所示。

xi=1∑b∈V+（i）ub→igt;0，∑b∈V-（i）ub→i=0

{0，1}∑b∈V+（i）ub→i=∑b∈V-（i）ub→i=0

0∑b∈V+（i）ub→i=0，∑b∈V-（i）ub→igt;0 （7）

如果Higt;0，變元xi=1；如果Hilt;0，變元xi=0；否則變元xi暫時不賦值。

算法1警示傳播算法（WP）

輸入：CNF因子圖G；最大迭代次數tmax；精度ε。

輸出：未收斂或收斂，輸出警示信息值u*a→i。

begin

當t=0時，對于因子圖的每個邊（a，i），以1/2的概率隨機初始化警示信息ua→i（0）→{0，1} //隨機初始化

for t=1 to tmax

通過字典的順序，對圖中每一條邊（a，i）∈E進行遍歷，采用警示更新算法UPDATE-WP對ua→i進行更新，即ua→i（t-1）→ua→i（t）

當圖中所有的邊（a，i）∈E，若∑（a，i）∈E|ua→i（t）-ua→i（t-1）|lt;ε，說明已收斂，ua→i（t）=ua→i（t-1），停止循環，返回u*a→i （t）

if t=tmax

尋找t*=arg mint∑（a，i）∈E|ua→i（t）-ua→i（t-1）|

返回：未收斂，并將u*a→i （t） = ua→i （t*）， /*把t*時刻的信息值保留并賦值給警示值*/

算法2警示信息值更新算法（UPDATE-WP）

輸入：警示信息值集合{ub→j：b∈V（j）＼a}，對所有的j∈V（a）＼i。

輸出：新的ua→i。

begin

ifV（a）＼i=，則返回ua→i=1

else

for j∈V（a）＼i

if V（j）＼a=，則hj→a=0

else hj→a=（∑b∈V+（j）＼aub→j）-（∑b∈V-（j）＼aub→j）

返回ua→i=∏j∈V（a）＼iθ（Jajhj→a）

算法3警示信息賦值指派算法

輸入：CNF因子圖G。

輸出：輸出一組變元賦值指派{x1，x2，x3，…，xn}。

begin

運行WP算法

計算所有的局部腔域Hi和沖突域ci

if ci=0，則對變元進行權值計算

if ci=1

if Higt;0，則xi=1

if Hilt;0，則xi=0

else Hi=0，則對變元進行權值計算

返回變元賦值指派

2.2變元權值計算

在迭代運算時，基礎的警示傳播算法只對沖突域ci=0，且局部腔域Higt;0的變元賦值為1，局部腔域Hilt;0的變元賦值為0，而對于沖突域ci=1的變元和ci=0且Hi=0的變元無法賦值。在求解最大可滿足性問題中，變元賦值的好壞直接影響著整個算法的求解效率，正確的變元賦值可以高效求解。本文提出了一種新的啟發式變元權值計算，通過權值計算來確定該變元的賦值。

對于未賦值的每一個變元都有一個正或負的權值，這取決于該變元的正文字和負文字出現的差異，變元的權值代表著變元為正或為負的程度。如果權值為正，則代表變元在整個CNF公式中更多地以正文字的形式出現，而不是負文字的形式出現，反之亦然。權重計算如式（8）所示。

Wvar=Number（PosLit）-Number（NegLit）Number（Clausevar）（8）

其中：Number（PosLit）表示變元正文字出現次數；Number（NegLit）表示變元負文字出現次數；Number（Clausevar）表示變元在子句中出現的次數。

算法4變元權值算法

輸入：CNF公式。

輸出：變元xi的賦值。

begin

for 對每一個未賦值的變元i：

初始變元權值Wi=0，找到包含變元i的所有子句Clausei并記錄總子句數Numberi

for對每一個子句Clausei中的變元

if igt;0，PosLit++

else ilt;0，NegLit++

Wi=PosLit-NegLitNumberi

if Wigt;0，則返回xi=1

else 返回xi=0

2.3局部搜索算法

在局部搜索算法中，搜索過程占用整個算法的大部分時間，普遍隨機搜索算法的初始解都是隨機選取，會造成初始解的隨機性，好的初始解可以高效地找到結果，不好的初始解會浪費很長時間且降低了算法的性能，同時還會重復地訪問一些解，出現循環的現象。本文提出的變元權值的警示傳播算法可以有效得到一組初始解，對后續進行局部搜索有很大幫助。

基于變元權值的警示傳播算法得到一組變元的賦值，由此構造了一組初始解。初始解得到的子句數不一定是最優的，需要局部搜素算法進行深一步搜索。對于Max-SAT問題，目的是找到滿足子句數最多的一組賦值，將得到的一組變元賦值放入到WalkSAT中進行搜索。

3實驗結果與分析

為了準確評估本文提出的新型變元權值計算的警示傳播算法能在解決Max-SAT問題時起到很好的效果，本文對算法WWP+WalkSAT、WalkSAT、SA、GA、VNS-GA、CCLS2akms、CCEHC、Optirise6-in和HS-Greedy進行了測試。其中WalkSAT、SA、GA、VNS-GA為經典的啟發式算法，CCLS2-akms、CCEHC、Optirise6-in和HS-Greedy為2016年Max-SAT Evaluation國際競賽的求解器。實驗結果使用了2016年Max-SAT Evaluation國際競賽中隨機類的數據集。

表1給出了SA、WalkSAT、WWP+WalkSAT、GA、VNS-GA幾種算法之間的統計比較結果。采用s3v70c1000、s3v80c1000兩種數據集（3-SAT實例，變元個數70和80，子句個數1 000），對滿足最大子句個數的結果進行了對比實驗。從表中可以看出，在70個子句中的10個實例中，有7個實例都取得了最好的結果，有3個實例略差一些。在80個子句中，只有4個實例取得最好結果，其余6個效果稍差一些。但可以明顯看出WWP+WalkSAT的效果遠遠高于WalkSAT，且滿足的子句個數也大大提高。

表2、3是將SA、WalkSAT、WWP+WalkSAT、CCEHC、CCLS2akms、Optirise6-in和HS-Greedy進行了測試。實驗結果使用了2016年Max-SAT Evaluation競賽中隨機類的數據集。其中表2中采用3-SAT實例，變元數70、90、110個，子句數700、800、900、1 000、1 100的數據集。每一種實例有10組數據。實驗結果采用平均精度計算表示，即最大可滿足子句數/實例子句數，再對10組數據求平均值。實驗表明：對于WWP+WalkSAT來說，精度達到了95%～99%，而CCEHC的精度在95%～97%。在15種數據集中，有12個數據集WWP+WalkSAT在求解精度方面排名第一，并且與CCEHC、HS-Greedy結果相差不大，但遠高于SA、WalkSAT、CCLS2akms、Optirise6-in幾種算法。說明WWP+WalkSAT算法對于求解易解算例十分有效，而且優于普通的局部搜索算法。表3中，實驗采用HG-3SAT-V300-C1000、HG-3SAT-V250-C1200兩種數據集（3SAT實例，300個變元，1 000和1 200個子句，α=4） 。實驗結果表明，算法CCLS2akms是無法求解該類問題的，WWP+WalkSAT的求解精度均達到了98%～99%，而CCEHC的精度穩定在99%左右。WWP+WalkSAT還是略差于CCEHC，但是性能遠遠好于SA、WalkSAT、Optirise6-in和HS-Greedy幾種算法。在難解算例中，WWP+WalkSAT稍差于CCEHC算法，但在易解實例中，WWP+WalkSAT求解性能好于CCEHC算法。由此可以說明WWP+WalkSAT算法對求解隨機Max-3-SAT的問題十分有效。

除此之外，通過五個數據集對算法WWP+WalkSAT和WalkSAT在迭代次數方面進行了對比實驗。圖3表明，兩者均進行1 000次迭代，結果表明除了數據集S3v110c1000中初始結果WWP+WalkSAT略差于WalkSAT，其余四個數據集一開始WWP+WalkSAT就優于WalkSAT。這是因為WalkSAT的初始解是隨機賦值，當初始解賦值好的時候會優于WWP+WalkSAT，而WWP+WalkSAT的初始解是通過變元權值計算得出的，所以一開始的滿足子句個數就會優于WalkSAT。隨著迭代次數的增加，WWP+WalkSAT滿足子句的個數遠遠優于WalkSAT。盡管在數據集S3v90c900中出現WalkSAT高于WWP+WalkSAT的現象，但是最后WWP+WalkSAT還是取得了不錯的結果。雖然在精度上取得了不錯的效果，但是WWP+WalkSAT算法的運行時間會差于WalkSAT算法，這也是該算法今后需要改進的地方。

4結束語

本文設計基于變元權值計算的警示傳播算法WWP+WalkSAT，對其算法進行了精度分析，實驗表明該算法對易解Max-3-SAT問題還是難解Max-3-SAT問題都具有較好的優勢，而且也打破了信息傳播算法求解的局限性，其結果對于以后的理論研究提供了很大的參考價值。與此同時該算法也可用于解決不同領域的實際問題，在組合拍賣、車輛調度、機器人路徑規劃、資源配置和網絡社交分析等方面有廣闊的應用前景。但是由于使用了基于變元權值計算的警示傳播算法增加了整個計算的復雜度因而消耗了時間，后續的研究將會在算法的變元剪枝策略以及其他減少時間效率方面入手。

參考文獻：

［1］王熙照，賀毅朝.求解背包問題的演化算法[J].軟件學報，2017，28（1）：1-16.（Wang Xizhao，He Yichao.Evolutionary algorithms for knapsack problems[J].Journal of Software，2017，28（1）：1-16.）

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

[3]Mousaei A，Taghaddos H，Nekouvaght T A，et al.Optimized mobile crane path planning in discretized polar space[J].Journal of Construction Engineering and Management，2021，147（5）：04021036.

[4]王曉峰，于卓，趙健，等.基于大規模圖的最大團問題算法分析[J].計算機工程，2022，48（6）：182-192，199.（Wang Xiaofeng，Yu Zhuo，Zhao Jian，et al.Analysis of algorithms for solving maximum clique problems of large-scale graphs[J].Computer Engineering，2022，48（6）：182-192，199.

[5]Suzuki M，Kabashima Y.Statistical mechanics of the minimum vertex cover problem in stochastic block models[J].Physical Review E，2019，100（6-1）：62101.

[6]何琨，鄭迥之.最大可滿足性問題的算法研究綜述[J].華中科技大學學報：自然科學版，2022，50（2）：82-95.（He Kun，Zheng Jiongzhi.Survey on algorithms for the maximum satisfiability problem[J].Journal of Huazhong University of Science and Technology：Natural Science Edition，2022，50（2）：82-95.）

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

[8]劉燕麗，黃飛，張婷.基于環型擴展推理規則的MaxSAT完備算法[J].南京大學學報：自然科學，2015，51（4）：762-771.（Liu Yanli，Huang Fei，Zhang Ting.MaxSAT complete algorithm based cycle extended inference rules[J].Journal of Nanjing University：Natural Sciences，2015，51（4）：762-771.

[9]Li Chumin，Xu Zhenxing，Coll J，et al.Combining clause learning and branch-and-bound for MaxSAT[C]//Proc of International Conference on Principles and Practice of Constraint Programming.Berlin：Sprin-ger，2021：1-18.

[10]Morgado A，Heras F，Liffiton M，et al.Iterative and core-guided MaxSAT solving：a survey and assessment[J].Constraints，2013，18（4）：478-534.

[11]Li Chumin，Manyà F，Mohamedou N O，et al.Resolution-based lower bounds in MaxSAT[J].Constraints，2010，15（4）：456-484.

[12]Heras F，Larrosa J，Oliveras A.MiniMaxSat：a new weighted Max-SAT solver[C]//Proc of International Conference on Theory and Applications of Satisfiability Testing.Berlin：Springer，2007：41-55.

[13]Johnson D S.Approximation algorithms for combinatorial problems[J].Journal of Computer amp; System Sciences，1974，9（3）：256-278.

[14]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.

[15]Chu Yi，Luo Chuan，Cai Shaowei，et al.Empirical investigation of stochastic local search for maximum satisfiability[J].Frontiers of Computer Science，2019，13（1）：86-98.

[16]王曉峰，許道云.警示傳播算法收斂的充分條件[J].軟件學報，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.）

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

[18]Shi Xiangqiong，Schonfeld D，Tuninetti D.Message error analysis of loopy belief propagation[C]//Proc of IEEE International Conference on Acoustics，Speech and Signal Processing.Piscataway，NJ：IEEE Press，2010：2078-2081.

[19]王曉峰，許道云，韋立.隨機可滿足實例集上警示傳播算法的收斂性[J].軟件學報，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.）

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

[21]Layeb A.A new greedy randomized adaptive search procedure for solving the maximum satisfiability[J].International Journal of Operational Research，2013，17（3）：1-17.

收稿日期：2022-01-14；修回日期：2022-03-05基金項目：國家自然科學基金資助項目（62062001）；寧夏自然科學基金資助項目（2020AAC03214）；北方民族大學研究生創新項目（YCX21086）

作者簡介：吳宇翔（1997-），男，寧夏石嘴山人，碩士研究生，主要研究方向為算法設計與分析；王曉峰（1980-），男，甘肅會寧人，副教授，博士，主要研究方向為機器學習、算法設計與分析；丁紅勝（1977-），男（通信作者），甘肅甘谷人，副教授，主要研究方向為數字圖像處理、算法分析與設計（78950228@qq.com）；于卓（1997-），男，寧夏銀川人，碩士研究生，主要研究方向為算法設計與分析．