基于禁忌搜索算法求解隨機約束滿足問題

李飛龍　趙春艷　范如夢

摘 要：為了求解具有增長取值域的隨機約束滿足問題（CSP），提出了一種基于禁忌搜索并與模擬退火相結(jié)合的算法。首先，利用禁忌搜索得到一組啟發(fā)式的初始賦值，即由一個隨機初始化的可行解通過鄰域構(gòu)造一組候選解，再利用禁忌表使候選解向最小化目標(biāo)函數(shù)值的方向移動;如果得到的最優(yōu)賦值不是問題的解，就把它作為啟發(fā)式的初始賦值，再執(zhí)行模擬退火對這組賦值進行修正直到得到全局最優(yōu)解。數(shù)值實驗結(jié)果表明，所提算法在接近問題的理論相變閾值時仍然能有效地找到問題的解，與其他局部搜索算法相比，表現(xiàn)出了顯著的優(yōu)越性，可用于隨機CSP的算法設(shè)計。

關(guān)鍵詞：隨機約束滿足問題;RB模型;相變現(xiàn)象;禁忌搜索;模擬退火;算法效率

中圖分類號： TP301.6文獻標(biāo)志碼：A

Solving random constraint satisfaction problems based on

tabu search algorithm

LI Feilong， ZHAO Chunyan*， FAN Rumeng

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

Abstract： A novel algorithm based on tabu search and combined with simulated annealing was proposed to solve random Constraint Satisfaction Problem （CSP） with growing domain. Firstly， tabu search was used to obtain a set of initial heuristic assignments， which? meant a set of candidate solutions were constructed based on a randomly initialized feasible solution through neighborhood， and then the tabu table was used to move the candidate solutions to the direction of minimizing the objective function value. If the obtained optimal assignment was not the solution of the problem， the assignment would be used as the initial heuristic assignment and then simulated annealing was performed to correct the set of assignments until the global optimal solution was obtained. The numerical experiments demonstrate that， the proposed algorithm can effectively find the solution of problem when approaching the theoretical phase transition threshold of problem， and it shows obvious superiority compared with other local search algorithms. The proposed algorithm can be applied to the algorithm design of random CSP.

Key words： random Constraint Satisfaction Problem （CSP）;Revised B （RB） model; phase transition phenomenon; tabu search; simulated annealing; algorithm efficiency

0 引言

約束滿足問題（Constraint Satisfaction Problem， CSP）是人工智能領(lǐng)域的一個重要分支[1-2]，它在物流規(guī)劃、生產(chǎn)調(diào)度、產(chǎn)品配置器、生物信息等領(lǐng)域都有非常廣泛的應(yīng)用。

CSP模型是探索非確定性多項式（Non-deterministic Polynomial， NP）-完全問題難解性的重要基礎(chǔ)。為了克服標(biāo)準(zhǔn)CSP模型中B模型的平凡漸進不可滿足性[3-5]，Xu等[6]提出了RB（Revised B）模型并證明了該模型具有精確的可滿足性相變現(xiàn)象。隨后，Xu等[7-8]又從理論和實驗上證明了RB（Revised B）模型在相變區(qū)域能產(chǎn)生大量的難解實例。近年來，RB模型受到了國內(nèi)外研究學(xué)者的廣泛研究[9-12]。理論上，沈靜等[13-16]提出了基于RB模型的推廣模型;Zhou等[17]改進了發(fā)生相變的條件。實驗上，Zhao等[18-20]設(shè)計了基于置信傳播的算法來求解RB模型;原志強等[21]提出了改進的模擬退火（Simulated Annealing， SA）和遺傳算法;吳撥榮等[22]將置信傳播和模擬退火相結(jié)合來求解RB模型。此外，基于RB模型的難解算例被用于各種算法競賽[23]。

本文提出了一種基于禁忌搜索（Tabu Search， TS）并與模擬退火（SA）相結(jié)合的高效算法來求解RB模型這類具有可變?nèi)≈涤虻碾S機CSP， 命名為TS-SA。首先，利用TS得到一個啟發(fā)式的初始賦值，即由一個初始可行解通過鄰域生成一組候選解，利用禁忌表使得候選解向目標(biāo)函數(shù)值減小的方向移動。如果得到的賦值不是問題的解，再利用SA對該賦值進行優(yōu)化直至得到最優(yōu)解。實驗結(jié)果表明，TS-SA算法的求解性能顯著優(yōu)于TS、SA以及其他局部搜索算法。在難解區(qū)域即使找不到解，得到的最優(yōu)解僅使得極少數(shù)的約束是不可滿足的。

