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

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

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

中圖分類號(hào)：TP301?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號(hào)：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 引言

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

針對(duì)RB模型生成的大值域CSP實(shí)例的求解方法可以分為兩大類。首先是完備性算法，例如回溯技術(shù)、約束傳播和變量排序啟發(fā)式，這些方法雖然能確保解的準(zhǔn)確性，但在處理大規(guī)模的RB模型實(shí)例時(shí)，時(shí)間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)；其次是不完備性算法，包括局部搜索、自然啟發(fā)式和近似概率求解。雖然這些方法可能無(wú)法獲得精確解，但它們旨在可接受的時(shí)間內(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］提出了一個(gè)可以訓(xùn)練的通用圖神經(jīng)網(wǎng)絡(luò)架構(gòu)作為任何約束滿足問(wèn)題的搜索啟發(fā)式方法，通過(guò)實(shí)驗(yàn)證明該方法優(yōu)于神經(jīng)組合優(yōu)化。同年，Korani等人［21］提出兩種離散群智能算法離散母樹(shù)優(yōu)化（mother tree optimization，MTO）和離散的粒子群（discrete particle swarm optimization，PSO）求解RB模型生成的CSP實(shí)例。2023年，Hossain［22］根據(jù)CSP的約束條件對(duì)所有變量進(jìn)行變量排序的啟發(fā)式策略，求解CSP實(shí)例。

本文基于RB模型生成的CSP問(wèn)題實(shí)例，對(duì)CSP中的最大約束可滿足問(wèn)題（MAX-CSP）的求解算法進(jìn)行了深入研究。主要關(guān)注局部搜索算法，并提出了兩種高效的局部搜索算法：基于權(quán)重搜索的W-MCH（weight-based minimum conflict heuristic algorithm）局部搜索算法和最小化變量域的 MDMCH（minimizing variable domain-minimum conflict heuristic algorithm）算法。通過(guò)收斂性和求解效率等實(shí)驗(yàn)結(jié)果的驗(yàn)證，這兩種算法各自展現(xiàn)了獨(dú)特的優(yōu)勢(shì)。相較于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ī)模上的求解時(shí)間至少縮短了30%，且在減少不可滿足約束數(shù)方面取得了顯著進(jìn)展。與多組啟發(fā)式算法相比，實(shí)驗(yàn)結(jié)果表明，這兩種局部搜索算法在求解RB模型生成的CSP實(shí)例時(shí)，呈現(xiàn)出高效的求解效率。

1 RB模型

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

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

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

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

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

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

2 局部搜索算法

2.1 MCH算法

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

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

算法1 MCH算法

2.2 W-MCH算法

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

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

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

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

pi=C（indexicount）/C_valueslength（4）

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

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

從圖2中可以看出，實(shí)際上在當(dāng)Pi>20% 時(shí)，權(quán)重已經(jīng)大于0.6，能滿足大多數(shù)違反變量的修改，在實(shí)際操作中若以weight>0 時(shí)的權(quán)重賦值，會(huì)造成算法過(guò)于隨機(jī)化，導(dǎo)致算法不能有效收斂。當(dāng)weight為0.3左右時(shí)，變量的原始概率值基本處于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)過(guò)200次迭代計(jì)算，得到的藍(lán)色區(qū)域（參見(jiàn)電子版）為迭代后的權(quán)重與初始權(quán)重的差值，可以看到，經(jīng)過(guò)權(quán)重指導(dǎo)搜索后，絕大多數(shù)變量的權(quán)重已經(jīng)小于初始權(quán)重值。此操作可以根據(jù)權(quán)重的不同分配，對(duì)不同的概率值造成不同程度的影響，從而實(shí)現(xiàn)根據(jù)權(quán)重調(diào)整的效果。經(jīng)過(guò)權(quán)重調(diào)整后，可以得到一組優(yōu)秀賦值解，再以MCH算法逐步搜尋單個(gè)變量進(jìn)行修改。W-MCH算法的偽代碼如算法2所示。

