基于樹寬的警示傳播算法收斂性分析

摘要：警示傳播算法作為一種基本的信息傳播算法，其收斂時求解可滿足性問題十分有效，但因子圖結構較為復雜時，算法往往不收斂導致求解失敗。為了對這種現象給予理論解釋，同時對警示傳播算法收斂性進行有效分析，利用樹分解方法構造了命題公式對應因子圖的樹寬度量模型，計算可滿足隨機實例的樹寬。建立樹寬與警示傳播算法收斂性之間的關系，給出了基于樹寬的警示傳播算法收斂性判定條件。通過實驗分析，結果表明該方法有效，對于分析其他信息傳播算法收斂性分析研究具有十分重要的意義。

關鍵詞：警示傳播算法； 收斂性； 樹寬； 命題公式； 可滿足性問題

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

文章編號：1001-3695（2022）10-027-3061-04

doi：10.19734/j.issn.1001-3695.2022.03.0098

Convergence analysis of warning propagation algorithm based on tree width

Xie Zhixina， Wang Xiaofenga，b， Yu Zhuoa， Cao Zexuana， Wu Yuxianga， Mo Chunhuia

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

Abstract：The warning propagation algorithm， as a basic information propagation algorithm， is very effective in solving the satisfiability problem when it converges. However， when the structure of factor graph is more complex， the algorithm often does not converge， resulting in solving failure. In order to give a theoretical explanation for this phenomenon， and to effectively analyze the convergence of warning propagation algorithm， this paper used tree decomposition method to constructed the tree width measurement model of factor graph corresponding to propositional formula， and calculated the tree width that satisfied the random instance. It established the relationship between tree width and convergence of warning propagation algorithm， and gave the convergence judgment condition of warning propagation algorithm based on tree width. The experimental results show that this method is effective， and it is very important to analyze the convergence of other information transmission algorithms.

Key words：warning propagation（WP） algorithm; convergence; tree width; propositional formula; satisfiability problem

0引言

約束滿足問題（constraint satisfaction problem，CSP）在人工智能研究領域中有著深遠影響［1～3］，并受到領域專家的廣泛關注。現實世界中許多問題可以歸約到CSP，如圖著色問題、旅行商問題（TSP）、調度問題等。可滿足性判定問題（satisfiability，SAT）是典型的CSP，已經被證明是NP完全的［4］，其NP完全性廣泛擴展應用于其他領域NP完全問題研究。SAT問題是研究對于給定命題公式是否存在一組布爾變量賦值，使該命題公式為真。由于SAT問題的廣泛應用和核心地位，受到了學者們普遍關注。

物理學家提出一種基于統計物理學的警示傳播算法（WP算法）［5］，是一種最基礎的信息傳播算法，主要是基于因子圖上進行警示信息的傳遞和迭代。當算法收斂時，對部分變元進行固定取值并對公式進行化簡，以實現SAT問題求解。但隨著因子圖結構逐漸復雜，信息在出現的環路中無限循環傳播，使得警示信息無法收斂到一個固定值，最終導致WP算法求解失敗，該現象稱為算法不收斂［6］。WP算法收斂問題是問題有效求解的保證，因此研究WP算法的收斂性對其應用有著重要的意義。