1 RB模型

RB模型由一個變量集合X={x1，x2，…，xN}和一個約束集合C={C1，C2，…，CM}構(gòu)成[6]。每個變量xi都從定義域D={1，2，…，dN}中取值，這里dN=Nα，α>0為常數(shù)。不難看出，RB模型中變量的取值域規(guī)模隨著變量數(shù)的增加呈多項式級增長，因此RB模型可以看作是一類具有可變?nèi)≈涤虻碾S機CSP。每個約束Ca都由一個變量的子集Xa和其相應(yīng)的不相容賦值集合Qa所構(gòu)成。從N個變量中隨機選取k（k≥2）個不同的變量構(gòu)成Xa，從Xa可能的dk個賦值中隨機不重復(fù)地選取pdk個k元賦值作為不相容賦值集合Qa，這里00是常數(shù)）個就構(gòu)成了RB模型的一個隨機實例RB（k，N，r，α，p） 。

若能找到這N個變量的一組完全賦值，使得所有約束同時被滿足，這組賦值就是RB（k，N，r，α，p）的一個解。文獻[6]中已經(jīng)嚴格證明了RB模型存在精確的可滿足性相變現(xiàn)象，即用Pr（SAT）表示隨機實例有解的概率，則有以下結(jié)論成立：

定理 設(shè)ps=1-e-α/r，若α>1/k，r>0是兩個常數(shù)，且滿足ke-α/r≥1 ，則：

limN→∞ Pr（SAT）=1， p

0，p>ps （1）

該定理表明，當(dāng)N→∞時，約束緊度存在一個閾值ps，若p>ps，RB模型隨機實例有解的概率趨近于0;若p

由于二元RB模型（即k=2）是NP-完全問題，故下面的算法均用于求解二元RB模型的隨機實例。而k>2的情形可以通過多項式時間歸約為二元的情形。

2 TS算法

TS算法是對局部鄰域搜索算法的推廣，是對人類智力過程的一種模擬，是人工智能的一種體現(xiàn)。它區(qū)別于其他現(xiàn)代啟發(fā)式算法的顯著特點是利用記憶來引導(dǎo)算法的搜索過程。TS算法涉及鄰域、候選解、禁忌表、禁忌長度、藐視準(zhǔn)則等概念。在鄰域搜索的基礎(chǔ)上，通過禁忌表來避免重復(fù)搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進而保證搜索空間的多樣化，最終實現(xiàn)對全局的優(yōu)化。

為將TS算法應(yīng)用于求解RB模型，先給出目標(biāo)函數(shù)的定義。對RB模型的一個隨機實例，設(shè)N個變量的一組完全賦值為X0=（σ1，σ2，…，σN） ，相應(yīng)的約束Ca中變量的賦值為X0a=（σ1a，σ2a，…，σNa）。定義目標(biāo)函數(shù)為不可滿足約束的數(shù)目，即：

E（X0）=∑Ma=1[1-S（X0a）]（2）

其中：

S（X0a）=1， σ1a，σ2a，…，σkaQa

0，σ1a，σ2a，…，σka∈Qa（3）

由此可見，若一組賦值使得目標(biāo)函數(shù)值為0，則這組賦值就是實例的解;否則就不是解。

