兩種高效局部搜索算法求解RB模型實(shí)例

楊易 王曉峰 唐傲 彭慶媛 楊瀾 龐立超

摘 要：RB （revised B）模型是一種在約束可滿足問題中具備精確相變增長域的隨機(jī)實(shí)例模型，提出兩種高效的啟發(fā)式局部搜索算法用于解決RB模型生成的大值域約束可滿足問題。首先為基于權(quán)重指導(dǎo)搜索的W-MCH算法，該算法通過約束判斷和違反約束數(shù)計(jì)分來進(jìn)行搜索，并引入了基于約束違反概率的權(quán)重計(jì)算公式，根據(jù)其關(guān)聯(lián)的約束權(quán)重進(jìn)行修正，再對變量進(jìn)行迭代調(diào)整。然后提出最小化值域的MDMCH算法，該算法通過記錄違反約束和逐步消除已違反約束變量的啟發(fā)式策略來減少搜索空間，并在最小化后的變量域內(nèi)重新校準(zhǔn)變量賦值，進(jìn)而有效提高算法的收斂速度。此外，還提出了融入模擬退火策略的WSCH和MDSCH算法，這兩種算法都能根據(jù)變量的表征特點(diǎn)對變量域進(jìn)行針對性的搜索。實(shí)驗(yàn)結(jié)果表明，與多種啟發(fā)式算法相比，這兩種算法在精度與時間效率方面均呈現(xiàn)明顯提升，在復(fù)雜難解的實(shí)例中能夠提供高效的求解效率，驗(yàn)證了算法的有效性和優(yōu)越性。

關(guān)鍵詞：RB模型；約束滿足問題；局部搜索算法；模擬退火；最小沖突啟發(fā)式

中圖分類號：TP301?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號：1001-3695（2024）05-017-1394-08

doi： 10.19734/j.issn.1001-3695.2023.09.0415

Two efficient local search algorithms for solving RB model examples

Abstract：The RB （revised B） model is a stochastic instance model with an accurate phase change growth domain in constraint-satisfiable problems. This paper proposed two efficient heuristic local search algorithms to solve the large-value domain constraints generated by the RB model. The first is the W-MCH algorithm based on weight-guided search. This algorithm searched through constraint judgment and constraint violation score， and introduced a weight calculation formula based on constraint violation probability， which was modified according to its associated constraint weight， and iteratively adjusted then variables. Then it proposed the MDMCH algorithm for minimizing the value range， this algorithm reduced the search space by recording the heuristic strategy of constraint violations and gradually eliminating the violated constraint variables， and recalibrated the variable assignments within the minimized variable domain， thereby effectively improving the algorithms convergence speed. In addition， it also proposed the WSCH and MDSCH algorithms that incorporate simulated annealing strategies. Both algorithms can perform targeted searches in the variable domain based on the characterization characteristics of the variables. Experimental results show that compared with various heuristic algorithms， these two algorithms have significantly improved accuracy and time efficiency， and can provide efficient solution efficiency in complex and difficult instances， verifying the effectiveness and superiority of the algorithms.

Key words：RB model; constraint satisfaction problem; local search algorithm; simulated annealing; minimum conflict heuristic

0 引言

約束可滿足問題（constraint satisfiability problem，CSP）作為人工智能科學(xué)領(lǐng)域的一個關(guān)鍵研究方向，在實(shí)際優(yōu)化問題中具有重要地位。許多現(xiàn)實(shí)世界中的優(yōu)化難題都能以CSP形式建模，這使得CSP通過不同編碼方式的可滿足性判定問題（satisfiability，SAT）公式相對于隨機(jī)SAT公式更自然地刻畫了約束之間的關(guān)系。約束編程在諸如機(jī)器設(shè)計(jì)［1］、電路設(shè)計(jì)［2］、汽車變速器設(shè)計(jì)［3］、調(diào)度與規(guī)劃［4］等領(lǐng)域得到成功應(yīng)用。因此，對CSP的深入研究變得愈加意義非凡。在CSP的生成模型、可滿足性相變和求解算法等方面，學(xué)者們都展開廣泛探討。最初，Achlioptas等人［5］發(fā)現(xiàn)了CSP的A、B、C、D四種初始模型存在嚴(yán)重缺陷，隨著變量數(shù)量的增加，并沒有出現(xiàn)漸進(jìn)性的相變現(xiàn)象，即平凡漸進(jìn)不可滿足性。為了彌補(bǔ)這些傳統(tǒng)模型的不足，E模型［5］和廣義模型［6］相繼被提出。然而，E模型無法靈活地調(diào)整實(shí)例的密度，而廣義模型則在引入概率分布后變得復(fù)雜。隨后，Xu等人［7］在2000年提出了一種新的隨機(jī)CSP模型，名為RB（revised B）模型。RB模型以其精確的相變特性，成為了一種增長域?qū)嵗Ｐ?，完美地彌補(bǔ)了前述模型的不足。此后，F(xiàn)an等人于2011年在RB模型基礎(chǔ)上提出了K-CSP［8］和d-K-CSP［9］兩個改進(jìn)模型。趙春艷等人［10］則提出了p-RB模型。盡管這些模型都是基于RB模型的改進(jìn)，但都存在一定的局限性。Huang等人［11］通過一階矩方式，推導(dǎo)出以RB模型生成的Max-CSP和Min-CSP的上下限。Xu等人［12］采用嚴(yán)格的一階和二階矩方法，證明了在可解階段接近可滿足的轉(zhuǎn)變，解會以指數(shù)數(shù)量的良好分離簇的形式聚合，每個簇包含亞指數(shù)數(shù)量的解，呈現(xiàn)出了聚類動態(tài)躍遷，而不是凝聚躍遷。最近，Zhou 等人［13］研究了模型RB的強(qiáng)制實(shí)例空間，并嚴(yán)格地證明了RB實(shí)例強(qiáng)迫解的期望數(shù)目與非強(qiáng)迫解的期望數(shù)目漸近相等。Xu等人［14］探究了RB模型解空間的結(jié)構(gòu)，發(fā)現(xiàn)隨著約束密度的增加，模型呈現(xiàn)出獨(dú)立相變、聚類相變、可滿足性相變以及隔離相變四種相變特性。RB模型因其兼具上述模型的優(yōu)點(diǎn)并彌合其缺陷，被廣泛應(yīng)用于該領(lǐng)域。然而，RB模型生成隨機(jī)實(shí)例的求解難度在變量規(guī)模達(dá)到僅為102量級時變得極具挑戰(zhàn)性［15］。綜上所述，RB模型在CSP研究中扮演著重要角色，為該領(lǐng)域的研究人員提供了一種常用且多特性的隨機(jī)實(shí)例模型。