當前對WP算法收斂性研究已經取得了一些成果。2001年，Weiss等人［7］得出當因子圖只有一個環時，算法收斂且得到的值為變量邊緣分布的有效近似。2007年，Maneva等人［8］對植入指派的隨機指派的可滿足實例產生模型給出一個收斂性條件，但其應用僅局限于該型實例產生模型，欠缺在3-SAT實例產生模型上判定應用。植入指派中，當概率p足夠大時，產生的實例高概率有一組滿足賦值。2013年，王曉峰等人［9］對兩個變量不屬于一個子句的特殊SAT結構進行研究，給出一個基于高斯模型算法收斂的充分必要條件，但只證明p取值很小的一部分植入指派實例，應用受限。2014年，Su等人［10，11］利用半定規劃檢查基于高斯模型算法的收斂性，對算法的收斂性進行了分析研究，對于半定規劃問題求解的瓶頸在于計算，當SAT問題規模增大即因子圖規模增加且變得復雜時，半定規模檢查效率較低且非常困難。2016年，王曉峰等人［12］對消息矩陣為半正定矩陣的算法進行了收斂性分析，給出了收斂的充分必要條件。2018年，佘光偉等人［13］基于（3，4）-SAT問題研究了修正WP算法的收斂性，得出修正WP算法在正則問題上收斂，但在過程中需要將3-SAT問題轉換為（3，4）-SAT特殊結構，且WP算法在轉換后的實例上對可滿足性判定失效。2020年，崔立等人［14］研究了WP可解公式上警示傳播算法的收斂性，給出了WP可解公式上警示傳播算法收斂的一個充分條件。2021年，牛進等人［15］利用結構熵概念對WP算法收斂性進行了分析并給出一個收斂閾值，但社區劃分準確性欠缺評價指標，影響因子圖結構熵的準確計算。2022年，梁晨等人［16］利用K維結構熵對調查傳播算法（survey pro-pagation，SP）收斂性進行分析，給出一個收斂的充分條件，但其中所要求的結構信息最小化滿足條件較難達到。以上對WP算法收斂性研究基本基于特殊模型或應用于某種具體情況，對于非特殊結構因子圖算法研究缺失。因此，對于WP算法收斂性分析研究仍需要大量工作去完成。

因子圖結構對WP算法收斂性影響巨大，隨著問題規模增大，因子圖中節點和邊數增加，導致WP算法信息傳遞變得十分復雜。1991年，Robertson等人［17］提出樹分解技術，該技術的目標在于將圖分解為一棵樹，利用樹上的結構信息反映原圖的一些性質。圖的樹寬（tree width）和樹分解（tree decomposition）對問題的求解提供了一條新途徑，對圖進行樹分解，將難解問題的圖模型限制在有限樹寬中，問題可以求解。從計算角度出發，樹寬與可處理性有著重要聯系，限制樹寬參數可用于限制組合爆炸，低樹寬意味著計算的快速完成。研究發現，CNF公式因子圖為一棵樹時，其可滿足性可以在多項時間內判定。文獻［18］利用樹寬參數對約束滿足問題中的QCSP（quantified constraint satisfaction）進行限制，得到一個多項式時間復雜度的求解算法。利用一種特殊的樹型結構，文獻［19］將正則公式對應的因子圖轉換為樹型結構，并給出了隨機正則（3，r）-SAT的可能相變點。文獻［20］利用樹分解技術求解了受約束的可滿足性問題，并對SAT問題進行了分析，并給出了求解難度與樹寬之間的關系。WP算法的收斂性與其因子圖結構密切相關，引入樹寬度量因子圖的結構特性，同時樹寬還可以反映分解后小問題的規模，更好地反映問題的復雜程度，相較于以往的信息傳播算法收斂性分析，沒有條件限制，適用范圍廣，同時從因子圖結構分析更好地反映命題公式結構特征與其收斂性之間的聯系，進而在因子圖結構性質上完善對WP算法收斂性質研究。

綜上所述，本文對WP算法求解SAT問題時的收斂性進行分析研究。利用樹寬的概念，在G（n，3，m）模型產生不同規模的SAT實例上，使用樹分解算法求得樹寬，對命題公式因子圖結構信息進行了分析，提出了SAT實例的樹寬模型，通過WP算法的收斂情況，分析WP算法的收斂性和樹寬之間關系，給出基于樹寬的WP算法收斂判定條件。

1相關知識

1.1因子圖

