基于動態度的回溯算法求解大值域約束滿足問題

摘 要： 針對一個具有精確可滿足性相變現象的大值域隨機約束滿足問題，提出了兩種啟發式動態回溯算法，即基于動態度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域與動態度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。這兩種算法分別基于ddeg和dom/ddeg挑選變量，利用維持弧相容（MAC）技術為挑選的變量進行賦值。當賦值無法進行時，再執行動態回溯修正變量的賦值。數值實驗結果表明：在控制參數非常接近理論相變點時，算法仍然能夠有效地找到問題的解。與經典回溯算法相比，這兩種啟發式動態回溯算法具有顯著的優越性。

關鍵詞： 約束滿足問題； 動態度； 回溯算法； 維持弧相容

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

文章編號： 1001-3695（2022）05-023-1427-05

doi：10.19734/j.issn.1001-3695.2021.09.0433

Dynamic degree based backtracking algorithm to solve constraint satisfaction problems with large domains

Zhang Xuecai， Zhao Chunyan

（College of Science， University of Shanghai for Science amp; Technology， Shanghai 200093， China）

Abstract： This paper proposed two heuristic dynamic backtracking algorithms which called ddeg-MAC backtracking algorithm based on dynamic degree and dom/ddeg-MAC backtracking algorithm based on dom/ddeg，respectively.The two algorithms chose variable according to the ddeg of the variable and the dom/ddeg of the variable，respectively.Both of the algorithms used maintaining arc consistency technique to assign the selected variables.When the assignment of the variabled violates the constraint，

it performed dynamic backtracking to correct the value of the nearest variable.Numerical results show that the algorithms can find the solution of the problem effectively when the control parameter is very close to the theoretical phase transition point.Compared to the classical backtracking algorithm，the two heuristic dynamic backtracking algorithms have significant advantages.

Key words： constraint satisfaction problem； dynamic degree； backtracking algorithms； maintaining arc consistency

0 引言

約束滿足問題（constraint satisfaction problem，CSP）是人工智能領域中一個非常重要的問題。近年來，已經成為統計物理學、信息論和離散數學等交叉學科領域中的研究熱點之一。CSP在如人臉識別、物流調度、統籌規劃、配置問題、視覺問題和機器學習等實際問題和工程技術中有著非常廣泛的應用。

許多問題如圖著色、頂點覆蓋、哈密頓回路、k-SAT、拉丁方和N-皇后等問題都是CSP。一般情況下，大多數的隨機CSP都是NP-完全問題。早期的許多理論研究和算法實驗主要是圍繞二元標準CSP模型A、B、C、D展開的［1～3］。然而，Achlioptas等人［4］指出這四個模型都表現出平凡漸近不可滿足性。為了克服這一缺點，一些改進的模型相繼被提出［5～9］。其中，Xu等人［6］提出了RB（Revised B）模型，此模型是對B模型的一個修改，通過對變量取值域和約束數目的限制，避免了標準B模型不能產生難解實例的缺點，并且嚴格證明了RB模型存在精確的可滿足性相變現象。隨后，Xu等人［10］從理論上證明了RB模型在相變區域生成的難解實例具有指數級的樹歸結復雜性，即這些隨機實例幾乎都是極其難解的。實驗上，也驗證了相變閾值附近，求解難度隨著問題規模呈指數級增長，并且在相變點處達到頂峰［11］。因此，RB模型自提出以來，就受到了國內外學者的廣泛關注。2011年，Zhao等人［12］利用有限尺度分析方法給出了有限規模下RB模型尺度窗口的一個上界。Fan等人基于RB模型先后提出了k-CSP［13］和d-k-CSP模型［14］，趙春艷等人［15］提出了p-RB模型，這些模型都被嚴格證明具有精確的可滿足性相變現象。雖然RB模型的相變點可以通過嚴格的數學方法得到，但是單個隨機實例的求解卻極具挑戰性?；赗B模型構造的可滿足難解算例被廣泛地應用于各種算法競賽中。Zhao等人［16，17］引入無序系統中的空腔場方法，提出了由置信傳播（belief propagation，BP）引導的消息傳遞算法，吳撥榮等人［18］將BP和模擬退火算法相結合來求解RB模型等具有大值域的隨機CSP。2021年，Zhao等人［19］提出了基于異步更新的BP消去算法，能在接近理論相變點時有效地求解RB模型。上述算法都是啟發式的不完備求解算法。而回溯（backtracking，BT）算法則是一種類似于窮舉的完備算法，它要么可以找到問題的解，要么能證明問題無解［20］。但是最壞情況下，算法具有指數級的復雜性。因此，許多研究學者從啟發式排序［21～24］、相容性技術［25，26］和回溯機制［27，28］等方面改進了回溯算法。2016年，Marino等人［29］提出了基于BT的調查傳播（survey propagation，SP）算法求解3-SAT問題，在非常接近相變閾值時能夠在線性時間內找到非凍結變量的解。Li等人［30］提出改進的基于變量度排序的啟發式搜索算法求解CSP。2021年，范如夢等人［31］提出了利度啟發式策略和最少約束值啟發式策略來選擇變量進行賦值的回溯算法，在較短的時間內能有效地找到問題的解。由此可見，在回溯算法中，基于變量度來選擇變量進行賦值具有非常重要的意義。

