李占山，張 良，郭勁松，張 乾

（1.吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)春 130012；2.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130012）

0 引 言

約束滿足問(wèn)題（Constraint satisfaction problems，CSP）是人工智能方向的一個(gè)重要分支，相關(guān)技術(shù)被廣泛應(yīng)用于組合問(wèn)題求解，如配置器設(shè)計(jì)、調(diào)度、符號(hào)推理和路由等。相容性算法和求解技術(shù)的研究一直是CSP領(lǐng)域的研究熱點(diǎn)，國(guó)內(nèi)研究人員已有工作主要集中于前者［1－4］，而隨著約束滿足問(wèn)題應(yīng)用領(lǐng)域的不斷擴(kuò)大，約束求解技術(shù)得到了越來(lái)越多的關(guān)注。已有求解算法主要包括三類:回溯算法、局部搜索和動(dòng)態(tài)規(guī)劃［5］。作為一種完全求解算法，回溯算法的主要任務(wù)包括為可解問(wèn)題找到解以及證明不可滿足問(wèn)題的不可解性，但在應(yīng)用過(guò)程中，由于問(wèn)題解空間規(guī)模較大，經(jīng)常會(huì)出現(xiàn)“組合爆炸”現(xiàn)象，樸素回溯過(guò)程在人們期望的時(shí)間內(nèi)難以給出一個(gè)有效解，如何提高求解效率成為研究回溯算法面臨的首要問(wèn)題。

求解過(guò)程中，回溯算法進(jìn)行深度優(yōu)先檢索，需要不斷選擇變量來(lái)進(jìn)行實(shí)例化，對(duì)眾多問(wèn)題的實(shí)驗(yàn)研究表明，變量被實(shí)例化的順序?qū)τ谀芊窀咝У厍蠼馄鹬陵P(guān)重要的作用。為了得到好的搜索變量排序，研究人員提出了多種變量啟發(fā)式方法，對(duì)于已有啟發(fā)式的討論可參見(jiàn)文獻(xiàn)［5］。通過(guò)實(shí)驗(yàn)對(duì)比研究人員發(fā)現(xiàn)，沒(méi)有一種現(xiàn)有啟發(fā)式能在所有問(wèn)題上的求解效率明顯優(yōu)于其他方法。因此，根據(jù)問(wèn)題自身特性，尋找基于問(wèn)題結(jié)構(gòu)的啟發(fā)式方法被認(rèn)為是提升求解效率的有效途徑。

Composed問(wèn)題為一類隨機(jī)問(wèn)題，眾多實(shí)際應(yīng)用問(wèn)題具有類似于Composed問(wèn)題的結(jié)構(gòu)特性，但受限于問(wèn)題的特殊結(jié)構(gòu)，現(xiàn)有啟發(fā)式方法在處理該類問(wèn)題時(shí)總是生成過(guò)多節(jié)點(diǎn)，造成求解效率下降。本文從Composed問(wèn)題結(jié)構(gòu)出發(fā)，提出邊界變量集的概念，并給出了Composed問(wèn)題中邊界變量的篩選方法，在此基礎(chǔ)之上設(shè)計(jì)實(shí)現(xiàn)了邊界啟發(fā)式方法。

1 問(wèn)題背景

定義1 二元約束網(wǎng)絡(luò)G＝ （X，D，C），其中，X 為有限變量集｛X1，X2，…，Xn｝，D 為論域集｛D1，D2，…，Dn｝，對(duì)于任意變量Xi∈ X，Di為其所有可能取值構(gòu)成的有限論域，即Di＝dom（Xi），C 為有限約束集｛C1，C2，…，Ce｝，任意Ci∈C均為作用在X上的二元關(guān)系。

變量Xi和Xj之間的約束記為Rij，則Rij?dom（Xi）×dom（Xj），值對(duì)（（Xi，a），（Xj，b））滿足Rij，當(dāng)且僅當(dāng)（（Xi，a）（Xj，b））∈Rij。約束網(wǎng)絡(luò)中，若變量Xi和Xj之間存在約束，則變量節(jié)點(diǎn)Xi和Xj之間存在?。╥，j），變量的度為與其相連約束弧的個(gè)數(shù)。