因子圖（factor graph）是一個二部圖，表示許多變量的全局函數分解成局部函數的乘積［21］。圖中包含變元與子句節點兩類節點。圓形表示變元節點，方框表示子句節點，實線表示變元在子句以正文字出現，虛線表示變元在子句中以負文字出現。例如：對于一個CNF公式

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

其因子圖如圖1所示。

警示傳播算法迭代過程在因子圖上進行，已經證明當因子圖為樹型結構時，信息傳播算法可以有效收斂，對于因子圖含有多個回路的圖形結構的實例，信息傳播算法不總有效，常表現為不收斂［22］。

1.2警示傳播算法

WP算法中子句節點傳遞給變元節點的消息為警示信息，記做ua→i。其值為1時表示子句a的可滿足性由變元的取值決定;值為0時，則表示變元的取值無法對子句a的可滿足性起到決定性作用。WP算法的信息更新迭代方程一般寫為警示信息之差形式，如下：

ua→i（t）=∏j∈V（a）＼iθ（－Jaj（∑b∈V+（j）＼aJbjub→j（t－1）－

∑b∈V－（j）＼aJbjub→j（t－1）））（1）

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

Hi=－∑b∈V（i）Jbiu*b→i（2）

hj→a=∑b∈V+（j）＼aub→j（t－1）－∑b∈V－（j）＼aub→j（t－1）（3）

Hi＜0時，賦值為0，Hi＞0時，賦值記為1，否則暫時不對xi進行賦值。hj→a：腔域，當xj變元只出現在子句a中，賦值為1。

算法1WP算法

輸入：CNF公式;迭代終止步數tmax。

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

a） 構造相應因子圖

b） 初始化迭代次數t=0，對因子圖上每條邊對ua→i以均等概率從{0，1}隨機選擇一個進行賦值

c） for t=1 to tmax

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

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

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

返回u*a→i

退出循環

e） if t==tmax

返回未收斂

根據WP算法的迭代過程及迭代方程可以看出，ua→i的值對固定變元xi的值十分重要，在固定變元規模下，因子圖規模趨于復雜時，同一變元出現在不同子句概率迅速增加，并且環路出現且數目急劇上升，式（1）中ua→i的計算與ub→j密切相關，ub→j用來計算在子句a中出現的變元在其他子句中的消息值，同一變元出現在不同子句中數目越多，需要計算的信息越多，此時ua→i計算變得更加復雜，引起求解時間增加，且每次迭代后的信息值趨于穩定的概率越低，算法收斂概率受到明顯影響。算法收斂時，可以得到警示信息的固定點，根據固定點信息進行部分變元賦值，進行CNF公式簡化以完成求解。由于問題規模的增加，變元xi出現在更多的子句中，根據式（3）的計算過程，腔域計算隨著因子圖規模增加計算量迅速增長，增加了計算時間，并且在每一次迭代中計算得到的信息也因復雜圖結構導致相鄰兩次計算不同，最終不收斂，算法失效。當算法不收斂時，迭代至設定最大迭代次數，求解時間達到最大，但此時算法已求解失敗，迭代次數不是算法求解時間的主要影響因素。因此，在WP算法迭代過程中，因子圖結構對WP算法性能影響重大。

1.3樹分解與樹寬

樹寬可以用來度量圖的復雜結構，研究人員發現，將規模大的難解問題利用樹分解思想，將其分解為規模較小的易解問題，求解十分有效。圖G=（V，E），對其進行樹分解，即對其節點集V進行劃分，使圖G盡可能地劃分為一棵樹型結構，使得圖中一個節點子集對應樹T=（I，F）結構中的一個節點，其中I為分解樹節點。樹寬描述其樹型結構信息，在樹型結構上刻畫圖G的結構性質，將圖的樹寬作為一個參數反映問題的求解復雜度，同時對算法在求解問題時的一些性質可以進行刻畫。