算法2 W-MCH算法

2.3 MDMCH算法

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

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

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

算法3 MDMCH算法

2.4 WSCH與MDSCH算法

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

算法4 WSCH、MDSCH算法

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

兩種改進(jìn)的局部搜索策略中都涉及到了約束檢查與后續(xù)MCH算法的尋優(yōu)，對(duì)此首先分析約束檢查的時(shí)間復(fù)雜度，在W-MCH算法迭代的主循環(huán)內(nèi)部會(huì)依次遍歷其約束數(shù)m，則時(shí)間復(fù)雜度為O（m）。對(duì)于內(nèi)部約束檢查中每次在解sol中取出k個(gè)變量x的時(shí)間復(fù)雜度為O（k） ，然后將取出的變量與每組約束C中的t個(gè)具體約束集進(jìn)行判斷的時(shí)間復(fù)雜度為O（t），該操作的時(shí)間復(fù)雜度為O（m×k×t）。即約束檢查的時(shí)間復(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ì)算涉及的操作相對(duì)較少，從約束集中取出不滿足約束索引為O（k），而對(duì)于C_values數(shù)組索引排序的最大操作時(shí)間復(fù)雜度為數(shù)組長(zhǎng)度，與賦值操作都為常數(shù)級(jí)。

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

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

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

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

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

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

WSCH與MDSCH算法外層循環(huán)主要為降溫次數(shù)，時(shí)間復(fù)雜度為O（log（T0/T）） ，內(nèi)層循環(huán)為嘗試產(chǎn)生新的解并決定是否接受新解，主要的迭代次數(shù)由馬爾可夫鏈長(zhǎng)度L參數(shù)控制，約束檢查與上述復(fù)雜度T1一致。兩類變體算法的主要時(shí)間復(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ù)確定時(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ā)式算法作為對(duì)比實(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。對(duì)于不同的n取約束密度p=［0∶0.01∶0.2］，由上述數(shù)值生成的RB模型的具體參數(shù)如表2所示。

3.1 收斂性分析

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

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

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

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

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

3.2 求解效率對(duì)比分析

圖7中分別對(duì)比WSCH、MDSCH算法與RSA、GSA在RB模型各維度10組實(shí)例上的求解概率。圖7（a）～（d）分別展示了RSA、GSA、WSCH和MDSCH四種算法在不同約束密度下的收斂概率。其中RSA在p≤0.07時(shí)，GSA在p≤0.1時(shí)兩種算法在各組RB模型變量實(shí)例上以概率1收斂，W-SCH在p≤0.11時(shí)以概率1收斂，而MDSCH在p≤0.12時(shí)可有效求解。在低維實(shí)例上n為20、40時(shí)，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時(shí)依然有0.1概率求解，但求解概率高于GSA。在變量n取40時(shí)，MDSCH在p取0.14，0.15 時(shí)，求解概率分別為0.9和0.5，WSCH求解概率都為0.6，RSA和GSA算法分別在p取0.14和0.15時(shí)失效，而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)了出來(lái)。在n為60時(shí)，WSCH在p=0.15 有0.1的概率收斂，而MDSCH算法有0.5的概率收斂，RSA和GSA求解失敗。在n取80時(shí)，WSCH在p=0.14有0.3的概率求解，RSA和GSA均已失效，而MDSCH依然有0.6的高概率求解。MDSCH在n取100時(shí)，將求解概率的約束密度提升到了0.12。綜合分析實(shí)驗(yàn)結(jié)果，相比于其他三類算法，MDSCH在高維復(fù)雜實(shí)例上表現(xiàn)出色，其求解概率均高于對(duì)比算法，與此同時(shí)，WSCH在低維實(shí)例中表現(xiàn)出了良好的性能。