給定RB模型變量的一組賦值，先隨機且不重復(fù)地從這N個變量中選取NCa個變量對Xij=（xi，xj）構(gòu)成鄰域變量集合。采用兩種不同的策略改變這組賦值中每對所對應(yīng)的賦值構(gòu)成NCa組候選解。這兩種策略分別是：將Xij中xi和xj的賦值相互交換;重新對xi和xj進行隨機賦值。將這組候選解中使得目標(biāo)函數(shù)取得最小值的那組賦值作為最優(yōu)候選解，它所對應(yīng)的Xij作為禁忌對象置入禁忌表中。禁忌表可以看作是一個N×N的矩陣，矩陣中的元素是禁忌對象Xij。禁忌表的主要目的是禁止這些禁忌對象在近期內(nèi)參與最優(yōu)候選解的選擇，從而避免搜索過程中出現(xiàn)循環(huán)和陷入局部最優(yōu)的現(xiàn)象。在最優(yōu)候選解更新過程中，要設(shè)定禁忌對象不允許被選取的最大次數(shù)即禁忌長度。禁忌長度的選取與問題特征有關(guān)，它在很大程度上決定了算法的計算復(fù)雜性。在TS算法中，設(shè)禁忌長度LTabu=N（N-1）/2，這樣能保證更新禁忌表時，至少有一個變量對Xij被選擇。當(dāng)禁忌長度為0時，禁忌表會釋放相應(yīng)的禁忌對象，重新參與候選解的選擇。在賦值更新過程中，可以設(shè)置藐視準(zhǔn)則，也就是最優(yōu)候選解優(yōu)于當(dāng)前最優(yōu)解時，即使這組賦值中所對應(yīng)的Xij在禁忌表中，也可以忽視其禁忌屬性，用它代替當(dāng)前解和最優(yōu)解。若不存在上述最優(yōu)候選解，則在候選解中選擇非禁忌的次優(yōu)候選解為新的當(dāng)前解，將對應(yīng)的Xij加入禁忌表，同時修改禁忌表中各禁忌對象的禁忌長度。重復(fù)上述迭代搜索過程，直到最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值為零，則停止迭代;否則，直至達到最大迭代次數(shù)。

TS算法的具體步驟如下：

輸入 二元RB模型的一個隨機實例以及TS算法中候選解的數(shù)目NCa，最大迭代次數(shù)tmax;

輸出 找到的最優(yōu)解以及對應(yīng)的目標(biāo)函數(shù)值。

步驟1 初始化禁忌表為N×N的零矩陣，由公式計算禁忌長度，隨機初始化一組賦值X0。

步驟2 t=0。

步驟3 計算目標(biāo)函數(shù)值E（X0），如果E（X0）=0，則輸出最優(yōu)解及對應(yīng)的目標(biāo)函數(shù)值。

步驟4 隨機生成鄰域變量集合，對鄰域變量集合采用兩種策略構(gòu)造NCa組候選解。計算候選解目標(biāo)函數(shù)值，按照從小到大保留較優(yōu)的NCa/2組候選解并記錄對應(yīng)的變量對Xij。將使得目標(biāo)函數(shù)值最小的候選解設(shè)為最優(yōu)候選解，并記錄對應(yīng)的目標(biāo)函數(shù)值。

步驟5 如果最優(yōu)候選解優(yōu)于當(dāng)前迭代的最優(yōu)解或滿足藐視準(zhǔn)則，則將最優(yōu)候選解作為當(dāng)前解和最優(yōu)解，并將其他禁忌對象的禁忌長度減1;否則將候選解中次優(yōu)且在禁忌表中對應(yīng)的禁忌長度為0的候選解作為當(dāng)前解，并將其他禁忌對象的禁忌長度減1。

步驟6 t=t+1。

步驟7 如果t>tmax，則輸出最優(yōu)解及對應(yīng)的目標(biāo)函數(shù)值;否則返回步驟3。

可以看出，TS算法先通過鄰域構(gòu)造了一組候選解，增強了全局搜索能力;再利用禁忌表使得目標(biāo)函數(shù)值向減少的方向移動，使算法具備較好的局部搜索能力。雖然該算法受初始賦值和鄰域結(jié)構(gòu)的影響較大，很難得到全局最優(yōu)解，但是搜索過程分布性好，搜索得到的最優(yōu)解僅使得較少的約束是不可滿足的。

SA算法是啟發(fā)式算法的一種。該算法從高溫出發(fā)，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)時能概率性地跳出并最終趨于全局最優(yōu)?？梢?，SA算法的局部搜索能力很強，可以很好地避免陷入局部最優(yōu);但是其對初始解的依賴性較大?？紤]到TS算法較強的全局搜索能力以及SA算法較強的局部搜索能力，本文將兩種算法結(jié)合提出了TS-SA算法來求解RB模型這類具有可變?nèi)≈涤虻碾S機CSP。

3 TS-SA算法

TS-SA算法可以概括為兩步：第一步，利用TS算法得到最優(yōu)解;第二步，若利用TS算法得到的最優(yōu)解不是RB模型隨機實例的解，就將此解作為SA算法的啟發(fā)式初始賦值，再執(zhí)行SA算法對該賦值進行修正，直至得到最優(yōu)解。

TS-SA算法具體步驟如下：