圖中節點子集構成一個包（bag），用TG=（X，T）表示一個圖的樹分解，X={Xi：i∈I}是圖G節點集的非空子集。其中：Xi的并集為圖G的節點集；圖G中的任意兩點存在一條邊，那么它們必同時屬于某個Xi；若j、k、l為樹中的三個節點，當j在l到k的路徑上，則有v屬于Xl和Xk，v也屬于Xj。

樹分解的寬度等于max（|Xi|-1： i∈I），即分解后最大包中點數目減1。圖G的樹寬為其最小樹分解的寬度。

定義1消點序。設圖G =（V，E），令n=|V|，雙射f：V→［n］記為消點序（elimination ordering），其中集合［n］={1，2，3，…，n}。

定義2弦圖。對于圖G中任何大小超過4的環路，存在連接環路中不相鄰節點的弦邊，使其環路大小不超過3，則此時圖G為弦圖。

圖G的樹寬為其所有超弦圖H中最小的一個最大團的大小減1。一般使用消點序和割集構造分解樹，同時也有利用智能算法構造樹分解的一些策略。

算法2消點序構造樹分解

輸入：圖G=（V，E）。

輸出：圖G的一個樹分解T=（I，F）。

a） 根據消點序對圖進行刪點。

b） 每刪掉一個點，將該節點鄰居節點加邊構成一個環并記錄。

c） 重復步驟b）的操作直到所有節點刪除完畢，根據消點序，反向生成樹節點，將每次有邊聯系的點放在一個包中。

d） 對構成的包進行合并包操作，使得包序列中不存在包與包之間真子集情況。

e） 連接包集，生成分解樹。

圖2給出一個示例，給出一個圖G及其樹分解結果。對于圖G，存在一個大小超過4的環，這里在樹分解中刪除節點v2時，連接v3和v5使其構成一個環，在樹分解后的樹型結構中，將v3、v5、v6放入一個包，作為一個樹節點。根據樹寬的定義，其分解后的樹寬為max（|xi|-1： i∈I），其樹寬為2。

2命題公式的樹寬

WP算法在求解3-SAT問題時十分有效，但在難解區域往往不收斂，此時WP算法求解失效。因此，研究WP算法收斂性十分重要。當前對于WP算法在因子圖上的收斂性分析，相關系統理論分析仍舊欠缺，本文利用樹寬度量因子圖的結構復雜性，建立因子圖樹寬度量模型，對因子圖的樹寬進行分析和研究，實現對WP算法在因子圖上收斂性分析。

2.1因子圖處理

樹分解算法應用于無向圖分解，因子圖是一種包含兩類節點、兩類邊的圖結構。樹分解過程中，需要利用節點的度和節點之間的邊關系信息去構造分解樹。對于圖G樹分解后的樹寬tw（G）有如下基本性質。

性質1［23］對圖G存在tw（G）≥γ（G）≥σ（G）。其中σ（G）為圖G中的小節點度數，γ（G）由式（4）給出。

γ（G）=|v|－1if G is a clique

minu，v∈V，（u，v）Emax{d（u），d（v）}otherwise（4）

由性質1可知，樹分解生成的樹寬與節點類型和邊類型無關，因子圖中的變元節點和子句節點，在樹分解過程中將視為一類點，根據樹分解寬度的定義，因子圖中表示變元在子句中以正負文字出現的兩種邊，不影響樹寬計算，視為一種邊即可。

根據樹分解過程，在進行樹分解算法處理時，先將因子圖中的變元和子句節點轉換為一類節點表示，將表示變元以負文字出現的虛邊轉換為實邊表示，處理過程如圖3所示。

根據圖3所示處理過程對于因子圖轉換后進行樹分解處理，分解結果得出給定因子圖分解樹中最大包節點為{2，6，7，8，9}，由樹寬定義計算樹寬為4。

2.2樹分解算法及樹寬度量

對于給定命題公式G（n，3，m）生成相應的因子圖，將其按照因子圖處理過程先進行轉換，隨后利用基于消點序的樹分解算法生成相應的樹分解。實驗中使用樹分解算法為近似分解算法，即分解得到的樹寬近似圖本身的寬度。