針對RB模型生成的大值域CSP實(shí)例的求解方法可以分為兩大類。首先是完備性算法，例如回溯技術(shù)、約束傳播和變量排序啟發(fā)式，這些方法雖然能確保解的準(zhǔn)確性，但在處理大規(guī)模的RB模型實(shí)例時，時間復(fù)雜度呈指數(shù)級增長；其次是不完備性算法，包括局部搜索、自然啟發(fā)式和近似概率求解。雖然這些方法可能無法獲得精確解，但它們旨在可接受的時間內(nèi)尋找近似解。2016年，王曉峰等人［16］探究了置信傳播算法在RB模型上的收斂性。同年，Xu等人［17］研究了局部搜索算法，提供了隨機(jī)游走算法的閾值界，并給出了隨機(jī)游走結(jié)合最小沖突啟發(fā)式算法。此外，2017年，原志強(qiáng)等人［18］引入了基于模擬退火的改進(jìn)方法RSA（revised simulated annealing algorithm）和結(jié)合遺傳算法的GSA（genetic simulated annealing algorithm），用于求解RB模型實(shí)例。2018年，Bouhouch等人［19］將二元CSP建模為0-1二次規(guī)劃，提出了基于離散化神經(jīng)網(wǎng)絡(luò)和局部搜索最小沖突啟發(fā)式MCH（minimum conflict heuristic algorithm）啟發(fā)式的方法，用于求解RB模型生成的二元CSP實(shí)例。2022年，Tnshoff等人［20］提出了一個可以訓(xùn)練的通用圖神經(jīng)網(wǎng)絡(luò)架構(gòu)作為任何約束滿足問題的搜索啟發(fā)式方法，通過實(shí)驗(yàn)證明該方法優(yōu)于神經(jīng)組合優(yōu)化。同年，Korani等人［21］提出兩種離散群智能算法離散母樹優(yōu)化（mother tree optimization，MTO）和離散的粒子群（discrete particle swarm optimization，PSO）求解RB模型生成的CSP實(shí)例。2023年，Hossain［22］根據(jù)CSP的約束條件對所有變量進(jìn)行變量排序的啟發(fā)式策略，求解CSP實(shí)例。

本文基于RB模型生成的CSP問題實(shí)例，對CSP中的最大約束可滿足問題（MAX-CSP）的求解算法進(jìn)行了深入研究。主要關(guān)注局部搜索算法，并提出了兩種高效的局部搜索算法：基于權(quán)重搜索的W-MCH（weight-based minimum conflict heuristic algorithm）局部搜索算法和最小化變量域的 MDMCH（minimizing variable domain-minimum conflict heuristic algorithm）算法。通過收斂性和求解效率等實(shí)驗(yàn)結(jié)果的驗(yàn)證，這兩種算法各自展現(xiàn)了獨(dú)特的優(yōu)勢。相較于MCH和WMCH（random walk minimum conflict heuristic algorithm），這兩種算法在收斂性上有了顯著提升。此外，在兩種局部搜索的基礎(chǔ)上提出了融入退火策略［18］的變體WSCH（weight-based simulated annealing minimum conflict heuristic algorithm）和MDSCH（minimizing variable domain simulated annealing minimum conflict heuristic algorithm）算法。而與文獻(xiàn)［17，18］中提到的RSA、GSA、WMCH等啟發(fā)式算法相比，這兩種算法在各變量規(guī)模上的求解時間至少縮短了30%，且在減少不可滿足約束數(shù)方面取得了顯著進(jìn)展。與多組啟發(fā)式算法相比，實(shí)驗(yàn)結(jié)果表明，這兩種局部搜索算法在求解RB模型生成的CSP實(shí)例時，呈現(xiàn)出高效的求解效率。

1 RB模型

RB模型是從著名的CSP模型B改進(jìn)而來，RB模型的一類隨機(jī)CSP實(shí)例表示為P∈RB{k，n，α，r，p}，其中對于每個實(shí)例的符號定義［11］如表1所示。由表1定義可以看出，隨著RB模型變量數(shù)xn的增長，取值域dn規(guī)模是呈多項(xiàng)式級增長。生成一個實(shí)例P∈RB（k，n，α，r，p），具體步驟如下：

a）設(shè)置模型RB的主要參數(shù)n、p、α和r。其中n是變量數(shù)量，p是約束緊度，r和α是兩個自定義的常數(shù)。

b）重復(fù)隨機(jī)選擇m個約束條件，每個約束都是通過從n個變量中獨(dú)立隨機(jī)地選擇k個變量形成。

c）對于每個約束C，從完整的dkn個賦值中隨機(jī)選取pdkn 種不同的k元賦值，形成一個不相容賦值的集合Qa，當(dāng)約束C的變量取值不屬于這些不相容賦值集合Qa時，該約束滿足。

在文獻(xiàn)［23］中給出控制參數(shù)p，臨界值pcr，可確定RB模型的可滿足性相變現(xiàn)象，并給出以下定理。

利用上述定理公式，根據(jù)RB模型的參數(shù)取值可確定出相變點(diǎn)pcr。更準(zhǔn)確地說，變量數(shù)接近無窮時，若ppcr，則CSP實(shí)例高概率接近0，無解。

2 局部搜索算法

2.1 MCH算法

局部搜索是解決約束滿足問題復(fù)雜計(jì)算組合問題的基本范式之一。盡管系統(tǒng)、完整的搜索算法已經(jīng)取得了進(jìn)步，但在大多情況下，局部搜索方法是解決這些大型復(fù)雜實(shí)例的優(yōu)秀可行方法。在解決CSP時，傳統(tǒng)的局部搜索算法通常從一個初始解s出發(fā)。在算法的迭代過程中，它會反復(fù)在當(dāng)前解的鄰域（s） 中尋找比當(dāng)前解更優(yōu)的解，并將找到的更優(yōu)解替代當(dāng)前解s*，直到在當(dāng)前鄰域（s）中無法找到比當(dāng)前解更好的解為止。如果在整個搜索過程中無法找到比解s*更優(yōu)的解，則該解被視為局部最優(yōu)解。