本文提出了兩種基于動態度的啟發式回溯算法，即基于動態度的ddeg-MAC回溯算法和基于值域與動態度比值的dom/ddeg-MAC回溯算法來求解RB模型等一類具有大值域的隨機CSP。這兩種算法分別基于ddeg值最大和dom/ddeg值最小來挑選變量，然后均利用MAC按照所挑選變量分量的AC支持個數從大到小的順序對所挑選的變量進行賦值。如果發生沖突，則在最大回溯次數內進行回溯。

3 數值結果與算法分析

RB模型在k≥2時都是NP-完全的。因此，本文取k=2，α=0.8，r=3，N∈［20，100］生成的RB模型隨機實例作為測試算例。由定理1可知，可滿足性相變閾值為pcr≈0.234。對不同的N，相應的變量取值域規模d，約束數目M，如表1所示。在這兩種算法中，均取最大回溯次數Tmax=500。

3.1 數值結果

在隨機生成的100個二元RB模型隨機實例上進行算法實驗。ddeg-MAC和dom/ddeg-MAC回溯算法能找到解的概率分別如圖1、2所示。從圖1可以看出，ddeg-MAC回溯算法在p≤0.08時能以概率1找到解，而當p≥0.14時算法失效。從圖2可以看出，dom/ddeg-MAC回溯算法在p≤0.14時能以概率1找到解，而當p≥0.2時算法失效。顯然，dom/ddeg-MAC回溯算法表現出了更好的求解性能。

取N=60，這兩種算法在求解100個隨機實例時無回溯和需要回溯找到解的實例數目分別如圖3、4所示。從圖3可以看到，ddeg-MAC算法在p≤0.08時能無回溯找到所有實例的解。當p≥0.16時，在有限的回溯次數下算法無法找到任何實例的解。而從圖4可知，dom/ddeg-MAC算法在p≤0.13時能無回溯地找到所有實例的解。隨著p的不斷增加，需要發生回溯才能找到解的實例數目逐漸增加。當p≥0.22時，算法在有限的回溯次數下無法找到任何實例的解。

取N=60時，這兩種算法求解時所需回溯次數的均值和方差如圖5、6所示。不難得出，在算法能找到解的概率從1到0轉變的區域內，需要的平均回溯次數呈現出逐漸增加的趨勢，且在算法求解的相變閾值處（即求解概率約為50%）方差達到最大。取p=0.1，對于不同的N，ddeg-MAC和dom/ddeg-MAC回溯算法求解100個由RB模型生成的隨機實例的運行時間分別如圖7、8所示。顯然，考慮了變量dom的dom/ddeg-MAC回溯算法大大縮短了求解時間。

3.2 算法分析

下面討論最大回溯次數Tmax的取值對算法求解性能的影響。取N=60，dom/ddeg-MAC回溯算法在Tmax分別取50、500和1 000時的求解概率和運行時間分別如圖9、10所示。從圖9可以看出，當Tmax充分大時，增加Tmax對算法的求解性能的影響并不大。但是，從圖10可以看出，增加Tmax大大增加了算法求解時所消耗的時間。這是由于在約束緊度較大時增加回溯次數會導致無效回溯的發生，只消耗了運行時間卻沒有提高算法的求解性能。故在算法實驗中優化了Tmax這一參數，取值設定為500。