對(duì)集合X中所有變量進(jìn)行賦值，令Xi＝ai，且ai∈Di，若元組T ＝ （a1，a2，…，an）滿足C中所有約束，則T為問(wèn)題的一個(gè)解，如果T不存在，該問(wèn)題是不可滿足的。對(duì)變量集X中任意k（1≤k＜n）個(gè)變量進(jìn)行賦值，得到元組T1＝ （a1，a2，…，ak），若T1滿足C中所有約束，則稱T1為該問(wèn)題的部分解。

約束網(wǎng)絡(luò)結(jié)構(gòu)特征描述還需要使用到如下定義，詳細(xì)介紹可參考文獻(xiàn)［6］。

定義2 （松緊度Tightness）

約束弧 （i，j）的松緊度記為Tij，則

定義3 （網(wǎng)絡(luò)密度Density）

回溯求解過(guò)程中，為了壓縮搜索空間，基于約束傳播思想，每次變量賦值以后都要進(jìn)行相容性檢查，如果檢查失敗，則需進(jìn)行回溯，檢查成功則在當(dāng)前未賦值變量中選擇變量進(jìn)行實(shí)例化，變量啟發(fā)式則作用于該過(guò)程指導(dǎo)變量的選取。根據(jù)不同的相容性強(qiáng)度，研究人員提出多種求解算法，Maintain arc consistency（MAC）［7］算法是應(yīng)用最為廣泛、被認(rèn)為是效率較高的求解算法之一。下面給出弧相容定義以及MAC算法實(shí)現(xiàn)框架［8］:

定義4 （弧相容Arc Consistency）AC

（1）弧 （i，j）是相容的，當(dāng)且僅當(dāng)對(duì)任意（Xi，a）∈ dom（Xi），存在（Xj，b）∈dom（Xj），使得（（Xi，a），（Xj，b））∈Rij。

（2）約束網(wǎng)絡(luò)是弧相容的，當(dāng)且僅當(dāng)對(duì)任意弧（i，j）∈G，（i，j）是相容的。

MAC算法實(shí)現(xiàn)框架如下所示:

2 Composed問(wèn)題

Composed問(wèn)題在文獻(xiàn)［9］中首先被描述，結(jié)構(gòu)上Composed問(wèn)題具有多個(gè)局部區(qū)域，一般Composed問(wèn)題結(jié)構(gòu)如圖1［6］所示。

圖1 典型Composed問(wèn)題結(jié)構(gòu)圖Fig.1 Typical tructure of Composed problems

圖1為同一問(wèn)題的兩個(gè)結(jié)構(gòu)圖，左邊約束網(wǎng)絡(luò)任意約束弧灰度相同，而右側(cè)網(wǎng)絡(luò)中，約束弧灰度正比于其松緊度大小。一個(gè)Composed問(wèn)題可表示成如下形式元組:

n1為中心區(qū)域變量個(gè)數(shù)，d1為中心區(qū)域變量論域的大小，m1為中心區(qū)域約束網(wǎng)絡(luò)密度，t1為中心區(qū)域內(nèi)約束弧松緊度；s為伴隨區(qū)域個(gè)數(shù)；參數(shù)n2、d2、m2和t2表示伴隨區(qū)域局部網(wǎng)絡(luò)特性，所表示內(nèi)容與中心區(qū)域相對(duì)應(yīng)；L表示將一個(gè)伴隨區(qū)域連接到中心區(qū)域的約束個(gè)數(shù)，t3為約束松緊度。實(shí)驗(yàn)部分所用測(cè)試樣例中，變量論域大小都為10，且每個(gè)伴隨區(qū)域都由8個(gè)變量構(gòu)成，為了表示起來(lái)更加簡(jiǎn)潔，略去某些特性，記為如下元組:

Composed問(wèn)題中，伴隨區(qū)域局部網(wǎng)絡(luò)密度以及變量間約束弧的松緊度都要高于中心區(qū)域，直觀上來(lái)看，在伴隨區(qū)域找到一個(gè)滿足所有約束的部分解會(huì)更加困難，按照設(shè)計(jì)現(xiàn)有啟發(fā)式方法所依賴的失敗優(yōu)先原則［10］，應(yīng)該利用啟發(fā)式方法將求解過(guò)程引導(dǎo)到這些區(qū)域，但受限于問(wèn)題結(jié)構(gòu)，現(xiàn)有啟發(fā)式方法無(wú)法實(shí)現(xiàn)該目標(biāo)。