輸入 二元RB模型的一個隨機實例，以及TS算法中候選解的個數(shù)NCa，最大迭代次數(shù)tmax;SA算法中初始溫度T0，終止溫度Tf，溫度控制參數(shù)a，同一溫度下最大迭代次數(shù)L。

輸出 找到的最優(yōu)解以及對應(yīng)的目標(biāo)函數(shù)值。

步驟1 運行上述TS算法，將返回的最優(yōu)賦值作為當(dāng)前解X0。

步驟2 T=T0。

步驟3 i=0。

步驟4 計算目標(biāo)函數(shù)值E（X0），如果E（X0）=0，則輸出最優(yōu)解及對應(yīng)的目標(biāo)函數(shù)值。

步驟5 隨機生成一個0到1之間的實數(shù)rand1。程序前

if （rand1<3/T） {令X0=Xbest，隨機選取一個不可滿足的約束，從其所關(guān)聯(lián)變量的協(xié)調(diào)賦值集合中隨機選取一組賦值，從而得到一組新的賦值記作Xnew}

else {對于X0，隨機選取一個不可滿足的約束，從其所關(guān)聯(lián)變量的協(xié)調(diào)賦值集合中隨機選取一組賦值，從而得到一組新的賦值記作Xnew}。程序后

步驟6 計算ΔE=E（X0）-E（Xnew） ;程序前

if （ΔE<0）{隨機取一個0到1之間的實數(shù)rand2

if （rand2

else {go to 步驟7}}

else {令X0=Xnew}。

程序后步驟7 計算當(dāng)前解的目標(biāo)函數(shù)值E（X0），如果優(yōu)于最優(yōu)解，則將當(dāng)前解賦予最優(yōu)解。

步驟8 i=i+1。

步驟9 如果i>L，則T=a·T;否則返回步驟4。

步驟10 如果T

由此可以看出，TS-SA算法先通過TS算法得到啟發(fā)式的初始賦值，再執(zhí)行SA算法對該賦值進行修正直至得到最優(yōu)解。其中，TS算法通過鄰域構(gòu)造候選解，是多個體進行迭代搜索，有效地避免了陷入局部最優(yōu)解。SA算法是單個體迭代搜索，由以TS算法得到的啟發(fā)式初始賦值避免了SA算法對初始賦值的依賴問題。TS-SA算法有效地利用了TS和SA這兩個算法的優(yōu)點，因此可以表現(xiàn)出良好的求解性能。

4 實驗與結(jié)果分析

4.1 TS-SA算法結(jié)果

在RB模型中，取k=2，α=0.8，r=3，N∈{20，40，60，80，100}，由第1章中的定理可以求出理論的可滿足性相變點為ps=0.234。在不同的問題規(guī)模N下，RB模型的定義域規(guī)模d、約束數(shù)目M等參數(shù)值如表1所示。

在TS算法中，取候選解個數(shù)NCa=120，最大迭代次數(shù)tmax=103，LTabu由禁忌長度公式計算。在隨機生成的50個實例RB（2，N，3，0.8，p）上測試TS算法的求解性能，求解概率如圖1所示。從圖1可以看出，當(dāng)N=20時，TS算法在約束緊度p≤0.15的范圍內(nèi)以概率1找到解，而在p≥0.23時算法失效;在N=100時，TS算法在約束緊度p≤0.09的范圍內(nèi)以概率1找到解，而在p≥0.12時算法失效。若取最大迭代次數(shù)tmax=2000，求解概率如圖2所示，取N=60。從圖2可以看出，增加迭代次數(shù)并沒有從本質(zhì)上改變算法意義上RB模型發(fā)生相變的區(qū)域，僅在個別點處提高了求解概率。因此，本文中算法的最大迭代次數(shù)取tmax=1000。

取N=40，TS算法求解隨機實例的平均迭代次數(shù)和平均運行時間如表2所示，其中：t表示平均迭代次數(shù)， time表示平均運行時間。從表2中可以看出，隨著p的不斷增加，TS算法的運行時間呈指數(shù)級增長。當(dāng)p≤0.14時，TS算法可以在較短的時間內(nèi)通過較少的迭代次數(shù)以概率1收斂到實例的解;當(dāng)0.14