消點序樹分解算法中，消點序影響著樹分解的求解質量，好的消點序得到的樹寬更加接近其本身樹寬，同時在求解時間上大多占優。構造一個好的消點序是困難的，LB算法基于任意消點序進行樹分解構造且表現良好。本文在LB算法的基礎上增加在子句節點和因子節點內進行隨機排序生成消點序的規則，規則規定對兩類節點消點的順序，在消點填邊策略下，保證了不在變元節點與子句節點之間增加邊，進而不影響WP算法警示信息的傳播過程。

消點序規則：每次生成的CNF公式中，對變元和子句節點進行編號，變元編號在變元個數范圍內隨機生成，子句節點編號在變元節點編號數目之后隨機生成。根據樹分解規則，此時填邊不影響WP算法運行。

LB算法根據消點序進行填邊處理，實現圖的三角化得到其弦圖，對于圖中存在的環利用其處理邏輯進行填邊操作，保證大小超過4的環存在弦邊。LB算法三角化結果如圖4所示。

對于LB算法需要初始化序列，這里按照圖中點的編號給出序列為{a，b，c，d，e，f }。首先對a點進行處理，a的鄰接點集有{a，b，c}（包含自身），以a的鄰接點集構造的連通分量有{d，e，f }，對d、f進行加邊，虛線表示添加的邊，按照序列重復過程實現圖G的LB三角化生成弦圖。

算法3LB的樹分解算法

輸入：圖G=（V，E）;序列限制的V序列α。

輸出：三角化的圖H及樹寬。

a） 初始化：G→H;→F。

b） for x in α：

計算x的的鄰接點集NH［x］得到以其為分割符的連通分量，對每個連通分量的鄰接點通過加邊構成環，加邊集記為F′;

F+F′→F; （V，E+F）→H。

c） 對構成的圖H，以消點序反向構成包集，刪除其中為其他包的真子集的包，連接生成分解樹。

d） 分解樹中最大的包中節點數目減1為分解樹寬。

WP算法在求解kSAT問題時，可以將難解區域變窄，利用分解樹的樹寬參數對NP-難問題進行分類，由于WP算法在難解區域失效且表現為不收斂，通過樹寬對WP算法收斂性進行判定，即對算法有效性給出了判定條件，同時對k-SAT問題進行了分類。該算法求解CNF公式的樹寬，反映了CNF公式的結構復雜性，分解過程中將因子圖分解為樹型結構，樹型結構體現不同變元和子句的聯系以及形成樹節點中原圖節點之間的相關性，利用樹寬參數對因子圖的結構信息進行表達。

利用本文算法對WP算法收斂性進行分析研究，與其他WP算法收斂性研究中對命題公式和圖模型結構限制相比，使用范圍不受限制，并且給出的判定條件使用方便。本文完善了在因子圖結構上對WP算法的收斂性分析，同時WP算法作為信息傳播算法中最為基礎的一種，為其他信息傳播算法收斂性研究提供了新的思路和方向。

3收斂性分析

本文利用模型G（n，3，m）產生隨機實例，其中n為變元個數，3表示每個子句的長度，m為子句個數，其中m個子句從所有可能的23×C3n個子句隨機均勻選擇。本實驗選取兩組實驗數據對比，變元規模分別設置為n=100和150，兩組實驗設置WP算法最大迭代次數都為1 000。這里根據算法3求得其樹寬，其中m/n用約束密度α表示，已經研究得出，約束密度對因子圖的結構和WP算法的收斂性有著重要影響。這里取α從2～5.5，遞增梯度為0.05。由于同一約束密度生成的隨機SAT實例會出現極少數異常SAT實例，為消除其影響，對同一約束密度的隨機實例取100組，實驗所得樹寬值為100組實例由算法3求得樹寬的均值，對于非整數均值進行取整操作。每組實例對其WP算法運行的收斂情況進行統計，計算其收斂率，SAT實例樹寬隨實例約束密度變化如圖5（b）所示。