常用啟發(fā)式方法中，deg和ddeg為靜態(tài)啟發(fā)式，dom／deg、dom／ddeg和dom／wdeg為動(dòng)態(tài)啟發(fā)式，初始階段，兩類啟發(fā)式受到變量度的影響，選取變量都會(huì)落到中心區(qū)域。不同于其他啟發(fā)式，dom／wdeg方法為每個(gè)約束弧綁定動(dòng)態(tài)weight值，變量Xi的wdeg值計(jì)算公式如下:

式中:FutVars為當(dāng)前未實(shí)例化變量集。

當(dāng)發(fā)生回溯時(shí)，導(dǎo)致死節(jié)點(diǎn)生成的約束弧weight值增加，當(dāng)檢索過(guò)程進(jìn)行到一定程度時(shí)，較大的weight值能幫助檢索過(guò)程跳轉(zhuǎn)到更加合理的區(qū)域進(jìn)行。因此dom／wdeg啟發(fā)式具有一定學(xué)習(xí)能力，但該過(guò)程仍會(huì)生成過(guò)多節(jié)點(diǎn)，使得問(wèn)題求解效率受到影響。

3 邊界啟發(fā)式方法

Composed問(wèn)題在結(jié)構(gòu)上可劃分為多個(gè)局部區(qū)域，當(dāng)位于某個(gè)局部區(qū)域內(nèi)部的變量被實(shí)例化并進(jìn)行相容性檢查時(shí)，約束傳播沿著約束弧進(jìn)行，而與該變量直接相連的變量大都位于該局部區(qū)域，這也使得整個(gè)約束傳播過(guò)程通常會(huì)被局限于該區(qū)域，dom／wdeg啟發(fā)式只能在該區(qū)域內(nèi)收集啟發(fā)式信息，文獻(xiàn)［11］的分析表明，在更全面的解空間內(nèi)收集啟發(fā)式信息有助于選擇更加合理的變量。

結(jié)合以上分析發(fā)現(xiàn)，Composed問(wèn)題的求解關(guān)鍵為位于中心區(qū)域與伴隨區(qū)域相鄰邊界上的變量，即位于伴隨區(qū)域且通過(guò)弱約束與中心區(qū)域相連的變量，符合這樣條件的變量稱為邊界變量，由這些變量構(gòu)成的集合稱為邊界變量集。當(dāng)邊界變量被實(shí)例化并進(jìn)行相容性檢查時(shí)，約束傳播會(huì)沿著約束弧同時(shí)影響到中心區(qū)域和伴隨區(qū)域，避免了被局限于某個(gè)區(qū)域。

邊界啟發(fā)式方法主要設(shè)計(jì)思想為從約束網(wǎng)絡(luò)中篩選出所有邊界變量構(gòu)成邊界變量集，檢索過(guò)程中，邊界變量集中的變量應(yīng)當(dāng)具有高于其他變量的實(shí)例化優(yōu)先級(jí)。為了找出邊界變量，在Composed問(wèn)題約束網(wǎng)絡(luò)上首先給出如下定義:

定義5 （平均松緊度Average tightness）

定義6 （強(qiáng)約束，弱約束）

約束Rij為強(qiáng)約束，當(dāng)且僅當(dāng)Tij≥avg＿t；反之，若Tij＜avg＿t則Rij為弱約束。

邊界啟發(fā)式方法在實(shí)現(xiàn)時(shí)分為兩個(gè)階段，一是預(yù)處理階段，對(duì)變量進(jìn)行篩選得到邊界變量集；二是在檢索過(guò)程中利用已有信息來(lái)選擇變量。