MCH迭代地修改單個變量的賦值，使違反約束的數(shù)量最小化。假設(shè)給定一個CSP實(shí)例P，通過為P中的每個變量賦值來初始化搜索過程，該值是從其域中統(tǒng)一隨機(jī)選擇的。在每個局部搜索步驟中，首先從沖突集中均勻地隨機(jī)選擇一個CSP變量x，然后從x的值域中選擇一個新值d，將d賦值變量x，使不滿足的約束沖突的數(shù)量最小化。如果有多個具有該屬性的沖突變量x值，則隨機(jī)選擇。當(dāng)找到解決方案或超過搜索步驟數(shù)限制時，終止搜索。這種傳統(tǒng)的局部搜索策略在尋找解決CSP的最優(yōu)解時，一般都是通過持續(xù)地在搜索空間中尋找更優(yōu)解，逐步單個地改善當(dāng)前解，以達(dá)到更好的問題解決效果。MCH求解RB模型實(shí)例的偽代碼如算法1。

算法1 MCH算法

2.2 W-MCH算法

與MCH算法不同，基于約束權(quán)重的概率選擇變量賦值的W-MCH算法是一種可變深度搜索策略，同時引導(dǎo)多個變量的搜索過程。在這一算法中，首先仍以CSP問題的違反約束記錄值作為算法的求解評價標(biāo)準(zhǔn)，即評估函數(shù)。對于RB模型實(shí)例，一組賦值解為X={x1，x2，…，xn}，對該組賦值進(jìn)行約束檢查，若違反約束時標(biāo)記1分，否則計(jì)0分。通過對一組賦值進(jìn)行約束檢查并計(jì)算評估分值，MAX-CSP問題的目標(biāo)在于最小化評估函數(shù)的目標(biāo)分值S，具體函數(shù)如下所示。

其中：m為約束的數(shù)量，通過檢查賦值是否滿足約束集Cm，使得評估分值S為0或最小，特別是在處理復(fù)雜實(shí)例的可滿足相變區(qū)域時，求解算法的主要目標(biāo)是在合理的時間范圍內(nèi)尋找到違反約束最少的解。

當(dāng)k=2，n=3，α=1，r=2，p=0.25時，考慮圖1中的RB模型實(shí)例P（k，n，α，r，p）。圖中綠色圈中，表示變量X={x1，x2，x3}，而紅色框中（參見電子版）表示的是變量約束，由r×n×ln n可得出約束數(shù)m為7，則約束C={c1，c2，…，c7} ，每個變量x映射的dn域大小為nα，計(jì)算結(jié)果為3，即值域d={0，1，2}，圖1中下方為不相容賦值Qa。W-MCH算法開始于隨機(jī)初始化多組解，并為每組解進(jìn)行評估得分。隨后，記錄初始賦值中得分最低的解，記為sol。假設(shè)初始解為sol={1，1，0}，接下來進(jìn)行約束檢查，以c1約束為例，涉及變量（x2，x3），當(dāng)x2賦值為1，x3賦值為0時，檢查其約束對應(yīng)的不相容賦值Q1={（1，2），（2，2）}，可以發(fā)現(xiàn)約束c1是滿足的，如圖1用實(shí)線表示滿足約束。依次檢查完所有的約束，在此實(shí)例中，初始解sol={1，1，0}違反約束c2、c3、c5，如圖1用虛線表示。同時，在檢查的過程中，初始化一個變量索引數(shù)組，記為C_values，在索引數(shù)組中存儲其違反約束的變量索引，如違反約束c2的變量對應(yīng)索引值為（1，2），累計(jì)存儲在C_values數(shù)組中。

此時，在MCH算法中的做法是記錄違反的不相容賦值中的Q，記為沖突集，對違反的單個變量進(jìn)行賦值修改。然而當(dāng)實(shí)例復(fù)雜時，MCH算法在單個變量上的修改可能效果有限。相比之下，W-MCH算法采用一種基于權(quán)重的方法，不同于MCH的是，W-MCH以C_values變量索引數(shù)組尋找其違反約束值，在每次循環(huán)中對賦值sol，通過權(quán)重指導(dǎo)實(shí)現(xiàn)多變量修改的算法策略。分析得到的索引變量集C_values，在該數(shù)組中發(fā)現(xiàn)索引的次數(shù)恰好代表了其變量的違反次數(shù)，故可對C_values進(jìn)行統(tǒng)計(jì)排序，并對應(yīng)地計(jì)算在數(shù)組中的占比概率pi。

pi=C（indexicount）/C_valueslength（4）

其中：C（indexicount）表示對應(yīng)索引值的計(jì)數(shù)頻次；C_valueslength為索引數(shù)組長度。事實(shí)上使用頻次計(jì)算出頻率pi或者其他概率，并不能有效地進(jìn)行概率選擇。原因是隨著變量的增加，單純的概率值并不能完全反映出變量的優(yōu)劣程度。如C_values中最大的P1 =0.5，但實(shí)際C_values數(shù)組中的x1已是最差的賦值變量。需要將概率值進(jìn)行映射以便更好地表征好壞程度，或者按照概率值的大小給予不同的權(quán)重來進(jìn)行選擇，對此提出了以下的權(quán)重公式。

其中：s=0.05為一個常數(shù)，控制著權(quán)重公式與映射曲率的大小，圖2為s取不同數(shù)值對其曲率的影響。由于s參數(shù)控制權(quán)重值的大小，又因在上述公式中，若indexicount值越大，表明當(dāng)前的賦值違反約束的數(shù)量越多，違反概率也相應(yīng)增大，所以需要更大的權(quán)重值來調(diào)整當(dāng)前賦值中的差值變量。理論上，當(dāng)存在概率值時，都必須修改違反約束的變量，然而變量之間的相互約束，必須固定一部分違反約束較少的賦值變量，對于違反約束多的賦值，使之以更高的權(quán)重去修改變量賦值。然而整體權(quán)重值不能過大，以免導(dǎo)致算法過于隨機(jī)化。經(jīng)過多次實(shí)驗(yàn)和分析，取參數(shù)值s=0.05。由于權(quán)重值是以約束的違反概率進(jìn)行計(jì)算的，所以并不會影響變量修正的準(zhǔn)確性，可以看出，隨著變量數(shù)的增加，C_valueslength的違反約束數(shù)也會增加，當(dāng)indexicount=0，即違反約束為0時，權(quán)重也為0，而當(dāng)約束違反時，權(quán)重也會隨之增加。但當(dāng)變量增多時，整體的權(quán)重值在迭代修正后會陷入一個局部值，從而影響算法的收斂速度。利用此策略得到一組最優(yōu)賦值后再利用MCH算法，所以此操作并不會影響算法的準(zhǔn)確性。如在圖1 C_values中，變量x1的賦值違反約束頻次為index1count=3，同理index2count=2，index3count=1，代入上述公式可以計(jì)算出weight1=0.99，weight2=0.96，weight3=0.56。以此權(quán)重對sol的所有變量重新賦值，假設(shè)賦值x1=2，x2=0，x3未能修改，則得到的解為solbest={2，0，0}，重新檢查約束集，則只有c3和c6違反，重復(fù)上述操作即可有效地降低算法的違反約束。