將ddeg-MAC、dom/ddeg-MAC回溯算法和BT算法及文獻［31］中提出的HBT算法進行了對比。HBT算法是一種基于靜態度的啟發式回溯算法。該算法先采用度啟發式的策略來確定待賦值變量的順序，然后利用最少約束值啟發式策略對選定的變量進行賦值，最后通過在有限的時間內進行回溯，得到變量的一組賦值。HBT、ddeg-MAC和dom/ddeg-MAC算法都是在變量賦值順序和變量如何取值這兩方面對經典的回溯算法進行優化。取N=60，這四種算法在求解RB模型時的成功概率如圖11所示。ddeg-MAC、dom/ddeg-MAC、HBT和BT算法的運行時間如圖12所示。HBT算法的終止條件回溯時間t=2 000 s，而其他三種算法的終止條件為達到最大回溯次數500。從圖中可以看出，HBT算法的時間復雜度高于其他三種算法，顯然dom/ddeg- MAC回溯算法在進入相變區域時表現出了最優越的求解性能，在最短的時間內最大地提高了求解概率。

ddeg-MAC和dom/ddeg-MAC回溯算法不僅可以用來求解具有增長取值域的隨機CSP，也可以用來求解具有固定取值域的隨機CSP，如經典二元CSP模型中的B模型。B模型可以用四元組〈N，d，p1，p2〉來表示，其中N表示變量數目，常數d表示每個變量的取值域。隨機選取p1C2N個二元約束組成B模型的一個隨機實例。對每個約束，隨機、不重復地選取p2d2個賦值對作為不協調賦值集合來限制變量的取值。在數值實驗中，在由〈N，10，0.1，p2〉生成的100個隨機實例運行dom/ddeg-MAC回溯算法。取N=20，60，100，對不同的p2，算法能成功找到解的概率（s）和運行時間（t）。如表2所示。當N較小時，dom/ddeg-MAC回溯算法能在較大的p2范圍內快速有效地找到問題的解。由于B模型具有平凡的漸近無解性，所以，隨著N的增大，算法可以求解的p2值逐步減小。

ddeg-MAC和dom/ddeg-MAC回溯算法可廣泛用于求解其他CSP，如以國際象棋為背景的N-皇后問題。取N∈［4，30］，ddeg-MAC、dom/ddeg-MAC和經典的回溯算法在100個問題上求解成功的概率和平均運行時間分別如圖13、14所示。從圖中可以看出，三種算法均能很快找到問題的解。其中dom/ddeg-MAC回溯算法在求解成功概率和運行時間上都表現出了相對優越的求解性能。

4 結束語

本文提出了兩種基于動態度的啟發式動態回溯算法來求解大值域的隨機CSP。這兩種算法分別按照變量的ddeg值和變量的dom/ddeg值來挑選變量進行深度優先的搜索，對選定的變量均按照其分量的AC支持數目之和降序排列進行賦值，當該變量的所有賦值無法使所有約束都被滿足時發生回溯。數值結果表明，dom/ddeg-MAC回溯算法表現出了相對優越的求解性能。在未來的研究中，可以將基于dom/ddeg挑選變量進行賦值的策略推廣到其他局部搜索算法上去，這對NP-完全問題的算法設計具有重要的意義。

參考文獻：

［1］Smith B M，Dyer M E.Locating the phase transition in binary constraint satisfaction problems［J］.Artificial Intelligence，1996，81（1-2）：155-181.

［2］Prosser P.An empirical study of phase transitions in binary constraint satisfaction problems［J］.Artificial Intelligence，1996，81（1-2）：81-109.

［3］Gent I P，Macintyre E，Prosser P，et al.Random constraint satisfaction：flaws and structure［J］.Constraints，2001，6（4）：345-372.

［4］Achlioptas D，Molloy M S O，Kirousis L M，et al.Random constraint satisfaction：a more accurate picture［J］.Constraints，2001，6（4）：329-344.

［5］Achlioptas D，Kirousis L M，Kranakis E，et al.Random constraint sa-tisfaction：a more accurate picture［C］//Proc of the 3rd International Conference on Principles and Practice of Constraint Programming.Berlin：Springer，1997：107-120.

［6］Xu Ke，Li Wei.Exact phase transitions in random constraint satisfaction problems［J］.Journal of Artificial Intelligence Research，2000，12（1）：93-103.

［7］Smith B M.Constructing an asymptotic phase transition in random binary constraint satisfaction problems［J］.Theoretical Computer Science，2001，265：265-283.

［8］Molloy M.Models for random constraint satisfaction problems［J］.SIAM Journal of Computing，2003，32（4）：935-949.

［9］Frieze A M，Molloy M.The satisfiability threshold for randomly generated binary constraint satisfaction problems［J］.Random Structure and Algorithms，2006，28（3）：323-339.

［10］Xu Ke，Li Wei.Many hard examples in exact phase transitions［J］.Theoretical Computer Science，2006，355（3）：291-302.