預(yù)處理階段，首先計(jì)算出網(wǎng)絡(luò)平均松緊度avg＿t，然后為變量設(shè)置標(biāo)識(shí)數(shù)組strong［n］和weak［n］（n為變量個(gè)數(shù)），對(duì)任意i∈（0…n－1），如果strong［i］為真，則變量Xi有強(qiáng)約束連接，為假則不受強(qiáng)約束限制，如果weak［i］為真，則變量Xi有弱約束連接，為假則不受弱約束限制。遍歷C中元素，對(duì)任意t∈（0…e－1），若Ct為強(qiáng)約束，則將其所約束變量i和j的strong標(biāo)識(shí)設(shè)為真，如果為弱約束，則將weak標(biāo)識(shí)設(shè)為真。對(duì)strong和weak初始化結(jié)束之后，對(duì)任意變量Xi∈X，若其對(duì)應(yīng)的標(biāo)識(shí)strong［i］與weak［i］合取為真，則變量Xi為邊界變量，否則不是。這樣在預(yù)處理階段結(jié)束后就可以得到邊界變量集mid＿var＿set。

求解階段:給出邊界啟發(fā)式的兩種實(shí)現(xiàn)策略，記為H1、H2。H1:選擇變量時(shí)先要判斷 mid＿var＿set是否為空，不為空，按照dom／wdeg啟發(fā)式從mid＿var＿set中選擇一個(gè)變量；若為空，則在所有未賦值變量中按照dom／wdeg啟發(fā)式選擇變量進(jìn)行實(shí)例化。H2:將mid＿var＿set內(nèi)所有邊界變量的初始wdeg值設(shè)定為一個(gè)大于0的定值，以此來(lái)提高邊界變量在dom／wdeg啟發(fā)式下的實(shí)例化優(yōu)先級(jí)，檢索過(guò)程按照dom／wdeg啟發(fā)式進(jìn)行。兩種策略主要區(qū)別在于:前者只有在所有邊界變量被實(shí)例化以后才會(huì)選擇非邊界變量進(jìn)行賦值，后者則是將dom／wdeg啟發(fā)式下的求解過(guò)程向邊界變量集靠攏，不保證邊界變量總是先于非邊界變量被選擇。

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)部分采用 MAC3rm［12］作為求解算法，MAC3rm為MAC算法中的一種，已有實(shí)驗(yàn)結(jié)果表明，MAC3rm的實(shí)際求解效率要優(yōu)于其他MAC算法?，F(xiàn)有啟發(fā)式中，dom／wdeg［13］方法在一系列問(wèn)題上有較好的表現(xiàn)，而且通過(guò)應(yīng)用該啟發(fā)式，MAC算法可以有效地代替基于回跳的求解技術(shù)，成為較為穩(wěn)定高效的通用求解算法，因此采用dom／wdeg啟發(fā)式與新啟發(fā)式方法進(jìn)行對(duì)比，以求解所消耗CPU時(shí)間、檢索過(guò)程生成節(jié)點(diǎn)數(shù)以及約束檢查數(shù)作為參考標(biāo)準(zhǔn)，其中CPU時(shí)間t以ms為單位，生成節(jié)點(diǎn)數(shù)和約束檢查次數(shù)分別記為num和cc，這里一次約束檢查是指判斷一個(gè)值對(duì) （（Xi，a），（Xj，b））是否滿足Rij所需要進(jìn)行的操作。為了提高實(shí)驗(yàn)本身的效率，預(yù)處理階段，首先在約束網(wǎng)絡(luò)上進(jìn)行一次弧相容檢查，刪除變量論域中的不滿足值，該過(guò)程所進(jìn)行的約束檢查次數(shù)不會(huì)被計(jì)入對(duì)比實(shí)驗(yàn)數(shù)據(jù)。H2啟發(fā)式需要為每個(gè)變量對(duì)應(yīng)wdeg設(shè)定初值，如果wdeg初值設(shè)為正無(wú)窮，則H2啟發(fā)式等同于H1，如果為0，則為dom／wdeg啟發(fā)式，為了避免該初值過(guò)大或者過(guò)小，并且能夠一定程度上反映問(wèn)題規(guī)模，這里設(shè)定為n／2（n為變量個(gè)數(shù)）。

實(shí)驗(yàn)中部分測(cè)試樣例的XML描述文檔可在線下載［14］，其他樣例則按照參數(shù)要求隨機(jī)生成，測(cè)試樣例包括了22組可滿足問(wèn)題，每組問(wèn)題都包括10個(gè)隨機(jī)生成的具體問(wèn)題，其中14組為可滿足，8組為不可滿足樣例。為了避免單個(gè)問(wèn)題本身特性對(duì)啟發(fā)式方法效果的影響，對(duì)每一類問(wèn)題的10個(gè)樣例測(cè)試結(jié)果取其平均值進(jìn)行比較。實(shí)驗(yàn)結(jié)果如表1和表2所示。