從圖2中可以看出，實(shí)際上在當(dāng)Pi>20% 時，權(quán)重已經(jīng)大于0.6，能滿足大多數(shù)違反變量的修改，在實(shí)際操作中若以weight>0 時的權(quán)重賦值，會造成算法過于隨機(jī)化，導(dǎo)致算法不能有效收斂。當(dāng)weight為0.3左右時，變量的原始概率值基本處于5%之上，為了使初始權(quán)重大多數(shù)變量都能被優(yōu)化，則取weight>30%為每次迭代的賦值概率。

Q1={（1，2），（2，2）}，Q2={（0，0），（1，1）};

Q3={（1，1），（2，0）}，Q4={（2，1），（1，1）};

Q5={（1，0），（2，2）}，Q6={（0，1），（0，0）};

Q7={（1，2），（2，1）}

C_values=［1，2，1，2，1，3］

為了驗(yàn)證以上取值，分析算法的權(quán)重初始值與迭代后的權(quán)重值。在圖3中可以看出變量數(shù)n=100，在經(jīng)過200次迭代計(jì)算，得到的藍(lán)色區(qū)域（參見電子版）為迭代后的權(quán)重與初始權(quán)重的差值，可以看到，經(jīng)過權(quán)重指導(dǎo)搜索后，絕大多數(shù)變量的權(quán)重已經(jīng)小于初始權(quán)重值。此操作可以根據(jù)權(quán)重的不同分配，對不同的概率值造成不同程度的影響，從而實(shí)現(xiàn)根據(jù)權(quán)重調(diào)整的效果。經(jīng)過權(quán)重調(diào)整后，可以得到一組優(yōu)秀賦值解，再以MCH算法逐步搜尋單個變量進(jìn)行修改。W-MCH算法的偽代碼如算法2所示。

算法2 W-MCH算法

2.3 MDMCH算法

若能以高效策略為MCH算法提高一組出色的起始賦值，那么在相變區(qū)域內(nèi)或許將獲得優(yōu)越的可行解。在分析W-MCH算法的權(quán)重圖之后，可觀察到在迭代之末，大約有20%的權(quán)重值仍保持較高水平。然而，對于這些過于突出的權(quán)重值，有時一個變量可能違反多個約束。為解決這一問題，引入MDMCH算法，此算法基于權(quán)重思想構(gòu)建，旨在通過消除違反約束的變量，從而有力地縮減搜索空間。

首先同W-MCH算法初始步驟基本一致，先進(jìn)行初始的約束檢查，記錄C_values數(shù)組，同時記錄沖突變量集Qc，但MDMCH算法對于沖突集Qc的處理方式與MCH算法不同，MCH是在沖突集Qc中隨機(jī)選擇變量進(jìn)行變量修改，最小化沖突數(shù)量。而MDMCH算法是在沖突集中尋找變量對應(yīng)的違反變量值，然后將尋找出的變量與變量值累計(jì)存儲到Q_values數(shù)組中。如圖4所示，假設(shè)現(xiàn)在初始賦值還是sol={1，1，0}?？蓹z查出每個變量的違反約束值，在該組賦值中，x1、x2、x3三個變量取值都與約束沖突。然后將沖突值依次在各自的變量域中消除沖突的變量，分別得到變量域dom（x1）=（0，2），dom（x2）=（0，2），dom（x3）=（0，1），再利用權(quán)重公式進(jìn)行指導(dǎo)搜索。通過權(quán)重值和消除后的各個變量域，可計(jì)算出此操作后的搜索空間為2×0.99×2×0.96×2×0.56≈4.25，而最初的基本搜索空間為33，此實(shí)例中搜索空間降低了85%。假設(shè)變量數(shù)為n，對應(yīng)的變量域?yàn)閐，而對應(yīng)每個變量域消除的沖突變量數(shù)為ai（a∈d－1），每個對應(yīng)的修改權(quán)重為wi，可計(jì)算出最小化值域與搜索空間dn的有效比值，計(jì)算公式如下：

若以各自的權(quán)重得到新賦值solbest={0，2，0}，并未違反約束進(jìn)而高效地尋找出可行解。在最小化值域的策略中，每次消除的變量都是在隨機(jī)初始賦值的基礎(chǔ)上找出違反約束的賦值變量進(jìn)行消除。每次消除違反賦值變量后，在剩余的值域內(nèi)進(jìn)行重新賦值。顯然，由于變量之間的相互約束性，此操作一定會過于刪除搜索空間，導(dǎo)致無法針對性求解，但會加快尋找局部最優(yōu)解的速度；然而在簡單易解實(shí)例上，容易陷入局部最優(yōu)；相反，在難解實(shí)例上，能高效地降低違反約束數(shù)，但在迭代后期也會陷入局部最優(yōu)。雖然最小化值域的策略充分地減少了搜索空間，導(dǎo)致無法精確求解，但此操作的目的并不是最終求解，而是快速地得到一組較優(yōu)賦值，在此賦值的基礎(chǔ)上再利用MCH算法在整個搜索空間進(jìn)行針對性的精確搜索，不但不會影響MDMCH算法的精確性，反而這一策略加快了算法的收斂速度。由于在循環(huán)消除變量域的過程中，此操作無法考慮多組變量之間的約束相互影響的變量域，所以當(dāng)變量增加時，在實(shí)驗(yàn)中發(fā)現(xiàn)變量域中會被消除為空，這也是導(dǎo)致在此操作陷入局部最優(yōu)的一個原因，這時取當(dāng)前變量域中違反約束最小的賦值解，記為當(dāng)前最優(yōu)解。對此，以0.2的概率對變量域?yàn)榭盏淖兞吭谄湓械淖兞坑蛑羞M(jìn)行隨機(jī)賦值，跳出局部最優(yōu)值，然后進(jìn)行MCH算法的單個變量尋優(yōu)。最后，通過權(quán)重差值實(shí)驗(yàn)發(fā)現(xiàn)，同樣對100個變量進(jìn)行200次迭代，分析初始權(quán)重，與迭代末的權(quán)重進(jìn)行對比。權(quán)重值的優(yōu)化如圖5所示，可以看出，MDMCH算法只有極個別權(quán)重值超過了初始權(quán)重值，對于大多數(shù)權(quán)重值都進(jìn)行了優(yōu)化處理。該操作利用最小化變量域的方式，極大地增強(qiáng)了算法的局部搜索能力。MDMCH算法的偽代碼如算法3所示。