［11］Xu Ke，Boussemart F，Hemery F，et al.Random constraint satisfaction：easy generation of hard（satisfiable） instances［J］.Artificial Intelligence，2007，171（8/9）：514-534.

［12］Zhao Chunyan，Zheng Zhiming.Threshold behaviors of a random constraint satisfaction problem with exact phase transition［J］.Information Processing Letters，2011，111（20）：985-988.

［13］Fan Yun，Shen Jing.On the phase transitions of random k-constraint satisfaction problems［J］.Artificial Intelligence，2011，175（3-4）：914-927.

［14］Fan Yun，Shen Jing，Xu Ke.A general model and thresholds for random constraint satisfaction problems［J］.Artificial Intelligence，2012，193（12）：1-17.

［15］趙春艷，范如夢，劉雅楠.不同緊度下約束滿足問題的相變現象［J］.計算機應用研究，2020，37（9）：2739-2743. （Zhao Chunyan，Fan Rumeng，Liu Yanan.Phase transitions in random constraint satisfaction problem with various constraint tightness［J］.Application Research of Computers，2020，37（9）：2739-2743.）

［16］Zhao Chunyan，Zhou Haijun，Zheng Zhiming，et al.A message-passing approach to random constraint satisfaction problems with growing domains［J］.Journal of Statistical Mechanics：Theory and Experiment，2011，2011：P02019.

［17］趙春艷，鄭志明.一種基于變量熵求解約束滿足問題的置信傳播算法［J］.中國科學：信息科學，2012，42（9）：1170-1180. （Zhao Chunyan，Zheng Zhiming.A belief-propagation algorithm based on variable entropy for constraint satisfaction problems［J］.Scientia Sinica Informationis，2012，42（9）：1170-1180.）

［18］吳撥榮，趙春艷，原志強.置信傳播和模擬退火相結合求解約束滿足問題［J］.計算機應用研究，2019，36（5）：1297-1301. （Wu Borong，Zhao Chunyan，Yuan Zhiqiang.Combining belief propagation and simulated annealing to solve random satisfaction problems［J］.Application Research of Computers，2019，36（5）：1297-1301.）

［19］Zhao Chunyan，Fu Yanrong.Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains［J］.Journal of Statistical Mechanics：Theory and Experiment，2021（3）：033408.

［20］Golomb S W，Baumert L D.Backtrack programming［J］.Journal of the ACM，1965，12（4）：516-524.

［21］Freuder E C.A sufficient condition for backtrack-free search［J］.Journal of the ACM，1982，29（1）：24-32.

［22］Dechter R，Meiri I.Experimental evaluation of preprocessing algorithms for constraint satisfaction problems［J］.Artificial Intelligence，1994，68：211-241.

［23］Boussemart F，Hemery F，Lecoutre C，et al.Boosting systematic search by weighting constraints［C］//Proc of the 16th European Conference on Artificial Intelligence.Valencia，Spain：IOS Press，2004：146-150.

［24］Bessiere C，Regin J C.MAC and combined heuristics：two reasons to forsake FC（and CBJ？） on hard problems［C］//Proc of the 2nd International Conference on Principles and Practice of Constraint Programming.Berlin：Springer，1996：61-75.

［25］Mackworth A K.Consistency in networks of relations［J］.Artificial Intelligence，1977，8（1）：99-118.

［26］Sabin D，Freuder E C.Contradicting conventional wisdom in constraint satisfaction［C］//Proc of the 11th European Conference on Artificial Intelligence.Amsterdam：Wiley，1994：125-129.

［27］Prosser P.Domain filtering can degrade intelligent backtracking search［C］//Proc of International Joint Conference on Artificial Intelligence.San Francisco：Morgan Kaufmann Publishers，1993：262-267.

［28］Ginsberg M.L.Dynamic backtracking［J］.Artificial Intelligence，1993，1：25-46.

［29］Marino R，Parisi G，Ricci-Tersenghi F.The backtracking survey propagation algorithm for solving random K-SAT problem［J］.Nature Communications，2016，7：article No.12996.

［30］Li Hongbo，Liang Yanchun，Zhang Ning，et al.Improving degree-based variable ordering heuristics for solving constraint satisfaction problems［J］.Journal of Heuristics，2016，22（2）：125-145.

［31］范如夢，趙春艷，李飛龍.啟發式回溯算法求解約束滿足問題［J］.計算機應用研究，2021，38（5）：1438-1442. （Fan Rumeng，Zhao Chunyan，Li Feilong.Heuristic backtracking algorithm to solve constraint satisfaction problems［J］.Application Research of Computers，2021，38（5）：1438-1442.）