實(shí)驗(yàn)結(jié)果顯示H1啟發(fā)式在某些樣例上求解效率急劇下降，消耗時(shí)間和生成節(jié)點(diǎn)數(shù)都有數(shù)量級(jí)上的增加，表3給出其中一個(gè)樣例的結(jié)果對(duì)比。

對(duì)檢索過(guò)程中變量被實(shí)例化的順序和次數(shù)進(jìn)行分析，可以發(fā)現(xiàn)產(chǎn)生這種現(xiàn)象的原因在于啟發(fā)式H1限制了dom／wdeg啟發(fā)式執(zhí)行，使得即使收集到足夠多的啟發(fā)式信息，也不能正確跳離當(dāng)前檢索區(qū)域。邊界變量位于不同伴隨區(qū)域內(nèi)，在某個(gè)邊界變量被實(shí)例化且進(jìn)行約束傳播之后，受dom／wdeg啟發(fā)式的影響，通常與該變量位于同一伴隨區(qū)域內(nèi)的其他邊界變量會(huì)被選擇進(jìn)行實(shí)例化。當(dāng)該伴隨區(qū)域內(nèi)所有邊界變量均被實(shí)例化后，受H1啟發(fā)式限制，檢索過(guò)程會(huì)跳轉(zhuǎn)到另外一個(gè)伴隨區(qū)域，并從中選擇邊界變量進(jìn)行實(shí)例化。在Composed問(wèn)題中，任意兩個(gè)伴隨區(qū)域之間沒(méi)有約束直接相連，因此在起始階段，各個(gè)伴隨區(qū)域內(nèi)邊界變量較容易被實(shí)例化，但隨著被實(shí)例化邊界變量的增多，在相容性檢查時(shí)，中心區(qū)域內(nèi)變量論域會(huì)被不斷刪減，此時(shí)可能出現(xiàn)論域?yàn)榭盏默F(xiàn)象而產(chǎn)生回溯。對(duì)于某些樣例，只有當(dāng)邊界變量集內(nèi)大部分變量被實(shí)例化后才會(huì)發(fā)生回溯，這時(shí)H1啟發(fā)式會(huì)不斷調(diào)整邊界變量的取值，直到找到一個(gè)可拓展為最終解的部分解，由于邊界變量集本身檢索空間也很龐大，該過(guò)程會(huì)耗費(fèi)大量時(shí)間。從實(shí)驗(yàn)結(jié)果可以看到H1啟發(fā)式求解效率的這種波動(dòng)現(xiàn)象只出現(xiàn)在了具有10個(gè)伴隨區(qū)域的問(wèn)題類中，伴隨區(qū)域個(gè)數(shù)為5的樣例中沒(méi)有出現(xiàn)該現(xiàn)象，由于伴隨區(qū)域個(gè)數(shù)的減少，邊界變量集中變量數(shù)也相應(yīng)減小，其自身搜索空間也不會(huì)過(guò)于龐大，因此規(guī)模較小的邊界變量集可以有效地避免出現(xiàn)這種情況。統(tǒng)計(jì)實(shí)驗(yàn)數(shù)據(jù)時(shí)，為了能對(duì)三種啟發(fā)式方法在普遍問(wèn)題上的求解效率進(jìn)行對(duì)比，出現(xiàn)

這種現(xiàn)象的特殊樣例并沒(méi)有包括在內(nèi)，表中對(duì)于包含這些樣例的每一類問(wèn)題均注明了實(shí)際統(tǒng)計(jì)樣例的個(gè)數(shù)。

表1 可滿足問(wèn)題Table 1 Satisfiable problems

表2 不可滿足問(wèn)題Table 2 Unsatisfiable problems

表3 特殊樣例Table 3 Abnormal instance