在 TS-SA算法中，取候選解個數(shù)NCa=120，最大迭代次數(shù)tmax=103，LTabu由禁忌長度公式計算。取初始溫度T0=97，終止溫度Tf=3，溫度控制參數(shù)a=0.95，同一溫度下最大迭代次數(shù)L=103。對于不同的問題規(guī)模N，分別在隨機生成的50個實例RB（2，N，3，0.8，p）上測試TS-SA算法的求解性能，求解概率如圖3所示。從圖3中可以看出：當(dāng)N=20時，TS-SA算法在約束緊度p≤0.16的范圍內(nèi)以概率1找到解，而在p≥0.23時算法失效;當(dāng)N=100時，TS-SA算法在約束緊度p≤0.12的范圍內(nèi)以概率1找到解，而在p≥0.17時算法失效。

TS算法和TS-SA算法在求解二元RB模型隨機實例過程中，在p=0.10和p=0.13時算法的平均運行時間分別如圖4和圖5所示。從圖4（a）和圖5（a）可以看出，兩種算法在N≤100時平均運行時間基本一樣。這是由于在p≤0.10時TS算法起主要作用，它能比較有效地找到實例的解，此時并不需要運行SA算法對TS算法得到的最優(yōu)賦值進行優(yōu)化或者僅在少數(shù)情況下需要再執(zhí)行SA算法。從圖4（b）和圖5（b）可以看出，這兩種算法在N≤80時平均運行時間基本一樣;而當(dāng)N=100時，TS-SA算法的運行時間明顯比TS算法多。這說明在p=0.13時隨著變量數(shù)目N的增加，需要再運行SA算法對TS算法得到的賦值進行修正才能得到實例的解或者最優(yōu)解。

當(dāng)p≥0.16時，TS算法和TS-SA開始失效，即不能有效地找到二元RB模型隨機的解，也就是得到的最優(yōu)解不能使得所有約束都是可滿足的。對于不同的問題規(guī)模N，由TS算法和TS-SA算法得到的最優(yōu)解使得約束不可滿足的平均數(shù)目如表3～4所示。從表3和表4可以看出，在鄰近相變點時TS-SA算法雖然找不到實例解，但是得到的最優(yōu)解僅使得極少數(shù)的約束是不可滿足的;并且TS-SA算法求解RB模型時得到的平均不可滿足約束數(shù)目明顯少于TS算法所得到的。

TS-SA算法總能收斂到一組賦值，該賦值是此算法得到的最優(yōu)解。事實上，當(dāng)p較小時，只執(zhí)行TS算法就能找到實例的解。隨著p的不斷增大，TS得到的賦值逐漸不能使得目標(biāo)函數(shù)為0，需要執(zhí)行SA算法對由TS算法得到的啟發(fā)式初始賦值進行修正，直到得到全局最優(yōu)解。如圖6所示，可以看到，取N=40，p從0.15增大到0.19時，在TS-SA算法找到解的實例中，僅執(zhí)行TS算法就能找到解的實例數(shù)目比例在逐漸降低，需要執(zhí)行SA算法才能找到解的實例數(shù)目占比逐漸增大。這表明在TS算法失效的情況下，SA算法的局部搜索能力開始占主導(dǎo)地位。直到非常接近理論相變點時，TS-SA算法失效，不能收斂到實例的解。

4.2 算法對比

將本文提出的TS-SA算法與TS算法，文獻[21]中提出的GSA（Genetic Simulated Annealing）算法、RSA（Revised Simulated Annealing）算法，文獻[22]中提出的BP-RSA-1（Belief Propagation-Revised Simulated Annealing-1）、BP-RSA-2（Belief Propagation-Revised Simulated Annealing-2）算法進行對比。特別地，取N=100，對于不同的約束緊度p，分別在隨機生成的50個實例RB（2，N，3，0.8，p）上運行算法，得到的求解概率如圖7所示。由圖7可以看出，本文提出的TS-SA算法求解效率明顯優(yōu)于TS算法、RSA算法;與BP-RSA-1算法、BP-RSA-2算法、GSA算法相比，TS-SA算法也在一定程度上提高了求解概率。

取N=60，p=0.13時，TS-SA算法、BP-RSA-1算法、GSA算法和RSA算法的平均運行時間如圖8所示。由圖8可以看出，當(dāng)N較大時，與其他算法相比，本文提出的TS-SA算法花費了較多的運行時間。而由圖4可知，當(dāng)N較小時，只運行TS算法就可以花費較少的時間有效地找到實例的解。這是因為大多數(shù)的實例都需要花費時間來執(zhí)行SA算法對由TS得到的啟發(fā)式初始賦值進行修正。