算法3 MDMCH算法

2.4 WSCH與MDSCH算法

由于在后期的搜尋中，基于權(quán)重和最小化值域的兩種算法策略都會縮小搜索空間，陷入局部最優(yōu)，而MCH算法的收斂效果較差。故而在W-MCH與MDMCH迭代后尋得一組最優(yōu)賦值，可融入模擬退火策略的MCH算法再進(jìn)行尋優(yōu)，并以1-3/T的概率進(jìn)行選擇擾動，利用最小約束數(shù)及當(dāng)前退火溫度T以 exp［－（Fnow－Fbest）］ 概率來接受新的賦值，在退火初期，需要使賦值進(jìn)行擾動后接受新賦值的概率較大。此賦值在大范圍的賦值空間中對變量賦值能夠進(jìn)行隨機(jī)擾動。在退火后期，隨著T值的減少，擾動概率減小，則對較優(yōu)賦值進(jìn)行針對性擾動。這樣在求解實(shí)例時，開始退火時期算法有優(yōu)秀的能力來逃避局部最優(yōu)值，從而快速找到簡單實(shí)例解。在求解復(fù)雜實(shí)例時，前期雖然過于隨機(jī)化，但隨著退火溫度的下降，算法在退火后期又可以進(jìn)行針對性的尋優(yōu)。避免以傳統(tǒng)退火策略中盲目性的隨機(jī)擾動降低求解效率，以此來提升算法的求解精度。引入退火策略算法具體的WSCH與MDSCH偽代碼如算法4。

算法4 WSCH、MDSCH算法

2.5 算法時間復(fù)雜度分析

兩種改進(jìn)的局部搜索策略中都涉及到了約束檢查與后續(xù)MCH算法的尋優(yōu)，對此首先分析約束檢查的時間復(fù)雜度，在W-MCH算法迭代的主循環(huán)內(nèi)部會依次遍歷其約束數(shù)m，則時間復(fù)雜度為O（m）。對于內(nèi)部約束檢查中每次在解sol中取出k個變量x的時間復(fù)雜度為O（k） ，然后將取出的變量與每組約束C中的t個具體約束集進(jìn)行判斷的時間復(fù)雜度為O（t），該操作的時間復(fù)雜度為O（m×k×t）。即約束檢查的時間復(fù)雜度為

T1（m，t，k）=O（m×t×k）（7）

而約束數(shù)r×n×ln n=m，pdkN=t，dN=nα，則T1為

記錄索引數(shù)組與權(quán)重計(jì)算涉及的操作相對較少，從約束集中取出不滿足約束索引為O（k），而對于C_values數(shù)組索引排序的最大操作時間復(fù)雜度為數(shù)組長度，與賦值操作都為常數(shù)級。

MCH算法的時間復(fù)雜度主要取決于兩個因素。首先是算法的迭代次數(shù)，算法通過迭代多次來尋找解，迭代次數(shù)可以通過設(shè)置參數(shù)來控制。通常情況下，迭代次數(shù)與問題的規(guī)模和復(fù)雜性無關(guān)，因此可以視為常數(shù)。其次是單次迭代中的局部搜索復(fù)雜度和沖突減少的效率與具體問題局部搜索實(shí)現(xiàn)算法相關(guān)。

綜合考慮以上因素，最小沖突啟發(fā)式算法的時間復(fù)雜度可以表示為

T2（n）=O（f（n，M，m））（9）

其中：n為問題規(guī)模；M為迭代次數(shù)；m為局部搜索的復(fù)雜度，而MCH的局部搜索主層循環(huán)時間復(fù)雜度為O（maxSteps），內(nèi)部搜索操作的搜索復(fù)雜度和沖突減少的效率主要取決于循環(huán)中約束檢查不滿足變量的時間復(fù)雜度T1，而對于每次變量修改的時間復(fù)雜度為O（k），所以MCH的時間復(fù)雜度為

T3（maxSteps，T1）=O（maxSteps×T1×k）（10）

MDMCH比W-MCH算法多一步消除變量域的中間處理操作，實(shí)際處理的主要時間復(fù)雜度為O（nα），而nα為變量域的大小，為常數(shù)級。兩種局部搜索的主要時間復(fù)雜度都為

WSCH與MDSCH算法外層循環(huán)主要為降溫次數(shù)，時間復(fù)雜度為O（log（T0/T）） ，內(nèi)層循環(huán)為嘗試產(chǎn)生新的解并決定是否接受新解，主要的迭代次數(shù)由馬爾可夫鏈長度L參數(shù)控制，約束檢查與上述復(fù)雜度T1一致。兩類變體算法的主要時間復(fù)雜度為

T5（T0，T，L，T1）=O（log（T0/T）×L×T1×k）（12）

由于RB模型為二元約束，k為常數(shù)取2，其中α取0.8，r和約束緊密度P為常數(shù)。即當(dāng)RB模型參數(shù)確定時， 兩種局部搜索W-MCH、MDMCH與兩種退火策略的WSCH與MDSCH變體算法的主要復(fù)雜度為T=O（n×ln n）。

3 實(shí)驗(yàn)分析

為了驗(yàn)證基于權(quán)重和最小化值域兩種算法策略的效率，分別進(jìn)行了收斂性與求解概率實(shí)驗(yàn)。此次實(shí)驗(yàn)取文獻(xiàn)［17，18，24～27］中參數(shù)明確，且為同類型的隨機(jī)啟發(fā)式算法作為對比實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為Windows 11，64位操作系統(tǒng)，CPU為AMD Ryzen 7 5800H，主頻為3.20 GHz，內(nèi)存16 GB；RB模型參數(shù)取與文獻(xiàn)［18］中相同的參數(shù)，k=2，α=0.8，r=3，n=［20∶20∶100］由定理1計(jì)算，可滿足性相變點(diǎn)為Pcr=0.234。對于不同的n取約束密度p=［0∶0.01∶0.2］，由上述數(shù)值生成的RB模型的具體參數(shù)如表2所示。

3.1 收斂性分析

