基于動(dòng)態(tài)度的回溯算法求解大值域約束滿(mǎn)足問(wèn)題

摘 要： 針對(duì)一個(gè)具有精確可滿(mǎn)足性相變現(xiàn)象的大值域隨機(jī)約束滿(mǎn)足問(wèn)題，提出了兩種啟發(fā)式動(dòng)態(tài)回溯算法，即基于動(dòng)態(tài)度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域與動(dòng)態(tài)度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。這兩種算法分別基于ddeg和dom/ddeg挑選變量，利用維持弧相容（MAC）技術(shù)為挑選的變量進(jìn)行賦值。當(dāng)賦值無(wú)法進(jìn)行時(shí)，再執(zhí)行動(dòng)態(tài)回溯修正變量的賦值。數(shù)值實(shí)驗(yàn)結(jié)果表明：在控制參數(shù)非常接近理論相變點(diǎn)時(shí)，算法仍然能夠有效地找到問(wèn)題的解。與經(jīng)典回溯算法相比，這兩種啟發(fā)式動(dòng)態(tài)回溯算法具有顯著的優(yōu)越性。

關(guān)鍵詞： 約束滿(mǎn)足問(wèn)題； 動(dòng)態(tài)度； 回溯算法； 維持弧相容

中圖分類(lèi)號(hào)： TP301.5"" 文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 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 引言

約束滿(mǎn)足問(wèn)題（constraint satisfaction problem，CSP）是人工智能領(lǐng)域中一個(gè)非常重要的問(wèn)題。近年來(lái)，已經(jīng)成為統(tǒng)計(jì)物理學(xué)、信息論和離散數(shù)學(xué)等交叉學(xué)科領(lǐng)域中的研究熱點(diǎn)之一。CSP在如人臉識(shí)別、物流調(diào)度、統(tǒng)籌規(guī)劃、配置問(wèn)題、視覺(jué)問(wèn)題和機(jī)器學(xué)習(xí)等實(shí)際問(wèn)題和工程技術(shù)中有著非常廣泛的應(yīng)用。

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

本文提出了兩種基于動(dòng)態(tài)度的啟發(fā)式回溯算法，即基于動(dòng)態(tài)度的ddeg-MAC回溯算法和基于值域與動(dòng)態(tài)度比值的dom/ddeg-MAC回溯算法來(lái)求解RB模型等一類(lèi)具有大值域的隨機(jī)CSP。這兩種算法分別基于ddeg值最大和dom/ddeg值最小來(lái)挑選變量，然后均利用MAC按照所挑選變量分量的AC支持個(gè)數(shù)從大到小的順序?qū)λ暨x的變量進(jìn)行賦值。如果發(fā)生沖突，則在最大回溯次數(shù)內(nèi)進(jìn)行回溯。

3 數(shù)值結(jié)果與算法分析

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

3.1 數(shù)值結(jié)果

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

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

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

3.2 算法分析

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

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

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

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

4 結(jié)束語(yǔ)

本文提出了兩種基于動(dòng)態(tài)度的啟發(fā)式動(dòng)態(tài)回溯算法來(lái)求解大值域的隨機(jī)CSP。這兩種算法分別按照變量的ddeg值和變量的dom/ddeg值來(lái)挑選變量進(jìn)行深度優(yōu)先的搜索，對(duì)選定的變量均按照其分量的AC支持?jǐn)?shù)目之和降序排列進(jìn)行賦值，當(dāng)該變量的所有賦值無(wú)法使所有約束都被滿(mǎn)足時(shí)發(fā)生回溯。數(shù)值結(jié)果表明，dom/ddeg-MAC回溯算法表現(xiàn)出了相對(duì)優(yōu)越的求解性能。在未來(lái)的研究中，可以將基于dom/ddeg挑選變量進(jìn)行賦值的策略推廣到其他局部搜索算法上去，這對(duì)NP-完全問(wèn)題的算法設(shè)計(jì)具有重要的意義。

參考文獻(xiàn)：

［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］趙春艷，范如夢(mèng)，劉雅楠.不同緊度下約束滿(mǎn)足問(wèn)題的相變現(xiàn)象［J］.計(jì)算機(jī)應(yīng)用研究，2020，37（9）：2739-2743. （Zhao Chunyan，F(xiàn)an 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］趙春艷，鄭志明.一種基于變量熵求解約束滿(mǎn)足問(wèn)題的置信傳播算法［J］.中國(guó)科學(xué)：信息科學(xué)，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］吳撥榮，趙春艷，原志強(qiáng).置信傳播和模擬退火相結(jié)合求解約束滿(mǎn)足問(wèn)題［J］.計(jì)算機(jī)應(yīng)用研究，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，F(xiàn)u 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，F(xiàn)reuder 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］范如夢(mèng)，趙春艷，李飛龍.啟發(fā)式回溯算法求解約束滿(mǎn)足問(wèn)題［J］.計(jì)算機(jī)應(yīng)用研究，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.）