取N=60，p≥0.17，五種算法求解RB模型隨機實例找不到解時，得到的平均不可滿足約束數(shù)目如表5所示。由表5可以看出，由TS算法得到的不可滿足約束的數(shù)目要小于RSA算法所得到的，可見TS算法的全局搜索能力是優(yōu)于RSA算法的。從求解概率來看，RSA算法的局部搜索能力優(yōu)于TS算法。而將TS和SA結(jié)合得到的TS-SA算法所得到的平均不可滿足約束數(shù)目是最少的。當(dāng)p=0.17時，TS-SA算法的平均最少不可滿足約束的數(shù)目占約束總數(shù)的比例約為0.3%;當(dāng)p=0.20時，TS-SA算法的平均最少不可滿足約束的數(shù)目占約束總數(shù)的比例約為1.1%。這充分表明了本文提出的TS-SA算法雖然在非常接近理論相變點時找不到實例的解，但得到的最優(yōu)解僅使得近1%的約束是不可滿足的。

5 結(jié)語

本文提出了一種基于TS并與SA相結(jié)合的高效算法TS-SA來求解RB模型這類具有可變?nèi)≈涤虻碾S機約束滿足問題（CSP）。TS-SA算法是利用TS算法得到最優(yōu)初始賦值，在不是問題解的情況下再執(zhí)行SA算法對這個啟發(fā)式的初始賦值進行優(yōu)化。實驗結(jié)果表明，在接近理論相變點時，TS-SA算法能有效地找到隨機實例的解;在理論相變點附近，即使算法失效，得到的最優(yōu)解僅使得極少數(shù)的約束是不可滿足的。這表明TS-SA算法充分利用了TS和SA算法的優(yōu)勢，既在全局搜索，又對局部優(yōu)化，表現(xiàn)出了良好的求解性能，可用于對隨機CSP的算法設(shè)計。接下來的工作中我們會嘗試研究將禁忌搜索算法與其他局部搜索算法相結(jié)合來進一步優(yōu)化算法的求解性能，從而探索CSP解空間的演化規(guī)律，以及問題難解性的根源。

參考文獻 （References）

[1]TSANG E. A glimpse of constraint satisfaction [J]. Artificial Intelligence Review， 1999， 13（3）： 215-227.

[2]MOLLOY M. Models for random constraint satisfaction problems [J]. SIAM Journal of Computing， 2003， 32（4）： 935-949.

[3]SMITH B M， DYER M E. Locating the phase transition in binary constraint satisfaction problems [J]. Artificial Intelligence， 1996， 81（1/2）： 155-181

[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]GENT I P， MACINTYRE E， PROSSER P， et al. Random constraint satisfaction： flaws and structure [J]. Constraints， 2001， 6（4）： 345-372.

[6]XU K， LI W. Exact phase transitions in random constraint satisfaction problems [J]. Journal of Artificial Intelligence Research， 2000， 12（1）： 93-103.

[7]XU K， LI W. Many hard examples in exact phase transitions [J]. Theoretical Computer Science， 2006， 355（3）： 291-302.

[8]XU K， BOUSSEMART F， HEMERY F， et al. Random constraint satisfaction： Easy generation of hard （satisfiable） instances [J]. Artificial Intelligence， 2007， 171（8/9）： 514-534.

[9]LIU T， LIN X， WANG C， et al. Large hinge width on sparse random hypergraphas [C]// Proceedings of the 22nd International Joint Conference on Artificial Intelligence. Reston： AAAI， 2011： 611-616.

[10]ZHAO C， ZHENG Z. Threshold behaviors of a random constraint satisfaction problem with exact phase transitions [J]. Information Processing Letters， 2011， 111（20）： 985-988.

[11]徐偉，鞏馥洲.值域增長約束滿足問題的無回溯與隨機行走策略的算法復(fù)雜性分析[J].計算機科學(xué)，2014，41（4）：205-210.（XU W， GONG F Z. Computational complexity analysis of backtrack-free and random-walk strategies on constraint satisfaction problems with growing domains [J]. Computer Science， 2014， 41（4）： 205-210.）

[12]王曉峰，許道云.RB模型實例集上置信傳播算法的收斂性[J].軟件學(xué)報，2016，27（11）：2712-2724.（WANG X F， XU D Y. Convergence of the belief propagation algorithm for RB model instances [J]. Journal of Software， 2016， 27（11）： 2712-2724.）