圖5分別描述了兩組變元規模為100和150的SAT實例時，SAT實例因子圖的樹寬隨著約束密度α增長的變化趨勢，其橫坐標為約束密度α。在兩組不同規模的SAT實例中，隨著約束密度α的增長，樹寬也逐漸增加，但其增長速度逐漸放緩。說明在樹分解過程中，隨著規模因子圖的結構逐漸復雜，樹分解生成樹節點包大小增長放緩，即因子圖中環路因子圖結構區域穩定。圖6對比了WP算法收斂率與SAT實例樹寬之間的關系，進而給出樹寬與收斂性之間的關系。

圖6分別展示了WP算法收斂概率隨樹寬tw變化的情況，統計WP算法在100組實例上的收斂個數，計算得到WP算法收斂概率，當樹寬值超過當前規模實例的樹寬閾值時，WP算法收斂概率驟然下降至不收斂。當實例變元規模n=100，樹寬tw≤62時，WP算法在隨機SAT實例求解上完全收斂，當63≤tw≤67時，WP算法在隨機SAT實例上的收斂概率從1迅速下降至0。當實例變元規模n=150，樹寬tw≤91時，WP算法在所有實例上完全收斂;當92≤tw≤100時，WP算法在隨機SAT實例上的收斂概率迅速下降到0。從圖6可以得到WP算法在大多數實例上高概率收斂，但一旦超過某一閾值，WP算法收斂概率驟降，幾乎不收斂。

隨機SAT實例中，對同一約束密度，實驗中會得到不同的樹寬，對應因子圖中出現環路和某些變元節點度不同。當約束密度增加，樹分解算法的求解時間也相應增加，本文樹分解算法對與當前節點和其鄰居節點構成的連通分量中增加邊，因子圖約束密度增加，環路相應增多，對應的連通分量增加，故增加了求解時間。同時，約束密度增加，意味著子句節點的增加，樹分解的寬度也與圖中節點數目相關，當WP算法的收斂概率突然下降，其樹寬仍緩慢增加，相比于隨機SAT實例的規模，樹寬大小與增長速度都遠小于隨機實例。這對研究信息傳播算法在難解實例上因子圖的結構信息與算法收斂性提供了一定的基礎。

因子圖的結構對WP算法性能影響巨大，實驗中給出了兩個變元規模下的WP算法收斂的充分條件，對于其他規模隨機SAT實例WP算法收斂時的樹寬閾值也可提供該方法得出。

4結束語

信息傳播算法在求解3-SAT問題時十分有效，WP算法作為一種基本的信息傳播算法，研究其性質對其他信息傳播算法有著重要作用。本文提出了一種度量命題公式結構特征的算法，利用樹寬表示因子圖的結構信息，在實驗中得到了不同規模隨機實例的樹寬變化和WP算法收斂性變化，給出在不同規模隨機實例算法收斂時的樹寬充分條件。下一步工作將樹分解算法進行改進，以求得更加接近圖樹寬的分解樹樹寬，同時將樹分解策略應用于其他信息傳播算法的收斂性分析，并對樹寬與因子圖復雜性的關系進行深入的分析和驗證。

參考文獻：

[1]Dyer M， Frieze A， Molloy M. A probabilistic analysis of randomly generated binary constraint satisfaction problems［J］.Theoretical Computer Science，2003，290（3）：1815-1828.

［2]Creignou N， Daudé H. The SAT-UNSAT transition for random constraint satisfaction problems［J］.Discrete Mathematics，2009，309（8）：2085-2099.

［3]Gaspers S， Papadimitriou C， Sther S H， et al. On satisfiability problems with a linear structure［EB/OL］.（2016-02-25）.http：//doi.org/10.48550/arxiv.1602.07876.

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

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

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