首先，對W-MCH、MDMCH與MCH，和文獻(xiàn)［17］中隨機(jī)游走最小沖突啟發(fā)式WMCH算法的收斂曲線進(jìn)行對比分析。隨后與文獻(xiàn)［18］中RSA和GSA算法進(jìn)行收斂曲線對比，而GSA和RSA算法都是以退火策略為循環(huán)。由于迭代次數(shù)與RSA和GSA不一致，為了方便比較，實(shí)驗(yàn)的收斂性比較以時間為橫軸。

在圖6（a）～（d）中，分別展示了這四種算法隨著變量數(shù)和約束密度的增加，其收斂曲線的變化趨勢。在圖6（a）中，展示了變量數(shù)n=20 以及約束密度p=0.14時的收斂曲線。在這種情況下，WMCH表現(xiàn)出最佳的收斂性能。這歸因于隨機(jī)游走搜索方法的盲目性，使其在簡單實(shí)例上尋找可行解空間時的表現(xiàn)較優(yōu)。盡管期望步數(shù)在隨機(jī)給定初始分配后非常大，即（1-p）-rnln n，但WMCH在一定概率下執(zhí)行隨機(jī)游走，具有一定程度跳出局部最優(yōu)的效果，因此，在較為簡單的實(shí)例中，WMCH的優(yōu)越性明顯。而W-MCH與MDMCH表現(xiàn)一般，由于在本身策略下縮小解空間，得到的一組較優(yōu)賦值后再由MCH算法處理，與MCH、WMCH在簡單實(shí)例上隨機(jī)賦值相比有一定的隨機(jī)性，當(dāng)WMCH與W-MCH和MDMCH的初始賦值違反約束數(shù)相差不大時，相對于WMCH與MCH，W-MCH與MDMCH增加了算法的復(fù)雜度，故收斂性較差。