[13]沈靜.約束滿足問題的模型構(gòu)造和相變現(xiàn)象[D].武漢：華中師范大學(xué)，2011：13-30.（SHEN J. A model of random constraint satisfaction problems and phase transitions [D]. Wuhan： Central China Normal University， 2011： 13-30.）

[14]沈靜，梅丹.可滿足實例的歸結(jié)復(fù)雜度[J].計算機工程與應(yīng)用，2014，50（22）：69-72.（SHEN J， MEI D. Resolution complexity of satisfiability instances [J]. Computer Engineering and Applications， 2014， 50（22）： 69-72.）

[15]SHEN J， REN Y. Bounding the scaling window of random constraint satisfaction problems [J]. Journal of Combinatorial Optimization， 2016， 31（2）： 786-801.

[16]沈靜，任耀峰，梅丹，等.一種產(chǎn)生可滿足性難解實例的模型[J].海軍工程大學(xué)學(xué)報，2016，28（3）：5-8.（SHEN J， REN Y F， MEI D， et al. A model to generate hard satisfiable instances [J]. Journal of Naval University of Engineering， 2016， 28（3）： 5-8.）

[17]ZHOU G， GAO Z， LIU J. On the constraint length of random-CSP [J]. Journal of Combinatorial Optimization， 2015， 30（1）： 188-200.

[18]ZHAO C， ZHOU H， ZHENG Z， et al. A message-passing approach to random constraint satisfaction problems with growing domains [J]. Journal of Statistical Mechanics： Theory and Experiment， 2011（2）： Article No. P02019.

[19]趙春艷，鄭志明.一種基于變量熵求解約束滿足問題的置信傳播算法[J].中國科學(xué)：信息科學(xué)，2012，42（9）：1170-1180.（ZHAO C Y， ZHENG Z M. A belief-propagation algorithm based on variable entropy for constraint satisfaction problems [J]. SCIENTIA SINICA Informationis， 2012， 42（9）： 1170-1180.）

[20]ZHAO C， ZHANG P， ZHENG Z， et al. Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2012， 85（1 Pt 2）： 016106.

[21]原志強，趙春艷.兩種改進的模擬退火算法求解大值域約束足問題[J].計算機應(yīng)用研究，2017，34（12）：3611-3616.（YUAN Z Q， ZHAO C Y. Two improved simulated annealing algorithms for solving constraint satisfaction problems with large domains [J]. Application Research of Computers， 2017， 34（12）： 3611-3616.）

[22]吳撥榮，趙春艷，原志強.置信傳播和模擬退火相結(jié)合求解約束滿足問題[J].計算機應(yīng)用研究，2019，36（5）：1297-1301.（WU B R， ZHAO C Y， YUAN Z Q. Combining belief propagation and simulated annealing to solve random satisfaction problems [J]. Application Research of Computers， 2019， 36（5）： 1297-1301.）

[23]CAI S， SU K L， SATTAR A， et al. Local search with edge weighting and configuration checking heuristics for minimum vertex cover [J]. Artificial Intelligence， 2011， 175（9/10）： 1672-1696.

This work is partially supported by the National Natural Science Foundation of China （11301339）， the National Natural Science Foundation of China — International （Regional） Cooperation and Exchange Program （11491240108）.

LI Feilong， born in 1994， M. S. candidate， His research interests include computational theory and computational complexity.

ZHAO Chunyan， born in 1982， Ph. D.， lecturer. Her research interests include non-deterministic polynomial-complete problem， computational theory and computational complexity.

FAN Rumeng， born in 1995， M. S. candidate. Her research interests include computational theory and computational complexity.

收稿日期：2019-05-16;修回日期：2019-07-08;錄用日期：2019-07-17。

基金項目：國家自然科學(xué)基金資助項目（11301339）;國家自然科學(xué)基金國際 （地區(qū)）合作與交流項目（11491240108）。

作者簡介：李飛龍（1994—），男，安徽阜陽人，碩士研究生，主要研究方向：計算理論與計算復(fù)雜性; 趙春艷（1982—），女，河南焦作人，講師，博士，主要研究方向：NP-完全問題、計算理論與計算復(fù)雜性; 范如夢（1995—），女，河南駐馬店人，碩士研究生，主要研究方向：計算理論與計算復(fù)雜性。

文章編號：1001-9081（2019）12-3584-06 DOI：10.11772/j.issn.1001-9081.2019050834