［7]Weiss Y， Freeman W T. Correctness of belief propagation in Gaussian graphical models of arbitrary topology［J］.Neural Computation，2001，13（10）：2173-2200.

［8]Maneva E， Mossel E， Wainwright M. A new look at survey propagation and its generalizations［J］.Journal of the ACM，2007，54（4）：1089-1098.

［9]王曉峰，許道云，韋立.隨機可滿足實例集上警示傳播算法的收斂性［J］.軟件學報，2013，24（1）：1-11.（Wang Xiaofeng， Xu Daoyun， Wei Li. Convergence of warning propagation algorithms for random sa-tisfiable instances［J］.Journal of Software，2013，24（1）：1-11.）

［10]Su Qinliang， Wu Y C. Convergence analysis of the variance in Gaussian belief propagation［J］.IEEE Trans on Signal Processing，2014，62（19）：5119-5131.

［11]Su Qinliang， Wu Y C. On convergence conditions of Gaussian belief propagation［J］.IEEE Trans on Signal Processing，2015，63（5）：1144-1155.

［12]王曉峰，許道云.警示傳播算法收斂的充分條件［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.）

［13]佘光偉，許道云.用于求解正則（3，4）-SAT實例集的修正警示傳播算法［J］.計算機科學，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.）

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

［15]牛進，王曉峰，林青文.基于結構熵的警示傳播算法收斂性分析［J］.計算機應用研究， 2021，38（3）：760-763，776.（Niu Jin， Wang Xiaofeng， Lin Qingwen. Convergence analysis of warning propa-gation algorithm based on structural entropy［J］.Application Research of Computers，2021，38（3）：760-763，776.）

［16]梁晨，王曉峰，劉子琳，等.基于K維結構熵的調查傳播算法收斂性分析［J］.計算機應用研究，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.）

［17]Robertson N， Seymour P D. Graph minors. X. obstructions to tree-decomposition［J］.Journal of Combinatorial Theory Series B，1991，52（2）：153-190.

［18]Chen Hubie. Quantified constraint satisfaction and bounded treewidth［C］//Proc of the 16th European Conference on Artificial Intel-ligence.Netherlands：IOS Press，2004：161-165.

［19]Krishnamurthy S， Sahoo S. Balanced k-satisfiability and biased random k-satisfiability on trees［J］.Physical Review E，2013，87（4）：042130.

［20]雷瑩，許道云.圖的樹分解算法及其應用［J］.計算機科學，2020，47（5）：51-58.（Lei Ying， Xu Daoyun. Algorithm of graph and its application［J］.Computer Science，2020，47（5）：51-58）.

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

［22]Hammerl T， Musliu N， Schafhauser W. Metaheuristic algorithms and tree decomposition［M］//Springer Handbook of Computational Intel-ligence.Berlin：Springer，2015：1255-1270.

［23]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.

收稿日期：2022-03-18；

修回日期：2022-05-05

基金項目：國家自然科學基金資助項目（62062001，61762019，61862051，61962002）；寧夏自然科學基金資助項目（2020AAC03214，2020AAC03219，2019AAC03120，2019AAC03119）；北方民族大學重大專項資助項目（ZDZX201901）；北方民族大學研究生創新項目（YCX22197）

作者簡介：謝志新（1997-），男，陜西渭南人，碩士研究生，主要研究方向為算法分析與設計；王曉峰（1980-），男（通信作者），甘肅會寧人，副教授，碩導，博士，主要研究方向為人工智能（xfwang@nmu.edu.cn）；于卓（1997-），男，寧夏銀川人，碩士研究生，主要研究方向為算法分析與設計；曹澤軒（1998-），男，寧夏銀川人，碩士研究生，主要研究方向為算法分析與設計；吳宇翔（1997-），男，寧夏銀川人，碩士研究生，主要研究方向為算法分析與設計；莫淳惠（1994-），女，重慶人，碩士研究生，主要研究方向為算法分析與設計．