在所有可滿足問(wèn)題中，25＋10＋〈5，0.05〉、75＋5＋〈10，0.05〉和75＋5＋〈15，0.05〉三類問(wèn)題難度較小，三種啟發(fā)式方法在所有樣例上都接近于無(wú)回溯求解。而在其他可滿足問(wèn)題上，H1和H2啟發(fā)式的求解效率均要明顯優(yōu)于dom／wdeg啟發(fā)式。結(jié)合前面的分析，H1啟發(fā)式求解效率在某些問(wèn)題上存在較大波動(dòng)，不能夠?qū)崿F(xiàn)穩(wěn)定求解，而H2啟發(fā)式則在所有問(wèn)題上都可以實(shí)現(xiàn)穩(wěn)定高效的求解。H1和H2啟發(fā)式在一般問(wèn)題上的求解效率相近，但由于穩(wěn)定性差異，H2啟發(fā)式要比H1更適用于可滿足問(wèn)題的求解。

在不可滿足問(wèn)題上，H1和H2啟發(fā)式的求解效率都要遠(yuǎn)高于dom／wdeg啟發(fā)式，啟發(fā)式生效的主要原因在于兩者為檢索過(guò)程尋找到了合適的起始點(diǎn)。在所有不可滿足樣例中，伴隨區(qū)域都是不可滿足的，通過(guò)對(duì)檢索過(guò)程中生成節(jié)點(diǎn)對(duì)應(yīng)的實(shí)例化變量進(jìn)行分析，發(fā)現(xiàn)dom／wdeg啟發(fā)式生成的多余節(jié)點(diǎn)大都對(duì)應(yīng)中心區(qū)域內(nèi)變量，只有在dom／wdeg啟發(fā)式收集到足夠信息時(shí)，檢索過(guò)程才能跳轉(zhuǎn)到邊界區(qū)域內(nèi)變量，從而快速得出問(wèn)題的不可滿足性。

通過(guò)對(duì)三種啟發(fā)式方法在可滿足問(wèn)題和不可滿足問(wèn)題上的求解效率進(jìn)行對(duì)比，H1和H2啟發(fā)式要明顯優(yōu)于dom／wdeg啟發(fā)式，其中H2啟發(fā)式方法在求解的穩(wěn)定性上要好于H1啟發(fā)式。而邊界啟發(fā)式方法生效的原因主要有以下兩點(diǎn):①啟發(fā)式篩選出的邊界變量位于問(wèn)題求解困難的部分，滿足失敗優(yōu)先原則，為檢索過(guò)程選擇了合適的起始點(diǎn)；②可以更好地發(fā)揮相容性技術(shù)在檢索過(guò)程中所能起到的作用，邊界變量賦值之后進(jìn)行相容性檢查時(shí)，約束傳播會(huì)同時(shí)朝著伴隨區(qū)域和中心區(qū)域兩個(gè)方向進(jìn)行，避免了被局限于某個(gè)局部，不僅可以壓縮問(wèn)題規(guī)模，還可以較早地發(fā)現(xiàn)指向死節(jié)點(diǎn)的無(wú)用分支?；诘诙c(diǎn)原因，dom／wdeg啟發(fā)式還可以在更加全面的解空間內(nèi)收集啟發(fā)式信息，從而給出更為合理的變量選擇。

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

基于Composed問(wèn)題結(jié)構(gòu)，提出了邊界變量的概念，并給出了在該類問(wèn)題上篩選邊界變量的方法，以此為基礎(chǔ)設(shè)計(jì)實(shí)現(xiàn)了邊界啟發(fā)式方法。通過(guò)實(shí)驗(yàn)分析，新啟發(fā)式求解效率要明顯高于原有啟發(fā)式方法。實(shí)驗(yàn)結(jié)果也表明邊界變量在該類問(wèn)題的求解過(guò)程中起著關(guān)鍵的作用。對(duì)于邊界變量，本文并沒(méi)有給出嚴(yán)格定義，直觀上邊界變量為位于問(wèn)題不同求解區(qū)域相鄰邊界上的變量。Composed問(wèn)題具有明顯的邊界區(qū)域，而且通過(guò)運(yùn)用約束弧的松緊度特性可以快速篩選出邊界變量，因此在該類問(wèn)題上進(jìn)行了關(guān)于邊界變量集有效性的分析與討論。但是文中邊界變量集的篩選方法過(guò)度依賴于Composed問(wèn)題結(jié)構(gòu)，而不具有普遍適用性，如何在具有類似結(jié)構(gòu)的眾多實(shí)際問(wèn)題中篩選出邊界變量集將是接下來(lái)工作的重點(diǎn)。文中討論只涉及到了約束弧的松緊度，顯然網(wǎng)絡(luò)密度在各局部區(qū)域的變化也是問(wèn)題結(jié)構(gòu)的重要特性，如何將二者結(jié)合給出更為通用的邊界變量集篩選方法，是改進(jìn)已有啟發(fā)式方法的重要方向。