不過隨機(jī)實(shí)例的復(fù)雜性上升，在n=60，p=0.14時，兩種局部搜索的搜索優(yōu)勢體現(xiàn)出來，在圖6（b）中可以看到，W-MCH的收斂速度最快，在100次迭代后，最小不可滿足約束數(shù)相對比于MCH、WMCH與MDMCH至少降低了34%左右。而WMCH有一定概率的隨機(jī)游走步驟，在實(shí)例稍復(fù)雜時，則是四種算法中收斂速度最差的。值得注意的是，在較復(fù)雜的實(shí)例中，MDMCH算法的效率與MCH、WMCH相當(dāng)，這是因?yàn)槠渲羞`反約束的數(shù)量相對較少，約束密度較小導(dǎo)致的不相容賦值稀疏，indexicount 違反的頻次與C_valueslength的比值較小，處于一個權(quán)重低位值，然而此實(shí)例下也不是難解實(shí)例，復(fù)雜約束較少，故最小化值域策略的效果不明顯。

進(jìn)一步增加模型實(shí)例的復(fù)雜度，當(dāng)n=100和p=0.14 時，兩種局部搜索方法的收斂速度顯著增快，如圖6（c）所示，大約在50次迭代后，這兩種方法的最少不可滿足約束數(shù)位于［40，60］，而MCH和WMCH算法的最少不可滿足約束數(shù)則在［130，140］。在相同的迭代次數(shù)下，相對于其他三種算法最少不可滿足約束數(shù)至少降低了70%。在此實(shí)例下，MDMCH算法的優(yōu)勢十分明顯，其最小化變量域的策略有助于更快地獲得一組初始賦值，加快算法的收斂速度。此外，隨著實(shí)例的復(fù)雜程度增加，似乎在接近實(shí)例的可滿足相變點(diǎn)附近，MDMCH算法更具有快速收斂的趨勢。對于最具挑戰(zhàn)性的實(shí)例，即n=100和p=0.20 的情況下，復(fù)雜約束增大，如圖6（d）所示，MDMCH算法在難解實(shí)例上的收斂速度最佳，這是由于無論算法處于哪種實(shí)例，在每次迭代求解中，C_valueslength 為一次約束檢查數(shù)組長度的定值，然而當(dāng)實(shí)例復(fù)雜時，即weight 與indexicount成正比，若賦值變量的違反約束數(shù)越大，則導(dǎo)致該變量的indexicount越大，則權(quán)重的值也相應(yīng)增大，故而在復(fù)雜難解實(shí)例上算法的收斂速度越快，而實(shí)例簡單時，該值影響的權(quán)重值較小，故而收斂速度無難解實(shí)例上那樣明顯，但由于變量約束的相互影響，又不能將概率權(quán)重映射過度放大，會造成多組賦值變量都需要以高權(quán)重進(jìn)行修正，導(dǎo)致算法難以收斂，而該組實(shí)驗(yàn)的收斂圖像正好驗(yàn)證了筆者的預(yù)期。需要指出的是，MDMCH算法引入了0.2概率的隨機(jī)賦值策略，從而在對比實(shí)驗(yàn)圖（b）～（d）中復(fù)雜實(shí)例上的MDMCH算法的最少不滿足約束數(shù)最小。

圖6（e）（f）分別為n=60，p=0.14和n=100，p=0.14引入退火策略的兩種算法與GSA和RSA算法的時間收斂對比?？梢钥闯?，融入基于權(quán)重搜索和最小化值域搜索策略的WSCH與MDSCH算法能迅速收斂到局部最優(yōu)值，在圖6（e）中兩種算法在10 s之內(nèi)已達(dá)到個位數(shù)的最少不可滿足約束數(shù)，比其他兩種算法的時間效率最高提升70%，進(jìn)而有效地給退火策略的MCH提供一組有效賦值，能盡早地搜索最優(yōu)解。隨著實(shí)例的復(fù)雜度增加，在圖6（f）中，WSCH與MDSCH算法的收斂速度似乎更加明顯，而MDSCH相比于其他三種算法能更早地跳出局部最優(yōu)，收斂速度大幅提升。此實(shí)驗(yàn)中更加清晰地驗(yàn)證了兩種改進(jìn)方法對于變量迭代修正的效率遠(yuǎn)遠(yuǎn)高于RSA、GSA、MCH和WMCH改進(jìn)算法。

3.2 求解效率對比分析

圖7中分別對比WSCH、MDSCH算法與RSA、GSA在RB模型各維度10組實(shí)例上的求解概率。圖7（a）～（d）分別展示了RSA、GSA、WSCH和MDSCH四種算法在不同約束密度下的收斂概率。其中RSA在p≤0.07時，GSA在p≤0.1時兩種算法在各組RB模型變量實(shí)例上以概率1收斂，W-SCH在p≤0.11時以概率1收斂，而MDSCH在p≤0.12時可有效求解。在低維實(shí)例上n為20、40時，WSCH表現(xiàn)出最佳的求解效率，在相變區(qū)域內(nèi)依然有高概率可解，其次為MDSCH，在變量n取20，WSCH和MDSCH算法求解概率的約束密度p都達(dá)到了0.16，RSA與GSA算法分別為0.1和0.13。WSCH和GSA算法在臨近相變點(diǎn)0.20時依然有0.1概率求解，但求解概率高于GSA。在變量n取40時，MDSCH在p取0.14，0.15 時，求解概率分別為0.9和0.5，WSCH求解概率都為0.6，RSA和GSA算法分別在p取0.14和0.15時失效，而MDSCH和WSCH算法的求解概率分別達(dá)到了0.16和0.17。綜上分析，在低維實(shí)例上，WSCH稍優(yōu)于MDSCH，兩種算法都優(yōu)于RSA和GSA的求解效率。隨著實(shí)例變得復(fù)雜，MDSCH的求解能力在n取60、80、100的高維實(shí)例上體現(xiàn)了出來。在n為60時，WSCH在p=0.15 有0.1的概率收斂，而MDSCH算法有0.5的概率收斂，RSA和GSA求解失敗。在n取80時，WSCH在p=0.14有0.3的概率求解，RSA和GSA均已失效，而MDSCH依然有0.6的高概率求解。MDSCH在n取100時，將求解概率的約束密度提升到了0.12。綜合分析實(shí)驗(yàn)結(jié)果，相比于其他三類算法，MDSCH在高維復(fù)雜實(shí)例上表現(xiàn)出色，其求解概率均高于對比算法，與此同時，WSCH在低維實(shí)例中表現(xiàn)出了良好的性能。

圖8中對比了四種算法在不同變量規(guī)模下的總運(yùn)行時間。可以觀察到，每個規(guī)模下MDSCH和WSCH算法的總運(yùn)行時間都明顯優(yōu)于GSA和RSA算法，時間效率最大提升了50%左右。值得注意的是，隨著變量規(guī)模的增加，尤其是在復(fù)雜可解實(shí)例中，MDSCH的時間效率開始優(yōu)于WSCH算法，MDSCH的最小化值域策略開始發(fā)揮作用，這使得它能更快地為退火策略的MCH算法提供一組出色的賦值，從而提高了求解的時間效率。綜上所述，MDSCH和WSCH算法在不同規(guī)模的變量下都表現(xiàn)出良好的性能，特別是在高維度和復(fù)雜實(shí)例中，MDSCH算法在求解效率方面表現(xiàn)出色。

為了進(jìn)一步驗(yàn)證WSCH和MDSCH算法的有效性，圖9（a）（b）分別在變量n取80、100，約束密度為［0.11，0.17］，進(jìn)行50個隨機(jī)實(shí)例的求解概率對比。其中BP-RSA-1（belief propagation-revised simulated annealing algorithm-1）［24］、 BP-RSA-2（belief propagation-revised simulated annealing algorithm-2）［24］、禁忌搜索TS（Tabu search）［25］、TS-SA（Tabu search-simulated annealing algorithm）［25］都為啟發(fā)式隨機(jī)搜索算法。而回溯BT（backtracking algorithm）［26］、基于度啟發(fā)式的HBT（heuristic backtracking algorithm）［26］、動態(tài)度的ddeg-MAC（dynamic degree-maintaining arc consistency）［27］都為基于回溯的完備性求解算法，基礎(chǔ)的BT與TS算法在高維難解

實(shí)例中并不具有求解能力。從圖9（a）可以看到，當(dāng)變量取80時，WSCH與MDSCH在同組算法中，p為0.12～0.14時展現(xiàn)的高概率求解，均優(yōu)于對比算法，在p=0.14時，表現(xiàn)最好的MDSCH與對比算法中最優(yōu)的BP-RSA-2相比，求解概率高出32%。而在p>0.14時，由于實(shí)例的復(fù)雜度增加，各算法均不能高效求解。如圖9（b），當(dāng)變量n取100，在p=0.14時，實(shí)例的復(fù)雜度上升，MDSCH算法稍弱于BP-RSA-2、HBT。在p=0.13時，WSCH求解概率僅次于MDSCH，而MDSCH與對比算法中最優(yōu)的TS-SA相比，求解概率高出16%。在變量n取100時，MDSCH算法在p=0.12時以概率1求解，為所有對比算法中最佳值。而無論變量n取80、100，在p取0.11、0.12時，兩種算法的求解效率均表現(xiàn)最佳。綜上分析，WSCH與MDSCH算法在高維難解實(shí)例中，對比各類啟發(fā)式算法表現(xiàn)出了高效的求解性能。

表3為RSA、GSA、WSCH和MDSCH四種算法在隨機(jī)的RB模型實(shí)例上，在各變量維度中分別運(yùn)行10次，取約束密度0.16～0.20在接近可滿足性相變的實(shí)驗(yàn)結(jié)果。ANVC表示平均不可滿足約束數(shù)，time為平均運(yùn)行時間。在平均運(yùn)行時間方面，對于復(fù)雜且難解的RB模型實(shí)例，WSCH和MDSCH算法的運(yùn)行時間基本相當(dāng)，相比之下，RSA和GSA算法的平均運(yùn)行時間至少增加了近30%。在不可滿足約束數(shù)量方面，當(dāng)變量維度較低（如n 取20或40）時，WSCH表現(xiàn)最佳。但在高維實(shí)例中，尤其是在變量維度較高（如n取60、80或100）且實(shí)例較復(fù)雜的情況下，MDSCH表現(xiàn)出色。值得注意的是，在復(fù)雜但可解的區(qū)域中，當(dāng)約束密度為0.16時，MDSCH的平均不可滿足約束數(shù)量提高的效率最多。綜上所述，這些實(shí)驗(yàn)結(jié)果表明，MDSCH在高維度和復(fù)雜RB模型實(shí)例上的性能表現(xiàn)優(yōu)越，特別是在可滿足性相變點(diǎn)附近的情況下，其平均不可滿足約束數(shù)量顯著減少。

4 結(jié)束語

對大值域CSP的求解探索是極其有意義的，如在一些實(shí)際應(yīng)用中，CSP的問題參數(shù)如域大小、變量數(shù)量、約束數(shù)量等可能不確定，RB模型可以用于生成多個實(shí)例，以測試不同參數(shù)下算法的表現(xiàn)。通過分析在不同參數(shù)配置下算法的性能表現(xiàn)，為實(shí)際應(yīng)用中的問題選擇最佳參數(shù)設(shè)置以提高問題求解的效率和準(zhǔn)確性。其次在自動化調(diào)度和資源分配問題中，RB模型可用于生成不同場景下的調(diào)度問題，這有助于評估自動化調(diào)度算法在處理多種不同場景下的性能。通過對多個場景下的調(diào)度問題進(jìn)行建模和求解，可以優(yōu)化資源分配，提高效率，最大程度減少成本。 本文提出了基于權(quán)重指導(dǎo)搜索的W-MCH和最小化值域MDMCH的兩種局部搜索方式，顯著提高了MCH算法在整體規(guī)模接近可滿足相變區(qū)域的求解效率。此外，融入退火策略的WSCH和MDSCH算法進(jìn)一步增強(qiáng)了算法的局部搜索能力。這些算法在求解RB模型生成的CSP問題實(shí)例方面表現(xiàn)出色，尤其在高約束密度和復(fù)雜性下具有明顯的優(yōu)勢。然而，這些算法仍有待優(yōu)化。例如，對于高維實(shí)例，可以進(jìn)一步優(yōu)化權(quán)重處理，采用自適應(yīng)權(quán)重調(diào)整策略，在迭代一定次數(shù)后重新映射各個變量的權(quán)重，實(shí)現(xiàn)更精確的搜索引導(dǎo)。未來的研究可以繼續(xù)探索這些算法在其他領(lǐng)域的應(yīng)用，并優(yōu)化它們以提高求解效率。

參考文獻(xiàn)：

［1］Frayman F，Mittal S. COSSACK： a constraint-based expert system for configuration tasks［M］//Knowledge-Based Expert Systems in Engineering： Planning and Design.Berlin：Springer，1987： 143-166.

［2］De Kleer J，Sussman G J. Propagation of constraints applied to circuit synthesis［J］. International Journal of Circuit Theory and Applications，1980，8（2）： 127-144.

［3］Nadel B A，Lin J. Automobile transmission design as a constraint satisfaction problem： modelling the kinematic level［J］. AI EDAM，1991，5（3）： 137-171.

［4］Mackworth A K. On seeing things，again［C］//Proc of IJCAI. 1983： 1187-1191.

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

［6］Molloy M. Models and thresholds for random constraint satisfaction problems［C］//Proc of the 34th Annual ACM Symposium on Theory of Computing. New York：ACM Press，2002： 209-217.

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

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

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

［10］趙春艷，范如夢，劉雅楠. 不同緊度下約束滿足問題的相變現(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.）

［11］Huang Ping，Yin Ming Hao. An upper （lower） bound for Max （Min） CSP［J］. Science China Information Sciences，2014，57（7）：1-9.

［12］Xu Wei，Zhang Pan，Liu Tian，et al. The solution space structure of random constraint satisfaction problems with growing domains［J］. Journal of Statistical Mechanics： Theory and Experiment，2015，2015（12）： P12006.

［13］Zhou Guangyan. Hiding solutions in model RB： forced instances are almost as hard as unforced ones［EB/OL］. （2021-3-15）. https：//arxiv.org/abs/2103.06649.

［14］Xu Wei，Zhang Zhe. The solution space structure of planted constraint satisfaction problems with growing domains［J］. Journal of Statistical Mechanics： Theory and Experiment，2022，2022（3）： 033401.

［15］Cai Shaowei，Su Kaile，Chen Qingliang． EWLS： a new local search for minimum vertex cover［C］//Proc of the 24th AAAI Conference on Artificial Intelligence． Menlo Park： AAAI Press，2010： 45-50

［16］王曉峰，許道云. RB模型實(shí)例集上置信傳播算法的收斂性 ［J］. 軟件學(xué)報(bào)，2016，27（11）： 2712-2724. （Wang Xiaofeng，Xu Daoyun. Convergence of the belief propagation algorithm for RB model instances ［J］. Journal of Software，2016，27（11）： 2712-2724.）

［17］Xu Wei，Gong Fuzhou. Performances of pure random walk algorithms on constraint satisfaction problems with growing domains［J］. Journal of Combinatorial Optimization，2016，32（1）： 51-66.

［18］原志強(qiáng)，趙春艷. 兩種改進(jìn)的模擬退火算法求解大值域約束滿足問題 ［J］. 計(jì)算機(jī)應(yīng)用研究，2017，34（12）： 3611-3616. （Yuan Zhiqiang，Zhao Chunyan. Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains ［J］. Application Research of Computers，2017，34（12）： 3611-3616.）

［19］Bouhouch A，Bennis H，Loqman C，et al. Neural network and local search to solve binary CSP［J］. Indonesian Journal of Electrical Engineering and Computer Science，2018，10（3）： 1319-1330.

［20］Tnshoff J，Kisin B，Lindner J，et al. One model，any CSP： graph neural networks as fast global search heuristics for constraint satisfaction［EB/OL］. （2022-08-22）. https：//arxiv.org/abs/2208.10227.

［21］Korani W，Mouhoub M. Discrete mother tree optimization and swarm intelligence for constraint satisfaction problems［C］//Proc of ICAART. 2022： 234-241.

［22］Hossain M S. Constraint propagation and variable ordering heuristics for solving Constrained Partial CP-nets［D］. ［S.l.］：University of Regina，2023.

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

［24］吳撥榮，趙春艷，原志強(qiáng). 置信傳播和模擬退火相結(jié)合求解約束滿足問題 ［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.）

［25］李飛龍，趙春艷，范如夢. 基于禁忌搜索算法求解隨機(jī)約束滿足問題 ［J］. 計(jì)算機(jī)應(yīng)用，2019，39（12）： 3584-3589. （Li Feilong，Zhao Chunyan，F(xiàn)an Rumeng. Solving random constraint satisfaction problems based on tabu search algorithm ［J］. Journal of Computer Applications，2019，39（12）： 3584-3589.）

［26］范如夢，趙春艷，李飛龍. 啟發(fā)式回溯算法求解約束滿足問題 ［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］. Applied Research of Compu-ters，2021，38（5）： 1438-1442.）

［27］張學(xué)才，趙春艷. 基于動態(tài)度的回溯算法求解大值域約束滿足問題 ［J］. 計(jì)算機(jī)應(yīng)用研究，2022，39（5）： 1427-1431. （Zhang Xuecai，Zhao Chunyan. Dynamic degree based backtracking algorithm to solve constraint satisfaction problems with large domains ［J］. Application Research of Computers，2022，39（5）： 1427-1431.）