圖8中對(duì)比了四種算法在不同變量規(guī)模下的總運(yùn)行時(shí)間?？梢杂^察到，每個(gè)規(guī)模下MDSCH和WSCH算法的總運(yùn)行時(shí)間都明顯優(yōu)于GSA和RSA算法，時(shí)間效率最大提升了50%左右。值得注意的是，隨著變量規(guī)模的增加，尤其是在復(fù)雜可解實(shí)例中，MDSCH的時(shí)間效率開(kāi)始優(yōu)于WSCH算法，MDSCH的最小化值域策略開(kāi)始發(fā)揮作用，這使得它能更快地為退火策略的MCH算法提供一組出色的賦值，從而提高了求解的時(shí)間效率。綜上所述，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個(gè)隨機(jī)實(shí)例的求解概率對(duì)比。其中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］、動(dòng)態(tài)度的ddeg-MAC（dynamic degree-maintaining arc consistency）［27］都為基于回溯的完備性求解算法，基礎(chǔ)的BT與TS算法在高維難解

實(shí)例中并不具有求解能力。從圖9（a）可以看到，當(dāng)變量取80時(shí)，WSCH與MDSCH在同組算法中，p為0.12～0.14時(shí)展現(xiàn)的高概率求解，均優(yōu)于對(duì)比算法，在p=0.14時(shí)，表現(xiàn)最好的MDSCH與對(duì)比算法中最優(yōu)的BP-RSA-2相比，求解概率高出32%。而在p>0.14時(shí)，由于實(shí)例的復(fù)雜度增加，各算法均不能高效求解。如圖9（b），當(dāng)變量n取100，在p=0.14時(shí)，實(shí)例的復(fù)雜度上升，MDSCH算法稍弱于BP-RSA-2、HBT。在p=0.13時(shí)，WSCH求解概率僅次于MDSCH，而MDSCH與對(duì)比算法中最優(yōu)的TS-SA相比，求解概率高出16%。在變量n取100時(shí)，MDSCH算法在p=0.12時(shí)以概率1求解，為所有對(duì)比算法中最佳值。而無(wú)論變量n取80、100，在p取0.11、0.12時(shí)，兩種算法的求解效率均表現(xiàn)最佳。綜上分析，WSCH與MDSCH算法在高維難解實(shí)例中，對(duì)比各類啟發(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)行時(shí)間。在平均運(yùn)行時(shí)間方面，對(duì)于復(fù)雜且難解的RB模型實(shí)例，WSCH和MDSCH算法的運(yùn)行時(shí)間基本相當(dāng)，相比之下，RSA和GSA算法的平均運(yùn)行時(shí)間至少增加了近30%。在不可滿足約束數(shù)量方面，當(dāng)變量維度較低（如n 取20或40）時(shí)，WSCH表現(xiàn)最佳。但在高維實(shí)例中，尤其是在變量維度較高（如n取60、80或100）且實(shí)例較復(fù)雜的情況下，MDSCH表現(xiàn)出色。值得注意的是，在復(fù)雜但可解的區(qū)域中，當(dāng)約束密度為0.16時(shí)，MDSCH的平均不可滿足約束數(shù)量提高的效率最多。綜上所述，這些實(shí)驗(yàn)結(jié)果表明，MDSCH在高維度和復(fù)雜RB模型實(shí)例上的性能表現(xiàn)優(yōu)越，特別是在可滿足性相變點(diǎn)附近的情況下，其平均不可滿足約束數(shù)量顯著減少。

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

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

［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)的模擬退火算法求解大值域約束滿足問(wè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é)合求解約束滿足問(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.）

［25］李飛龍，趙春艷，范如夢(mèng). 基于禁忌搜索算法求解隨機(jī)約束滿足問(wèn)題 ［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］范如夢(mèng)，趙春艷，李飛龍. 啟發(fā)式回溯算法求解約束滿足問(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］. Applied Research of Compu-ters，2021，38（5）： 1438-1442.）

［27］張學(xué)才，趙春艷. 基于動(dòng)態(tài)度的回溯算法求解大值域約束滿足問(wèn)題 ［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.）