［1］朱興軍，張永剛，李瑩，等.多值傳播的相容性技術(shù)［J］.自動(dòng)化學(xué)報(bào)，2009，35（10）:1296－1301.Zhu Xing－jun，Zhang Yong－gang，Li Ying，et al.Consistency technique of multi－value propagation［J］.Acta Automatica Sinica，2009，35（10）:1296－1301.

［2］劉春暉，朱興軍，孫吉貴，等.一種改進(jìn)的雙向Singleton弧相容算法［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，2008，38（3）:666－670.Liu Chun－h(huán)ui，Zhu Xing－jun，Sun Ji－gui，et al.Improved bidirectional Singleton arc consistency algorithm［J］.Journal of Jilin University（Engineering and Technology Edition），2008，38（3）:666－670.

［3］杜會(huì)盈，李占山，李宏博，等.圖分割在Singleton弧相容算法中的應(yīng)用［J］.吉林大學(xué)學(xué)報(bào):理學(xué)版，2010，48（6）:981－986.Dui Hui－ying，Li Zhan－shan，Li Hong－bo，et al.Graph partitioning applied in Singleton algorithm［J］.Journal of Jilin University（Science Edition），2010，48（6）:981－986.

［4］高健，孫吉貴，張永剛，等.參數(shù)化弧相容約束傳播［J］.吉林大學(xué)學(xué)報(bào):信息科學(xué)版，2007，25（2）:183－187.Gao Jian，Sun Ji－gui，Zhang Yong－gang，et al.Parameterized arc consistency constraint propagation［J］.Journal of Jilin University（Information Science Edition），2007，25（2）:183－187.

［5］van Beek Peter.Backtracking search algorithms［C］∥Handbook of Constraint Programming.Francesca Rossi，Peter van Beek，Toby Walsh（eds），New York:Elsevier，2006:85－126.

［6］Li Xing－jian，Epstein Susan L.Learning clusterbased structure to solve constraint satisfaction problems［J］.Annals of Mathematics and Artificial Intelligence，2010，60:91－117.

［7］Sabin Daniel，F(xiàn)reuder Eugene C.Contradicting conventional wisdom in constraint satisfaction［C］∥Proceedings of CP，Rosario，Orcas Island，Washington，1994:10－20.

［8］Likitvivatanavong Chavalit，Zhang Yuan－lin，Bowen James，et al.Arc consistency during search［C］∥Veloso Manuela M （eds.）.Proceedings of IJCAI，Hyderabad，India:Morgan Kaufmann，2007:137－142.

［9］Christophe Lecoutre，F(xiàn)rederic Boussemart，F(xiàn)red Hemery.Backjump－based techniques versus confict—directed heuristics［C］∥Proceedings of ICTAI，Boca Raton，F(xiàn)lorida，USA:IEEE Press，2004:549－557.

［10］Haralick Robert M，Elliott Gordon L.Increasing tree search efficiency for constraint satisfaction problems［J］.Artificial Intelligence，1980，14:263－313.

［11］Grimes Diarmuid，Wallace Richard J.Learning from failures in constraint satisfaction search［C］∥Wheeler Ruml，F(xiàn)rank Hutter，AAAI Workshop on Learning for Search，Boston， Massachusetts，USA:AAAI Press，2006.

［12］Christophe Lecoutre，F(xiàn)red Hemery.A study of residual supports in arc consistency［C］∥Veloso Manuela M（eds），Proceedings of IJCAI，Hyderabad，India，2007:125－130.

［13］Frederic Boussemart，F(xiàn)red Hemery，Christophe Lecoutre，et al.Boosting systematic search by weighting constraints［C］∥R.López De Mántaras，L.Saitta，Proceedings of ECAI，Valencia，Spain:IOS Press，2004:146－150.

［14］http:／／www.cril.univ－artois.fr／～lecoutre／benchm arks.html＃