非二元條件約束滿足問(wèn)題求解

袁際軍，黃敏鎂

（1．廣東財(cái)經(jīng)大學(xué) 金融學(xué)院，廣東 廣州 510320；2．華南師范大學(xué) 管理科學(xué)系，廣東 廣州 510006）

0 引言

約束滿足問(wèn)題（Constraint Satisfaction Problem，CSP）由一組具有有限域的變量以及限制變量間取值組合的約束構(gòu)成。CSP的解是一組對(duì)所有變量的賦值，并使得該賦值滿足所有的約束［1－2］。近三十年來(lái)，CSP因其強(qiáng)大的知識(shí)表示能力及豐富的領(lǐng)域獨(dú)立求解技術(shù)，在越來(lái)越多的現(xiàn)實(shí)領(lǐng)域中得到廣泛應(yīng)用，如調(diào)度問(wèn)題［3－4］、日程安排問(wèn)題［5］、配置問(wèn)題［6－7］等。然而，隨著上述問(wèn)題求解規(guī)模的擴(kuò)大、約束維數(shù)的多元化以及解空間變化的動(dòng)態(tài)性，使得CSP直接建模并求解上述問(wèn)題時(shí)，易遇到知識(shí)表示及求解上的困難。

為了有效處理變量在約束條件支配下動(dòng)態(tài)參與問(wèn)題求解的特性，如豪華型汽車需要配置天窗而標(biāo)準(zhǔn)型不必配置天窗（即變量“天窗”是否出現(xiàn)在最終解中，依賴于變量“汽車”的取值是豪華型還是標(biāo)準(zhǔn)型），Mittal和Falkenhainer對(duì)CSP進(jìn)行了擴(kuò)展，提出了經(jīng)典的動(dòng)態(tài)約束滿足問(wèn)題（Dynamic Constraint Satisfaction Problems，DCSP）模型［8］。DCSP模型將CSP中的變量劃分為初始變量和非初始變量?jī)深?，并引入激活性約束建模初始變量與非初始變量以及非初始變量間的條件依賴關(guān)系；通過(guò)激活性約束動(dòng)態(tài)地控制非初始變量的狀態(tài)，使之依條件動(dòng)態(tài)參與問(wèn)題求解并出現(xiàn)在最終解集中。為了區(qū)別文獻(xiàn)中已有的另一類動(dòng)態(tài)約束滿足問(wèn)題［9］，Sabin將Mittal提出的DCSP模型更名為條件約束滿足問(wèn)題（Conditional Constraint Satisfaction Problems，CCSP）［10－11］，并從二元約束的角度進(jìn)行了系統(tǒng)的研究。盡管條件約束滿足問(wèn)題及其變體，如Sabin提出的復(fù)合約束滿足問(wèn)題（composite constraint satisfaction problems）［12］、Esther提出的混合條件約束滿足問(wèn)題（Mixed and Conditional Constraint Satisfaction Problems，MCCSP）［13］、Mouhoub提出的條件復(fù)合約束滿足問(wèn)題（Conditional and Composite Constraint Satisfaction Problems，CCCSP）［5］、Dong Yang［14］以及 Lin Wang［15］提出的改進(jìn)型動(dòng)態(tài)約束滿足問(wèn)題等，在建模問(wèn)題的動(dòng)態(tài)性方面擁有更強(qiáng)的知識(shí)表示力，然而在求解條件約束滿足問(wèn)題及其變體時(shí)，上述文獻(xiàn)大都假設(shè)只考慮二元約束的情形，并給出直接或間接的求解方法。直接求解方法主要是針對(duì)CCSP的特征，在直接求解CCSP時(shí)嵌入處理CSP相似的弧一致性技術(shù)，以實(shí)現(xiàn)對(duì)CCSP的直接求解，如在回溯求解期間，嵌入前向檢查算法（Forward Checking，F(xiàn)C）或維持弧一致性（Maintaining Arc Consistency，MAC）方法［5］。為進(jìn)一步提高算法的求解效率，針對(duì)條件約束滿足問(wèn)題及其變體在處理激活性約束時(shí)，新變量的動(dòng)態(tài)引入對(duì)問(wèn)題一致性狀態(tài)的影響，Lin Wang等［15］提出了前向檢查（Forward Checking，F(xiàn)C）算法與后看檢查算法（如回跳算法（Backjumping algorithm，BJ））相結(jié)合的混合式算法FC－BJ，以增強(qiáng)傳統(tǒng)的回溯算法的求解性能；引入最先失敗原則的動(dòng)態(tài)變量排序啟發(fā)式思想，以改進(jìn)混合式算法FC－BJ的求解效率，即算法FCBJ－FF；實(shí)證表明該算法的求解性能顯著優(yōu)于求解條件約束滿足問(wèn)題的傳統(tǒng)回溯算法［8，14］。間接求解方法主要是通過(guò)將CCSP轉(zhuǎn)化為標(biāo)準(zhǔn)的CSP［13，16］，通過(guò)對(duì)CSP的求解來(lái)實(shí)現(xiàn)對(duì)CCSP的間接求解。間接求解方法在處理CCSP時(shí)，往往會(huì)由于新增約束及變量值域規(guī)模的顯著擴(kuò)大，導(dǎo)致問(wèn)題的求解規(guī)模過(guò)大，影響求解效率；同時(shí)這種轉(zhuǎn)化還易引起建模約束問(wèn)題時(shí)知識(shí)表示的不自然。Raphael等［16］基于CCSP轉(zhuǎn)換成CSP時(shí)存在的上述不足，提出兩種新的建模方法（如對(duì)象建模語(yǔ)言Alloy及回答集編程（Answer Set Programming，ASP））用于直接建模CCSP并實(shí)現(xiàn)其求解。由于CCSP向Alloy或ASP模型的轉(zhuǎn)化是直接自然的，且Alloy模型可轉(zhuǎn)化為可滿足性問(wèn)題（Satisfiability Problem，SAT）以實(shí)現(xiàn)其求解，同時(shí)ASP模型也可轉(zhuǎn)化為一種被求解器Cmodels可接受的形式以實(shí)現(xiàn)其求解，其中求解器Cmodels的內(nèi)核也是基于SAT的。然而從算法的角度而言，Raphael只是提出了如何直接建模CCSP的方法，但采用何種算法來(lái)實(shí)現(xiàn)高效的求解卻并未明確給出。

上述研究主要針對(duì)二元條件約束滿足問(wèn)題，關(guān)注回溯算法與一致性技術(shù)的結(jié)合。然而，在現(xiàn)實(shí)問(wèn)題中，非二元約束出現(xiàn)得非常頻繁。利用非二元約束滿足問(wèn)題領(lǐng)域的已有理論，直接拓展二元條件約束滿足問(wèn)題求解方法，以實(shí)現(xiàn)對(duì)非二元條件約束滿足問(wèn)題的直接求解，是一種可供嘗試的求解途徑。在非二元約束滿足問(wèn)題求解方面，目前存在一些較好的算法，如非二元弧一致性（non－binary Forward Checking，nFC）算法［17］、廣義弧一致性（Generalized Arc Consistency 2001/3．1，GAC2001/3．1）算法［18］、域過(guò)濾一致性算法［19］、關(guān)系鄰域逆一致性（Relational Neighborhood Inverse Consistency，RNIC）算法［20］等。域過(guò)濾一致性算法與關(guān)系鄰域逆一致性算法RNIC具有強(qiáng)局部一致性特征，在大規(guī)模難問(wèn)題求解時(shí)具有一定的優(yōu)勢(shì)。其中，算法RNIC主要應(yīng)用于非二元約束滿足問(wèn)題的對(duì)偶圖上。在問(wèn)題規(guī)模不大時(shí)，實(shí)施非二元弧一致算法或廣義弧一致算法，會(huì)因每次約束檢查時(shí)代價(jià)的降低而帶來(lái)算法總體效率的提高。然而，在求解非二元條件約束滿足問(wèn)題時(shí)，不同于二元CSP中的約束傳播方法可直接嵌入到二元CCSP的求解過(guò)程中，有些適用于非二元CSP的經(jīng)典約束傳播方法［17］，如nFC1、nFC2和nFC3，并不適用于直接嵌入到帶有非二元約束的條件約束滿足問(wèn)題的求解過(guò)程中。

本文的關(guān)注焦點(diǎn)在于實(shí)現(xiàn)對(duì)非二元條件約束滿足問(wèn)題的直接求解。

1 非二元條件約束滿足問(wèn)題

非二元條件約束滿足問(wèn)題（Non－binary Conditional Constraint Satisfaction Problem，NCCSP）是一個(gè)五元組P＝（V，VI，D，C，A），其中：

（1）集合V 表示一組變量，即V＝｛vi｜i∈｛1，2，…，n｝｝，n表示不同變量的個(gè)數(shù)。對(duì)于任一變量vi∈V，存在三種可能狀態(tài)，即活動(dòng)變量（active：vi）、非活動(dòng)變量（?active：vi或inactive：vi）與未定義變量（undefined：vi）。處于活動(dòng)狀態(tài)的變量參與問(wèn)題求解，且在求解過(guò)程中需指派域值；處于非活動(dòng)狀態(tài)的變量在求解過(guò)程中禁止指派域值；處于未定義狀態(tài)的變量指該變量此時(shí)尚未激活，不參與問(wèn)題求解。

（2）集合VI表示一組非空初始變量，且有VI?V。對(duì)于任一變量vj∈VI，均處于活動(dòng)變量狀態(tài)。

（3）集合D表示一組與變量相對(duì)應(yīng)的值域，即D＝｛D（vi）｜i∈｛1，2，…，n｝｝。其中，D（vi）表示變量vi的值域，本文僅研究離散有限域變量。

（4）集合C表示一組兼容性約束，即C＝｛Cj｜j∈｛1，2，…，｜C｜｝∧S（Cj）?V｝，｜C｜表示不同兼容性約束的個(gè)數(shù)，變量集合S（Cj）稱為第j個(gè)約束Cj的作用范圍。對(duì)于?S（Cj）＝｛vji｜i＝1，2，…，｜S（Cj）｜｝，則 有 Cj?D（vj1）×D（vj2）× … ×D（vj｜S（Cj）｜）成立。若?Ci∈C，使得｜S（Ci）｜＞2，則稱該Ci為非二元兼容性約束。如果兼容性約束Cj作用范圍中所有變量處于活動(dòng)變量狀態(tài)，則該約束稱為被激活的兼容性約束；在求解過(guò)程中，僅被激活的兼容性約束參與問(wèn)題求解。

（5）集合A表示一組激活性約束。激活性約束分為包含性約束和排斥性約束：①包含性約束形如：（ ，…， ）incl， ，…， ，

Ccondvivj?vk其中條件變量為vivj目

標(biāo)變量為vk，且有vk?｛v1，…，vj｝，當(dāng)條件變量（vi，…，vj）的一組指派與約束條件Ccond（vi，…，vj）一致時(shí)，目標(biāo)變量vk將被觸發(fā)為活動(dòng)變量狀態(tài)；②排斥（ ，…， ）excl，性約束形如：Ccondvivj?vk其中目標(biāo)變量vk?｛v1，…，vj｝。當(dāng)條件變量（vi，…，vj）的一組指派與約束條件Ccond（vi，…，vj）一致時(shí)，目標(biāo)變量vk將被觸發(fā)為非活動(dòng)變量狀態(tài)。

定義1 非二元條件約束滿足問(wèn)題的解。NCCSP的解是對(duì)所有處于活動(dòng)變量狀態(tài)的一個(gè)指派Ti，并使得該指派Ti必須滿足如下兩個(gè)要求：①在Ti中的所有變量及其賦值必須滿足C∪A；②不存在Ti的子集仍然是NCCSP的一個(gè)解。

定義2 約束投影。給定一個(gè)約束Ci及約束作用范圍S（Ci）的子集Sj，將Sj在約束Ci中對(duì)應(yīng)變量的域值組合加以截留，形成一個(gè)作用在變量集合Sj上新的約束關(guān)系，這種新的約束關(guān)系稱為約束Ci在變量集合Sj上的約束投影。令Sj?S（Ci），則Ci在Sj上的約束投影形成的新約束記為πSj（Ci）。

定義3 非二元弧一致性。若?t∈Cj，使得dk∈π｛vi｝（t）成立，則稱變量vi的域值dk與約束Cj具有一致性。若?dr∈D（vi），?t∈Cj，使得dr∈π｛vi｝（t）成立，則稱變量vi與兼容性約束Cj具有一致性。若非二元兼容性約束Cj作用范圍S（Cj）中的任一變量vk都與約束Cj具有一致性，則稱兼容性Cj是非二元弧一致的。若兼容性約束集合C中的任一約束Ci都是非二元弧一致的，則稱兼容性約束集合C是非二元弧一致的。

在NCCSP的求解過(guò)程中，動(dòng)態(tài)地構(gòu)建與NCCSP相關(guān)的約束網(wǎng)絡(luò)。在該約束網(wǎng)絡(luò)中，所有變量均處于活動(dòng)變量狀態(tài)，在求解過(guò)程中這些變量均需被指派域值，NCCSP的解由約束網(wǎng)絡(luò)中的所有變量及其相應(yīng)賦值組成。

2 非二元條件約束滿足問(wèn)題求解算法

非二元條件約束滿足問(wèn)題是非二元約束滿足問(wèn)題 （Non－binary Constraint Satisfaction Problem，NCSP）與二元條件約束滿足問(wèn)題（Binary Conditional Constraint Satisfaction Problem，BCCSP）的進(jìn)一步泛化。為了處理NCCSP求解過(guò)程中約束維數(shù)的非二元性及參與求解變量規(guī)模的動(dòng)態(tài)可變性，本文借鑒處理NCSP和BCCSP的求解方法［10，11，17］，提出下述兩種不同類型的非二元條件約束滿足問(wèn)題求解算法。

2．1 非二元條件約束滿足問(wèn)題求解的回溯算法

回溯搜索方法是求解約束滿足問(wèn)題的基本方法。根據(jù)NCCSP的性質(zhì)，問(wèn)題中主要存在激活性約束和兼容性約束兩種不同類型的約束。回溯過(guò)程中，采用深度優(yōu)先搜索策略；對(duì)每一變量賦值時(shí)，相繼嵌入激活性約束檢查與兼容性約束檢查，以求解NCCSP。非二元條件約束滿足問(wèn)題求解的回溯算法流程如圖1所示。2．1．1 非二元條件約束滿足問(wèn)題回溯算法

非二元條件約束滿足問(wèn)題回溯算法（Backtrack Search for Non－binary Conditional Constraint Satisfaction Problem，NCCSP－BT）主要采用深度優(yōu)先方式遍歷整個(gè)搜索樹(shù)（算法1）：首先從變量集合Vactive（注：Vactive初始化時(shí)所含的變量為NCCSP中的所有初始變量VI）中挑選一個(gè)未賦值變量，作為當(dāng)前變量vrb，并從當(dāng)前變量值域D｛vrb｝中挑選域值d，實(shí)例化該變量vrb；然后針對(duì)當(dāng)前變量的賦值，相繼調(diào)用子程序激活性約束檢查算法activity（）和兼容性約束檢查算法compatibility（）進(jìn)行沖突性檢查，若無(wú)沖突產(chǎn)生，則從更新后的變量集合Vactive中挑選另一未賦值變量，作為當(dāng)前變量并進(jìn)行遞歸搜索；若出現(xiàn)沖突，則恢復(fù)原有信息，再?gòu)腄｛vrb｝中挑選另一域值，實(shí)例化當(dāng)前變量并重復(fù)之前的操作；若D｛vrb｝中的所有域值被遍歷后仍有沖突產(chǎn)生，則回溯到上一階段。程序的終止主要以求解到所需要的解或發(fā)現(xiàn)無(wú)解為止。

算法1 非二元條件約束滿足問(wèn)題回溯算法（NCCSP－BT）。

boolean NCCSP－BT（i，Vactive，D，C，A，B，values）｛

if（變量i的值大于集合Vactive中元素個(gè)數(shù)之和）return true//獲得一個(gè)可行解

vrb←Vactive（i）// 從列表 Vactive中獲取當(dāng)前待賦值變量vrb

for each（d∈D｛vrb｝）｛

將域值d賦予當(dāng)前變量vrb，并將信息添加到values中

V1←Vactive；B1←B；values1←values；

if（activity（vrb，Vactive，values，A，B）and（compatibility（vrb，Vactive，values，C））｛

i←i＋1；NCCSP－BT（i，Vactive，D，C，A，B，values）；i←i－1｝

Vactive←V1；B←B1；values←values1｝

return false｝//結(jié)束 NCCSP－BT（）2．1．2 對(duì)激活性約束檢查的處理

根據(jù)激活性約束的定義，當(dāng)約束條件中的條件變量未全賦值或條件變量的賦值不滿足約束條件時(shí)，激活性約束中的目標(biāo)變量將不會(huì)被觸發(fā)。因此，對(duì)激活性約束的檢查，僅需要檢查約束條件在當(dāng)前變量賦值下被滿足時(shí)，其觸發(fā)的目標(biāo)變量激活性狀態(tài)對(duì)搜索空間所造成的影響。

在回溯搜索過(guò)程中，激活性約束檢查算法（算法2）對(duì)激活性約束的處理如下：①在激活性約束集合A中，挑選條件變量（包含當(dāng)前賦值變量vrb）已實(shí)例化的所有激活性約束，組成新的約束集合AA。②對(duì)激活性約束AA中的每條約束a進(jìn)行檢查：若a的約束條件不被values中的相應(yīng)條件變量賦值滿足時(shí)，則當(dāng)前變量vrb的賦值視為對(duì)約束a無(wú)影響；若a的約束條件被滿足時(shí)，當(dāng)前變量vrb的賦值可能會(huì)引發(fā)兩類沖突而導(dǎo)致該賦值不可行，即包含性約束觸發(fā)的目標(biāo)變量已處于活動(dòng)變量狀態(tài)，或排斥性約束觸發(fā)的目標(biāo)變量已處于非活動(dòng)變量狀態(tài)；若無(wú)沖突產(chǎn)生，則在結(jié)構(gòu)數(shù)組B中記錄新觸發(fā)的活動(dòng)變量和非活動(dòng)變量歷史信息，并在變量列表Vactive中添加新觸發(fā)的活動(dòng)變量。

算法2 激活性約束檢查算法。

boolean activity（vrb，Vactive，values，A，B）｛

//Vactive是活動(dòng)變量列表

令Vactive＝Vassign∪Vunassign

//Vassign是Vactive中已賦值變量列表（包括當(dāng)前賦值變量vrb）

//Vunassign是Vactive中未賦值變量列表

AA←｛ai｜ai∈A∧cond（ai）?Vassign∧vrb∈cond（ai）｝

//A是激活性約束集合，cond（ai）是激活性約束ai的條件變量集

for each（a∈AA）｛

if（a的條件約束被values滿足）｛

//values保存迄今已實(shí)例化變量的賦值信息

i

f（a是包含性約束）｛i

f（a的目標(biāo)變量此前已被觸發(fā)為非活動(dòng)變量狀態(tài)）return false else if（a的目標(biāo)變量此前未被觸發(fā)）｛

Vactive←Vactive∪｛a的目標(biāo)變量｝

在結(jié)構(gòu)數(shù)組B中添加a的目標(biāo)變量的歷史信息｝｝

else｛//a是排斥性約束

if（a的目標(biāo)變量此前已被觸發(fā)為活動(dòng)變量狀態(tài)）return false

else if（a的目標(biāo)變量此前未被觸發(fā)）｛

在結(jié)構(gòu)數(shù)組B中添加a的目標(biāo)變量的歷史信息｝｝｝

return true｝//結(jié)束activity（）2．1．3 對(duì)兼容性約束檢查的處理

在回溯搜索過(guò)程中，每次實(shí)例化當(dāng)前變量時(shí)，均需進(jìn)行兼容性約束檢查，以檢測(cè)該變量的實(shí)例化是否與相關(guān)約束沖突。如果兼容性約束所涉及的受約束變量中不包含當(dāng)前變量，或除當(dāng)前變量外還有其他尚未實(shí)例化的變量，則對(duì)當(dāng)前變量的實(shí)例化不會(huì)違反此兼容性約束。因此，約束檢查時(shí)，只需檢查與當(dāng)前變量相關(guān)的兼容性約束。

在兼容性約束檢查算法中（算法3），令Vassign是活動(dòng)變量集合Vactive中的已賦值變量子集，Vunassign是Vactive中的未賦值變量子集，S（Cj）是兼容性約束Cj的約束作用范圍，值組values是對(duì)迄今已實(shí)例化變量的一組指派。算法首先從兼容性約束集合C中，挑選約束作用范圍由當(dāng)前變量vrb和已賦值變量所構(gòu)成的兼容性約束子集CC（注：CC＝｛Cj｜Cj∈C∧S（Cj）?Vassign∧vrb∈S（Cj）｝）；然后對(duì)每條兼容性約束CCj∈CC進(jìn)行沖突性檢測(cè)，若值組values在約束作用范圍S（CCj）上的約束投影π｛S（CCj）｝（values）不滿足約束CCj，則表明當(dāng)前變量vrb賦值與該約束相沖突，使得當(dāng)前變量賦值不可行。

算法3 兼容性約束檢查算法。

boolean compatibility（vrb，Vactive，values，C）｛

令Vactive＝Vassign∪Vunassign

//Vassign是Vactive中已賦值變量列表，Vunassign是Vactive中未賦值變量列表

CC←｛Cj｜Cj∈C∧S（Cj）?Vassign∧vrb∈S（Cj）｝

for each（CCj∈CC）｛//vrb是當(dāng)前賦值變量

if（π｛S（CCj）｝（values）?CCj）return false｝

return true｝//結(jié)束compatibility（）

回溯算法在求解需要較少回溯次數(shù)或無(wú)回溯次數(shù)就能得到解的約束問(wèn)題時(shí)，具有較大的優(yōu)勢(shì)。相對(duì)其他求解算法而言，在回溯過(guò)程中導(dǎo)致搜索失敗的相同因素反復(fù)出現(xiàn)，是使得回溯算法求解效率低下的主要原因。如果在搜索過(guò)程中無(wú)視這些因素，將導(dǎo)致過(guò)多無(wú)效回溯，從而使得算法求解效率低下。因而對(duì)回溯算法的改進(jìn)就在于盡可能早地發(fā)現(xiàn)這些影響因素。為此，下面提出一種 “前看”搜索策略，以便提前探測(cè)出這些因素并加以處理。

2．2 非二元條件約束滿足問(wèn)題求解的前向檢查算法

前向約束傳播策略［17］是指在求解期間，針對(duì)當(dāng)前變量的賦值，對(duì)參與問(wèn)題求解的變量空間，實(shí)施一定程度的局部弧一致性技術(shù)，提前剪除所有未賦值變量值域中與已賦值變量（包括當(dāng)前賦值變量）相沖突的域值，盡早探知無(wú)解分支，達(dá)到減少搜索空間、提高求解效率的目的。依據(jù)非二元條件約束滿足問(wèn)題的特征，結(jié)合前向約束傳播策略的思想，本文提出求解非二元條件約束滿足問(wèn)題的前向檢查算法，如圖2所示。

2．2．1 求解NCCSP的前向檢查算法

類似于非二元條件約束滿足問(wèn)題回溯算法，前向檢查算法同樣采用深度優(yōu)先方式遞歸遍歷整個(gè)搜索樹(shù)。區(qū)別在于回溯算法（算法1）采用“回看”的搜索策略，即在每次實(shí)例化當(dāng)前變量后，總是檢查當(dāng)前變量的賦值是否與已賦值變量產(chǎn)生沖突；而非二元條件前向檢查算法則采用“前看”的搜索策略，即在每次實(shí)例化當(dāng)前變量后，檢查未賦值變量的值域中哪些域值和已賦值變量（包含當(dāng)前變量）產(chǎn)生沖突，并剔除這些與已賦值變量不一致的未賦值變量域值。根據(jù)在前向檢查中實(shí)施弧一致性程度的不同，前向檢查算法又細(xì)分為基于NFC4的非二元條件前向檢查算法（NCCSP－NFC4）和基于NFC5的非二元條件前向檢查算法（NCCSP－NFC5）。NCCSPNFC4算法對(duì)搜索過(guò)程中每次當(dāng)前變量賦值后的瞬時(shí)狀態(tài)，通過(guò)先后調(diào)用子程序activity（）和NFC4（），采用“前看”的搜索策略判斷當(dāng)前的變量賦值是否可行，實(shí)施方法見(jiàn)算法4；而NCCSP－NFC5算法則對(duì)搜索過(guò)程中的每次當(dāng)前變量賦值后的瞬時(shí)狀態(tài)，通過(guò)先后調(diào)用子程序activity（）和NFC5（），采用“前看”的搜索策略判斷當(dāng)前的變量賦值是否可行，實(shí)施方法見(jiàn)算法5。與回溯算法（算法1）相似，這兩類前向檢查算法程序主要以求解到所需要的解或發(fā)現(xiàn)無(wú)解而終止。

算法4 基于NFC4的非二元條件前向檢查算法（NCCSP－NFC4算法）。

boolean NCCSP－NFC4（i，Vactive，D，C，A，B，values）｛

if（變量i的值大于集合Vactive中元素個(gè)數(shù)之和）return true//獲得一個(gè)可行解

vrb←Vactive（i）//Vactive保存一組被觸發(fā)的活動(dòng)變量

for each（d∈D｛vrb｝）｛//vrb是當(dāng)前賦值變量

將域值d賦予當(dāng)前變量vrb，并將信息添加到values中；

V1←Vactive；B1←B；values1←values；D1←D；

if（activity（vrb，Vactive，values，A，B）and（NFC4（D，C，Vactive，values））｛

i←i＋1；NCCSP－BT（i，Vactive，D，C，A，B，values）；i←i－1｝

Vactive←V1；B←B1；values←values1；D←D1｝return false

｝//結(jié)束 NCCSP－NFC4（）

算法5 基于NFC5的非二元條件前向檢查算法（NCCSP－NFC5算法）。

boolean NCCSP－NFC5（i，Vactive，D，C，A，B，values）｛

if（變量i的值大于集合Vactive中元素個(gè)數(shù)之和）return true//獲得一個(gè)可行解

vrb←Vactive（i）//Vactive是一組被激活的包含性變量

for each（d∈D｛vrb｝）｛//vrb是當(dāng)前賦值變量

將域值d賦予當(dāng)前變量vrb，并將信息添加到values中；

V1←Vactive；B1←B；values1←values；D1←D；

if（activity（vrb，Vactive，values，A，B）and（NFC5（D，C，Vactive，values））｛

i←i＋1；NCCSP－BT（i，Vactive，D，C，A，B，values）；i←i－1｝

Vactive←V1；B←B1；values←values1；D←D1｝

return false

｝//結(jié)束 NCCSP－NFC5（）

2．2．2 對(duì)激活性約束檢查的處理

兼容性約束與激活性約束處理的先后順序?qū)λ惴ǖ男示哂休^大影響。在面向非二元條件約束滿足問(wèn)題的前向檢查算法中，針對(duì)當(dāng)前變量的賦值，如果先進(jìn)行兼容性約束弧一致操作再進(jìn)行激活性約束檢查操作，則在對(duì)激活性約束進(jìn)行處理后，當(dāng)有新的目標(biāo)變量被激活并加入待求解的問(wèn)題空間時(shí)，就需要對(duì)這部分被激活的新變量再次實(shí)施弧一致性處理，以便在下一階段挑選出未賦值變量進(jìn)行賦值時(shí)，當(dāng)前問(wèn)題已經(jīng)處于一定程度的弧一致?tīng)顟B(tài)。因此，為防止上述繁瑣處理過(guò)程，本文在求解過(guò)程中針對(duì)當(dāng)前變量賦值，均遵循先檢查激活性約束、再檢查兼容性約束的順序，以提高算法求解效率。其中，激活性約束檢查過(guò)程與2．1．2節(jié)方法相同。

2．2．3 對(duì)非二元條件前向檢查中約束傳播過(guò)程的處理

在非二元條件約束滿足問(wèn)題求解期間，設(shè)Vi是變量xi賦值后第i個(gè)瞬時(shí)狀態(tài)對(duì)應(yīng)的所有活動(dòng)變量，Vj是變量xj賦值后第j個(gè)瞬時(shí)狀態(tài)對(duì)應(yīng)的所有活動(dòng)變量，并假定第j個(gè)瞬時(shí)狀態(tài)是第i個(gè)瞬時(shí)狀態(tài)的后繼狀態(tài)；由于所有非初始變量（V－VI）在求解期間并非總是參與問(wèn)題求解，可假設(shè)Vi≠Vj。令Vi→j＝Vj－Vi，則Vi→j是變量Cactivep，f賦值后所觸發(fā)的一組新增活動(dòng)變量。令Cactivej（Cactivej?C）是與第j個(gè)瞬時(shí)狀態(tài)對(duì)應(yīng)的一組被激活的約束，且有Cactivep，f＝

Cactivec，f∪（Cactivep，f－Cactivec，f）∪Cactivep，p∪Cactivef，f。其中：Cactivec，f 表示包含一個(gè)當(dāng)前賦值變量xj和至少一個(gè)未賦值變量的所有被激活的兼容性約束；Cactivep，f表示包含至少一個(gè)已賦值變量（當(dāng)前變量xj也視為已賦值變量）和至少一個(gè)未賦值變量的所有已激活的兼容性約束；Cactivep，p表示一組約束范圍是已賦值變量構(gòu)成的被激活的兼容性約束；Cactivef，f表示一組約束范圍是未賦值變量構(gòu)成的被激活的兼容性約束。假設(shè)Vi－j中存在變量xj1和xj2，且有xj1∈S（ck）∧ck∈Cactivec，f及xj2∈S（ct）∧ct∈（Cactivep，f－Cactivec，f）；根據(jù)文獻(xiàn)［17］中的弧一致方法nFC1、nFC2和nFC3，若在約束傳播過(guò)程中的第j個(gè)瞬時(shí)狀態(tài)對(duì)約束集合Cactivec，f嵌入弧一致操作，則與約束集合Cactivec，f相關(guān)的Vi→j中的變量（如xj1）的域值與已賦值變量具有一致性，但并不能保證與約束集合Cactivec，f無(wú)關(guān)的Vi→j中變量（如xj2）的域值也與已賦值變量具有一致性。因此，弧一致方法nFC1，nFC2和nFC3不能直接應(yīng)用于第j個(gè)瞬時(shí)狀態(tài)。若在約束傳播過(guò)程中的第j個(gè)瞬時(shí)狀態(tài)以約束集合Cactivep，f為弧一致處理對(duì)象，則Vi→j中的變量在弧一致處理后，與已賦值變量不一致的域值將被剔除，從而使變量集合Vj處于一致性狀態(tài)。因此，文獻(xiàn)［17］中的弧一致方法nFC4和nFC5可直接應(yīng)用于第j個(gè)瞬時(shí)狀態(tài)。

根據(jù)上述分析，在約束傳播過(guò)程中提出兩種非二元條件弧一致方法，即 NFC4和NFC5（算法NFC4和NFC5的基本思想分別來(lái)自于弧一致方法nFC4和nFC5）。其中：①NFC4：僅對(duì)集合Cactivep，f中的所有兼容性約束實(shí)施一遍非二元弧一致性僅，并剔除未賦值變量值域中與已賦值變量不一致的域值；如果在此過(guò)程中發(fā)現(xiàn)某個(gè)未賦值變量值域變?yōu)榭占?，則表明探測(cè)到了一個(gè)無(wú)解分支，說(shuō)明當(dāng)前變量賦值不可行，實(shí)施方法見(jiàn)算法6。②NFC5：對(duì)集合Cactivep，f中的所有兼容性約束實(shí)施非二元弧一致，使所有兼容性約束在實(shí)施非二元弧一致性處理后均達(dá)到弧一致?tīng)顟B(tài)；如果在此過(guò)程中發(fā)現(xiàn)某個(gè)未賦值變量值域變?yōu)榭占?，則表明探測(cè)到了一個(gè)無(wú)解分支，說(shuō)明當(dāng)前變量賦值不可行，實(shí)施方法見(jiàn)算法7。

算法6 NFC4算法。

boolean NFC4（D，C，Vactive，values）｛

令Vactive＝Vp∪Vf

//Vp是Vactive中已賦值變量（包括當(dāng)前賦值變量）集合，Vf是Vactive中未賦值變量集合

Cactive← ｛Cj｜Cj∈C∧S（Cj）?Vactive

｝p，f0（S（C）－V）S（C）∧ ＜｜jp｜＜｜j｜

for each（c∈Capc，tfive）｛

for each（v∈（S（c）∩Vf））｛

//v是兼容性約束c作用范圍中的未賦值變量

for each（val∈D｛v｝）｛

if（not（變量v的域值val與約束c具有一致性））｛D｛v｝←D｛v｝－｛val｝

If（D｛v｝等于空集）return false｝｝｝｝

return true｝//結(jié)束NFC4（）

算法7 NFC5算法。

boolean NFC5（D，C，Vactive，values）｛令 Vactive＝Vp∪Vf；

Cactive← ｛Cj｜Cj∈C∧S（Cj）?Vactive

｝；p，f0（S（C）－V）S（C）∧ ＜｜jp｜＜｜j｜

CC←Capc，tfive

；while（CC≠?）｛

CC←CC－｛Cj｝；

for each（v∈（S（Cj）∩Vf））｛

//v是兼容性約束c作用范圍中的未賦值變量

revise＝false；

for each（val∈D｛v｝）｛

if（not（變量v的域值val與約束c具有一致性））｛

D｛v｝←D｛v｝－｛val｝；revise＝true｝｝if（revise＝＝true）｛

if（D｛v｝等于空集）return false；CC←CC∪｛Ci｜Ci∈Capc，tfive∧v∈S（Ci）∧i≠j｝｝｝｝return true｝//結(jié)束NFC5（）

2．3 算例

變量集V＝｛v1，v2，v3，v4，v5，v6｝，其中初始變量集VI＝｛v1，v2，v3，v4｝。每個(gè)變量的值域D都是｛e，f，g｝，兼容性約束｛C1，C2，C3｝與激活性約束｛A1，A2，A3｝分別如表1所示。

為闡述3種算法間的差異，表2和表3分別展示了一個(gè)簡(jiǎn)單算例的處理過(guò)程。它由4個(gè)初始變量｛v1，v2，v3，v4｝和2個(gè)非初始變量｛v5，v6｝組成，每個(gè)變量分享相同的值域｛e，f，g｝，服從3個(gè)兼容性約束｛C1，C2，C3｝和3個(gè)激活性約束｛A1，A2，A3｝。其中：A1和A2是包含性約束，A3是排斥性約束。

表1兼容性約束與激活性約束表示

表2 變量v1 和v2相繼實(shí)例化時(shí)不同算法對(duì)約束處理的差異

表3 變量v1和v2相繼實(shí)例化時(shí)不同算法所致的域值過(guò)濾

在變量v1賦值e（即（v1，e））之后，沒(méi)有約束含有兩個(gè)已實(shí)例化的變量（包括當(dāng)前變量v1）。因此，算法NCCSP－NBT對(duì)非初始變量｛v5，v6｝的當(dāng)前狀態(tài)無(wú)影響，也不過(guò)濾任何變量的域值。算法NCCSP－NFC4對(duì)激活性約束｛A1，A2，A3｝和兼容性約束C3無(wú)影響；在先后對(duì)約束C1和C2應(yīng)用非二元弧一致方法后，從D｛v2｝、D｛v3｝和D｛v4｝中刪除了域值g。值得注意的是，如果以不同的順序處理這些約束，過(guò)濾效果將會(huì)有所不同。算法NCCSP－NFC5對(duì)激活性約束｛A1，A2，A3｝和兼容性約束C3無(wú)影響；在對(duì)約束集｛C1，C2｝應(yīng)用非二元弧一致方法后，從D｛v2｝中刪除了域值f和g，從D｛v3｝和D｛v4｝中刪除了域值g。

在變量v2賦值e（即（v2，e））之后，激活性約束A1和A3的約束條件分別得到滿足。因此，算法NCCSP－NBT對(duì)A1和A3處理之后，導(dǎo)致變量v5的狀態(tài)由未定義變?yōu)榛顒?dòng)狀態(tài)，變量v6的狀態(tài)由未定義變?yōu)榉腔顒?dòng)狀態(tài)；由于約束C1、C2和C3所包含的變量未完全實(shí)例化，所有算法NCCSP－NBT對(duì)所有兼容性約束無(wú)影響，也不過(guò)濾任何變量的域值。算法NCCSP－NFC4先對(duì)激活性約束A1和A3進(jìn)行檢查，然后對(duì)兼容性約束C1、C2和C3實(shí)施一遍非二元弧一致；導(dǎo)致變量v5的狀態(tài)由未定義變?yōu)榛顒?dòng)狀態(tài)，變量v6的狀態(tài)由未定義變?yōu)榉腔顒?dòng)狀態(tài)；從D｛v3｝中刪除了域值f，從D｛v5｝中刪除了域值f和g。算法NCCSP－NFC5先對(duì)激活性約束A1和A3進(jìn)行檢查，再對(duì)約束｛C1，C2，C3｝實(shí)施弧一致方法，直至所有兼容性約束達(dá)到弧一致?tīng)顟B(tài)；導(dǎo)致變量v5的狀態(tài)由未定義變?yōu)榛顒?dòng)狀態(tài)，變量v6的狀態(tài)由未定義變?yōu)榉腔顒?dòng)狀態(tài)；從D｛v3｝中刪除了域值f，從D｛v4｝中刪除了域值f，從D｛v5｝中刪除了域值f和g。

3 算法復(fù)雜性分析

為了更好地衡量非二元條件約束滿足問(wèn)題回溯算法與兩類前向檢查算法的性能，本章給出最壞情況下的時(shí)間復(fù)雜度分析，然后證明其正確性。

定理1 非二元條件約束滿足問(wèn)題回溯算法（NCCSP－BT算法）在每個(gè)節(jié)點(diǎn)最壞的情況下，所消耗的時(shí)間復(fù)雜度是O（tam｜A｜＋m｜C｜）。

證明 在實(shí)例化變量xi時(shí)，令A(yù)Ai為約束條件包含變量xi的一組激活性約束，CCi為約束范圍包含變量xi的一組兼容性約束。

（1）令A(yù)Ai中激活性約束aij包含的目標(biāo)變量個(gè)數(shù)為tij，則D｛xi｝中的每個(gè)域值d實(shí)例化xi時(shí)，若滿足激活性約束aij的約束條件，則需進(jìn)一步檢查每個(gè)目標(biāo)變量是否與已知狀態(tài)產(chǎn)生沖突。因此，實(shí)例化變量xi時(shí)，對(duì)激活性約束aij檢查的時(shí)間復(fù)雜度為O（tij｜D｛xi｝｜）。如果變量的域值規(guī)模最大為m，激活性約束所觸發(fā)的目標(biāo)變量數(shù)目最大為ta，激活性約束AAi最壞情況下的最大規(guī)模為｜A｜，則實(shí)例化變量xi時(shí)，最壞情況下對(duì)所有相關(guān)激活性約束檢查的時(shí)間復(fù)雜度為O（tam｜A｜）。

（2）實(shí)例化變量xi時(shí)，對(duì)每一條兼容性約束的一致性檢查，最壞情況下的時(shí)間復(fù)雜度為O（m）；若CCi最壞情況下的規(guī)模最大為｜C｜，則實(shí)例化變量xi時(shí)，最壞情況下對(duì)所有相關(guān)兼容性約束檢查的時(shí)間復(fù)雜度為O（m｜C｜）。由于NCCSP＿BT算法的性能主要由激活性約束檢查與兼容性約束檢查決定，在最壞情況下，對(duì)每個(gè)節(jié)點(diǎn)所消耗的時(shí)間復(fù)雜度是O（tam｜A｜＋m｜C｜）。

定理2 非二元條件前向檢查算法NCCSPNFC4和NCCSP－NFC5在每個(gè)節(jié)點(diǎn)最壞的情況下，具有相同的時(shí)間復(fù)雜度O（tam｜A｜＋（rc－1）mrc－1｜Cactivep，f｜）。

證明 在實(shí)例化變量xi時(shí)，令Cactivep，f表示包含至少一個(gè)已賦值變量（當(dāng)前變量xi也視為已賦值變量）和至少一個(gè)未賦值變量的所有已激活的兼容性約束。設(shè)Cactivep，f中的一條兼容性約束ci的約束維數(shù)為ri，則算法 NCCSP－NFC4對(duì)ci檢查時(shí)，ci中至多包含ri－1個(gè)未賦值變量。因此，在對(duì)ci實(shí)施弧一致性時(shí)，最壞情況下算法NCCSP－NFC4的時(shí)間復(fù)雜度為O（（ri－1）mri－1）。如果Cactivep，f中兼容性約束的最大維數(shù)為rc，則在實(shí)例化變量xi時(shí)，最壞情況下算法NCCSP－NFC4對(duì)兼容性約束檢查的時(shí)間復(fù)雜度為O（（rc－1）mrc－1｜Cactivep，f｜）。由定理1的分析可知，在實(shí)例化變量xi時(shí)，對(duì)激活性約束檢查的時(shí)間復(fù)雜度為O（tam｜A｜）。因此，算法NCCSP－NFC4在每個(gè)節(jié)點(diǎn)最壞情況下所消耗的時(shí)間復(fù)雜度為O（tam｜A｜＋（rc－1）mrc－1｜Cactivep，f｜）。

在搜索過(guò)程中，對(duì)于給定的節(jié)點(diǎn)，算法NCCSPNFC4和NCCSP－NFC5的主要區(qū)別在于對(duì)兼容性約束集合Cactivep，f實(shí)施弧一致性程度的不同。算法NCCSP－NFC4僅對(duì)Cactivep，f中的約束實(shí)施一次弧一致，而算法NCCSP－NFC5對(duì)Cactivep，f實(shí)施弧一致直到所有約束都處于弧一致性狀態(tài)。文獻(xiàn)［17，21］表明，在嵌入某種優(yōu)化算法如GAC2001時(shí)，算法NCCSPNFC4和 NCCSP－NFC5對(duì)Cactivep，f實(shí)施弧一致，可具有相同的最壞時(shí)間復(fù)雜度。

4 應(yīng)用實(shí)例分析與基于隨機(jī)問(wèn)題的仿真實(shí)驗(yàn)

4．1 評(píng)價(jià)指標(biāo)

對(duì)非二元條件約束滿足問(wèn)題求解算法性能的衡量，本文主要采用如下評(píng)價(jià)指標(biāo)：①求解時(shí)間，指在求得問(wèn)題的一個(gè)可行解或無(wú)解時(shí)所耗費(fèi)的運(yùn)行時(shí)間；②回溯次數(shù)，指在求解過(guò)程中遇到一個(gè)無(wú)解狀態(tài)而不得不回溯到前一求解狀態(tài)的次數(shù)；③兼容性約束檢查次數(shù)，指在判斷當(dāng)前變量賦值是否為一個(gè)有效賦值而對(duì)兼容性約束進(jìn)行檢查的有效次數(shù)；④條件約束檢查次數(shù)，指對(duì)當(dāng)前變量賦值后，判斷目標(biāo)變量是否被觸發(fā)而對(duì)激活性約束進(jìn)行檢查的次數(shù)。

4．2 NCCSP的應(yīng)用實(shí)例

4．2．1 應(yīng)用實(shí)例及建模

在產(chǎn)品配置領(lǐng)域，功能與實(shí)現(xiàn)該功能的組件間是典型的多對(duì)多關(guān)系。根據(jù)“關(guān)鍵組件理論”［8，22］，每個(gè)功能都存在實(shí)現(xiàn)其功能的關(guān)鍵組件，該關(guān)鍵組件要么完整地實(shí)現(xiàn)該功能，要么和其他非關(guān)鍵組件共同作用實(shí)現(xiàn)該功能。一旦實(shí)現(xiàn)某一功能的關(guān)鍵組件被確定，則與之相關(guān)的非關(guān)鍵組件也需要隨之依條件動(dòng)態(tài)確定。另外，關(guān)鍵組件存在不同的組件類型，不同的組件類型所實(shí)現(xiàn)的功能也存在差異，從而導(dǎo)致實(shí)現(xiàn)某一特定功能所需配套的非關(guān)鍵組件集也不相同。在建模為非二元條件約束滿足問(wèn)題模型時(shí)，產(chǎn)品功能可分別建模為變量，實(shí)現(xiàn)該功能的關(guān)鍵組件類型建模為該變量的域值，為配合關(guān)鍵組件類型實(shí)現(xiàn)某一特定功能的非關(guān)鍵組件，采用激活性約束進(jìn)行建模，產(chǎn)品功能間的約束可建模為兼容性約束。

根據(jù)以上理論，以一個(gè)簡(jiǎn)化的某汽車產(chǎn)品配置問(wèn)題為例［8，10］，根據(jù)該制造商的實(shí)際制造能力和客戶的要求，建立該配置問(wèn)題的NCCSP模型。在該配置問(wèn)題中，有8個(gè)可配置對(duì)象，其中3個(gè)是必選可配置對(duì)象，5個(gè)是非必選可配置對(duì)象。這些可配置對(duì)象間存在：①4個(gè)兼容性約束，包括2個(gè)二元約束和2個(gè)三元約束；②11個(gè)激活性約束，包括8個(gè)包含性約束和3個(gè)排斥性約束。這些可配置對(duì)象和配置約束均被抽象為非二元條件約束滿足問(wèn)題中相應(yīng)的變量和變量間的約束，并建立如圖3所示的面向該產(chǎn)品配置問(wèn)題的NCCSP模型。4．2．2 實(shí)例模型求解

對(duì)4．2．1節(jié)的NCCSP模型，分別采用本文提出的三種算法進(jìn)行求解，實(shí)驗(yàn)環(huán)境為Windows XP，Intel（R）Core（TM）2Duo CPU T7100 ＠1．80 GHz 1．79GHz，0．99GB 的 內(nèi) 存，編 程 語(yǔ) 言 為MATLAB 7．1。求解到第一個(gè)可行解時(shí)的實(shí)驗(yàn)結(jié)果如表4所示。

由表4可知，在獲得第一個(gè)可行解時(shí)，算法NCCSP－BT和 NCCSP－NFC4具有相似的時(shí)間性能，算法NCCSP－NFC5具有最壞的時(shí)間性能。進(jìn)一步分析發(fā)現(xiàn)，相對(duì)于條件約束檢查次數(shù)，兼容性約束檢查次數(shù)對(duì)算法的性能影響相對(duì)較大。

表4 汽車產(chǎn)品配置問(wèn)題的NCCSP模型的求解結(jié)果

需要指出的是，該實(shí)例分析的目的并不在于比較各算法的相對(duì)求解性能，而在于通過(guò)該實(shí)例引出NCCSP的一個(gè)應(yīng)用場(chǎng)景。在現(xiàn)實(shí)問(wèn)題中，變量間經(jīng)常存在復(fù)雜的約束，這些約束很多是以非二元約束的形式存在。在涉及必選變量和可選變量的場(chǎng)合，由于在問(wèn)題最終解中可選變量允許以非賦值的形式存在，導(dǎo)致在求解期間并非所有變量都參與求解。因此，在建模這類問(wèn)題時(shí)，可利用激活性約束依條件動(dòng)態(tài)引入或剔除參與求解的可選變量，從而增加模型的表示力和求解效率。本例的配置問(wèn)題便是一種典型的NCCSP的應(yīng)用。

4．3 基于隨機(jī)問(wèn)題的仿真實(shí)驗(yàn)

4．3．1 仿真實(shí)驗(yàn)數(shù)據(jù)的產(chǎn)生

在4．2節(jié)，由于實(shí)例較簡(jiǎn)單，并不能充分揭示各算法性能的相對(duì)差異。為進(jìn)一步比較本文所提算法的求解性能，需要使用隨機(jī)發(fā)生器生成的NCCSP實(shí)例。因此，借鑒文獻(xiàn)［10］開(kāi)發(fā)的二元條件約束滿足問(wèn)題隨機(jī)生成器的方法，采用 MATLAB 7．1開(kāi)發(fā)了一個(gè)NCCSP隨機(jī)生成器。

該隨機(jī)生成器在生成測(cè)試實(shí)例時(shí)，采用如下參數(shù)作為輸入變量：①n為全體變量個(gè)數(shù)；②m為變量的最大域值規(guī)模，在生成隨機(jī)問(wèn)題時(shí)將所有變量的域值規(guī)模都固定為m；③rc為兼容性約束的最大維數(shù)，在生成隨機(jī)問(wèn)題時(shí)將兼容性約束的維數(shù)都固定為rc；④ra為激活性約束中的約束條件的最大維數(shù)，在生成隨機(jī)問(wèn)題時(shí)將激活性約束中約束條件維數(shù)都固定為ra；⑤pnoni為非初始變量生成的概率，隨機(jī)問(wèn)題中非初始變量規(guī)模為npnoni，初始變量規(guī)模為n（1－pnoni）；⑥sc為兼容性約束被滿足的概率，隨機(jī)問(wèn)題中每個(gè)兼容性約束所包含的合法元組規(guī)模為scmrc；⑦dc為兼容性約束密度，隨機(jī)問(wèn)題中所包含的兼容性約束的規(guī)模為dcCrnc；⑧sa為激活性約束被滿足概率，具有相同條件變量的激活性約束中，其約束條件的合法元組規(guī)模為samra；⑨da為激活性約束密度，具有不同條件變量的激活性約束規(guī)模為daCrna；具有相同條件變量的激活性約束，其差異主要取決于條件變量取值的不同，激活性約束的總規(guī)模為samradaCrna；⑩pincl為每條產(chǎn)生的激活性約束是包含性約束的概率，排斥性約束生成的概率則為（1－pincl）；○11ta為激活性約束所觸發(fā)的最大目標(biāo)變量數(shù)目。

4．3．2 仿真實(shí)驗(yàn)條件設(shè)定與實(shí)驗(yàn)結(jié)果

在面向非二元條件約束滿足問(wèn)題的回溯算法和前向檢查算法中，兼容性約束與激活性約束處理的先后順序?qū)λ惴ㄐ阅艽嬖谝欢ǖ挠绊?。為了評(píng)估本文所提算法性能的差異及不同類型約束處理順序?qū)λ惴ㄔ斐傻挠绊?，本文仿真?shí)驗(yàn)由兩部分構(gòu)成：①實(shí)驗(yàn)一，衡量在不同類型NCCSP實(shí)例下本文所提三種算法的性能差異；②實(shí)驗(yàn)二，衡量在調(diào)整不同類型約束處理順序后，原算法及其相應(yīng)變體的性能差異。4．3．2．1 實(shí)驗(yàn)一

在生成的隨機(jī)非二元條件約束滿足問(wèn)題中，本文設(shè)定公共參數(shù)為：rc＝3，ra＝2，da＝0．5，pincl＝0．5，ta＝1；其他參數(shù)取值可變。在相同的一組實(shí)驗(yàn)參數(shù)下，每次產(chǎn)生100個(gè)隨機(jī)測(cè)試實(shí)例，實(shí)驗(yàn)結(jié)果分別取各評(píng)價(jià)指標(biāo)的算術(shù)平均值。實(shí)驗(yàn)環(huán)境為Windows XP，Intel（R）Core（TM）2Duo CPU T7100＠1．80GHz 1．79GHz，0．99GB的內(nèi)存，編程語(yǔ)言為MATLAB 7．1。

（1）不同約束密度下各類約束被滿足概率變化時(shí)的算法性能

分別研究在不同兼容性約束密度下，兼容性約束與激活性約束被滿足概率變化時(shí)，本文三種算法的求解性能。設(shè)計(jì)兩組實(shí)驗(yàn)：①n＝15，m＝7，pnoni＝0．5，sa＝0．5，dc＝［0．3，0．5，0．7］，sc＝ ［0．1，0．2，0．3，0．4，0．5，0．6，0．7，0．8，0．9］；實(shí)驗(yàn)結(jié)果如圖4所示；②n＝15，m＝7，pnoni＝0．5，sc＝0．5，dc＝［0．3，0．5，0．7］，sa＝ ［0．1，0．2，0．3，0．4，0．5，0．6，0．7，0．8，0．9］。實(shí)驗(yàn)結(jié)果如圖5所示。

由圖4可知，相同兼容性約束密度dc下，三種算法在兼容性約束被滿足的概率sc由小變大時(shí)，運(yùn)算時(shí)間均經(jīng)歷了由快到慢、進(jìn)而由慢到快的過(guò)程；同時(shí)可見(jiàn)，當(dāng)sc在區(qū)間［0．4，0．8］內(nèi)變化時(shí)，運(yùn)算時(shí)間發(fā)生了顯著變化，問(wèn)題開(kāi)始變得難以求解；此時(shí)，算法NCCSP－BT具有最壞的求解性能，其次是NCCSP－NFC5，再次是 NCCSP－NFC4。另外，不同兼容性約束密度dc下，當(dāng)兼容性約束被滿足的概率sc在區(qū)間［0．4，0．7］變化時(shí)，所有 NCCSP問(wèn)題均開(kāi)始變得難以求解。上述現(xiàn)象表明：①在兼容性約束被滿足概率sc很小時(shí)，所產(chǎn)生的隨機(jī)測(cè)試實(shí)例以無(wú)解問(wèn)題為主，三種算法均能快速探測(cè)到一個(gè)無(wú)解狀態(tài)；②在兼容性約束被滿足概率sc很大時(shí)，所產(chǎn)生的隨機(jī)測(cè)試實(shí)例可行解非常多，此時(shí)，三種算法均能很容易地將一個(gè)部分實(shí)例化解擴(kuò)展為一個(gè)有效解；③兼容性約束被滿足概率sc在區(qū)間［0．4，0．8］內(nèi)變化時(shí)，所產(chǎn)生的隨機(jī)測(cè)試實(shí)例變得難以求解，原因在于部分實(shí)例化解向有效解擴(kuò)展的過(guò)程中，引起搜索失敗的因素反復(fù)出現(xiàn)，從而導(dǎo)致求解困難。算法NCCSP－NFC4和NCCSP－NFC5在搜索過(guò)程中分別嵌入不同程度的弧一致技術(shù)，能夠有效地剪去不必要的搜索分支，減少求解過(guò)程中的回溯次數(shù)，因而在難問(wèn)題上具有比算法NCCSP－BT更優(yōu)的時(shí)間性能。

從圖5可知，相同兼容性約束密度dc下，三種算法的運(yùn)算時(shí)間均隨著激活性約束被滿足概率sa的變大而增加；其中，算法NCCSP－BT具有最壞的求解性能，其次是NCCSP－NFC5，再次是 NCCSPNFC4。另外，隨著兼容性約束密度dc的增加，三種算法在求解相同問(wèn)題時(shí)，運(yùn)算時(shí)間增加所引起的時(shí)間性能曲線均趨向于平緩。上述現(xiàn)象表明：①在激活性約束被滿足的概率sa較小時(shí)，激活性約束的目標(biāo)變量被觸發(fā)的可能性較低；因而在問(wèn)題求解過(guò)程中變量規(guī)模的變化不顯著，此時(shí)問(wèn)題易于求解；隨著激活性約束被滿足概率sa的增大，激活性約束的目標(biāo)變量被觸發(fā)的可能性也隨之增加，從而導(dǎo)致問(wèn)題求解過(guò)程中變量規(guī)模的變化愈來(lái)愈顯著，問(wèn)題開(kāi)始變得難以求解。②兼容性約束密度dc的不斷增加，使得問(wèn)題中兼容性約束的規(guī)模不斷變大，從而增加了一個(gè)部分實(shí)例化解擴(kuò)展為有效解的難度。由于在求解過(guò)程中，算法 NCCSP－NFC4和 NCCSP－NFC5嵌入了不同程度的弧一致技術(shù)，預(yù)先剪去后續(xù)不必要的搜索分支，提高了求解性能。

（2）不同程度動(dòng)態(tài)性特征時(shí)算法性能

由圖4和圖5可知，算法 NCCSP－NFC4和NCCSP－NFC5在求解NCCSP問(wèn)題時(shí)，其時(shí)間性能均顯著地優(yōu)于算法 NCCSP－BT；而算法 NCCSPNFC4和NCCSP－NFC5兩者間的求解性能差異卻并不顯著。下面進(jìn)一步比較具有不同程度動(dòng)態(tài)性特征 的 NCCSP 問(wèn) 題 下，算 法 NCCSP－NFC4 和NCCSP－NFC5的相對(duì)求解性能。設(shè)定實(shí)驗(yàn)條件如下：n＝15，m＝7，sa＝0．5，dc＝0．5，sc＝0．5，pnoni＝［0．1，0．2，0．3，0．4，0．5，0．6，0．7，0．8，0．9］，實(shí)驗(yàn)結(jié)果如圖6所示。

非初始變量生成概率pnoni決定了NCCSP中全體變量被劃分為初始變量集合與非初始變量集合各自的相對(duì)規(guī)模。pnoni值越大，變量被挑選作為非初始變量的可能性越大，從而使得解空間的規(guī)模也隨之增大；在求解過(guò)程中，NCCSP問(wèn)題將展示更強(qiáng)的動(dòng)態(tài)性特征，即更多的非初始變量將頻繁動(dòng)態(tài)地被挑選參與到求解過(guò)程中。由圖6可知，當(dāng)pnoni值超過(guò)0．6的臨界點(diǎn)時(shí)，算法NCCSP－NFC4和NCCSPNFC5在時(shí)間性能上無(wú)顯著差異；當(dāng)pnoni＜0．6時(shí)，算法NCCSP－NFC4具有比NCCSP－NFC5更佳的時(shí)間性能。同時(shí)可知，當(dāng)pnoni值在區(qū)間［0．4，0．6］變化時(shí)，兩種算法的求解性能均發(fā)生了顯著變化，問(wèn)題開(kāi)始變得難以求解。上述現(xiàn)象表明：①pnoni＜0．6時(shí)，算法NCCSP－NFC5在求解過(guò)程中嵌入更深程度的前看策略所帶來(lái)的回溯次數(shù)減少的收益，并不能彌補(bǔ)求解過(guò)程中因?qū)嵤└畛潭惹翱床呗运枰ㄙM(fèi)的更多兼容性約束檢查次數(shù)而付出的代價(jià)，從而使得算法NCCSP－NFC4在pnoni值小于0．6時(shí)具有相對(duì)更佳的求解性能；②當(dāng)pnoni＞0．6時(shí)，相對(duì)算法NCCSP－NFC4而言，算法NCCSP－NFC5在求解時(shí)實(shí)施更深程度的前看策略所帶來(lái)的收益，與其實(shí)施該技術(shù)所需付出的代價(jià)大致相當(dāng)，因而在此情況下兩種算法的相對(duì)性能差異并不顯著；③從圖6還可知，兩種算法的時(shí)間性能曲線與兼容性約束檢查次數(shù)曲線的形狀非常相似，說(shuō)明算法的時(shí)間性能基本上決定于求解過(guò)程中其所執(zhí)行的兼容性約束檢查次數(shù)；同時(shí)亦說(shuō)明相對(duì)于條件約束檢查，執(zhí)行一次兼容性約束檢查需花費(fèi)更多的時(shí)間代價(jià)。

（3）問(wèn)題規(guī)模變化時(shí)算法性能

在前述實(shí)驗(yàn)中，本文固定變量規(guī)模為15和變量域值規(guī)模為7，該問(wèn)題實(shí)際上代表了一類規(guī)模不大的NCCSP。由于NCCSP解空間規(guī)模主要取決于全體變量及其域值的規(guī)模，本節(jié)分別研究在不同變量規(guī)模和變量域值規(guī)模下，算法NCCSP－NFC4和NCCSP－NFC5的相對(duì)性能。設(shè)計(jì)兩組實(shí)驗(yàn)：①n＝［10，20，30，40，50，60，70，80，90，100］，m＝7，pnoni＝0．5，sa＝0．5，dc＝0．5，sc＝0．5；實(shí)驗(yàn)結(jié)果如圖7所示；②n＝15，m＝ ［5，7，9，11，13，15，17，19，21，25，35］，pnoni＝0．5，sa＝0．5，dc＝0．5，sc＝0．5。實(shí)驗(yàn)結(jié)果如圖8所示。

由圖7可知，在變量規(guī)模小于臨界點(diǎn)50時(shí)，算法NCCSP－NFC4的時(shí)間性能更優(yōu)；而當(dāng)變量規(guī)模超過(guò)臨界點(diǎn)50時(shí)，算法NCCSP－NFC5的時(shí)間性能更優(yōu)。在回溯次數(shù)上，算法NCCSP－NFC5由于在求解過(guò)程中實(shí)施更深程度的前看策略，刪除了更多不必要的搜索分支，具有相對(duì)于算法NCCSP－NFC4更優(yōu)的回溯性能。從圖8可知，在變量域值規(guī)模小于臨界點(diǎn)21時(shí)，算法NCCSP－NFC4的時(shí)間性能更優(yōu)；而當(dāng)變量域值規(guī)模大于臨界點(diǎn)21時(shí)，算法NCCSP－NFC5的時(shí)間性能更優(yōu)。在回溯次數(shù)上，算法NCCSP－NFC5始終具有比算法 NCCSP－NFC4更優(yōu)的回溯性能。上述現(xiàn)象表明：①回溯性能的改善并不一定帶來(lái)算法時(shí)間性能的改善，只有當(dāng)實(shí)施更深程度前看策略所帶來(lái)的收益大于所付出的代價(jià)時(shí)，回溯性能的改善才帶來(lái)算法時(shí)間性能的改善；②算法NCCSP－NFC4和NCCSP－NFC5具有不同的適用區(qū)間，總體而言，算法NCCSP－NFC4適用于求解中小規(guī)模的NCCSP問(wèn)題；而算法NCCSP－NFC5則適用于求解大規(guī)模的NCCSP。4．3．2．2 實(shí)驗(yàn)二

在本文所提的原算法中，對(duì)約束的處理均遵循先激活性約束再兼容性約束的順序。若調(diào)整不同類型的約束處理順序，為保證調(diào)整后算法的正確性，需對(duì)原算法進(jìn)行一定的修改?；厮菟惴∟CCSP－BT中，若先處理兼容性約束、再處理激活性約束，則激活性約束所激活的目標(biāo)變量會(huì)改變當(dāng)前狀態(tài)問(wèn)題的拓?fù)浣Y(jié)構(gòu)；但由于回溯算法對(duì)兼容性約束的檢查采用“后看”策略，約束處理順序的改變并不會(huì)影響算法的正確性。本文將先處理兼容性約束，再處理激活性約束的回溯算法視為算法NCCSP－BT的變體，稱為NCCSP－BT（variant）。在面向非二元條件約束滿足問(wèn)題的前向檢查算法中，若進(jìn)行兼容性約束非二元弧一致操作使得問(wèn)題處于弧一致?tīng)顟B(tài)，則再進(jìn)行激活性約束處理會(huì)導(dǎo)致新激活的活動(dòng)變量集破壞之前問(wèn)題的弧一致?tīng)顟B(tài)，此時(shí)需要在對(duì)新產(chǎn)生的活動(dòng)變量集和已賦值變量集之間進(jìn)行非二元弧一致操作，以維護(hù)所有的未賦值變量與已賦值變量間的弧一致性，從而確保后續(xù)階段賦值操作的正確性。在前向檢查算法中先對(duì)兼容性約束實(shí)施NFC4操作，再在激活性約束處理中對(duì)新激活的活動(dòng)變量集與已賦值變量集嵌入NFC4操作，這種算法視為NCCSP－NFC4的變體，稱為 NCCSP－NFC4（variant）。另外，在前向檢查算法中，先對(duì)兼容性約束實(shí)施NFC5操作，再在激活性約束處理中對(duì)新激活的活動(dòng)變量集與已賦值變量集嵌入NFC5操作，這種算法視為 NCCSP－NFC5的變體，稱為 NCCSPNFC5（variant）。為衡量各原算法與其相應(yīng)變體的算法性能差異，限于篇幅，本文僅給出下述設(shè)計(jì)參數(shù)取值時(shí)的仿真結(jié)果（如圖9）：n＝15，m＝7，pnoni＝0．5，sa＝0．5，dc＝ 0．5，sc＝ ［0．1，0．2，0．3，0．4，0．5，0．6，0．7，0．8，0．9］。

從圖9可知，不同類型約束處理的先后順序?qū)λ惴ㄐ阅艿拇_具有一定影響。相對(duì)原算法而言，先處理兼容性約束、再處理激活性約束，對(duì)原算法的求解性能有一定的改善作用。其中，回溯算法NCCSP－BT（variant）相對(duì)原算法 NCCSP－BT而言，在約束檢查上，以兼容性約束檢查次數(shù)增加的輕微代價(jià)，換取了條件約束檢查次數(shù)的顯著降低，從而節(jié)省了搜索成本，使得回溯算法NCCSP－BT（variant）的時(shí)間性能比原算法NCCSP－BT得到了明顯的改善。在前向檢查算法上，原算法變體（NCCSPNFC4（variant）和 NCCSP－NFC5（variant））相對(duì)原算法（NCCSP－NFC4、NCCSP－NFC5）而言，其條件約束的檢查次數(shù)顯著減少，也使得其時(shí)間性能均獲得了輕微改善。

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

本文對(duì)經(jīng)典二元條件約束滿足問(wèn)題進(jìn)行了拓展，給出了非二元條件約束滿足問(wèn)題模型。借鑒求解非二元約束滿足問(wèn)題的傳統(tǒng)回溯算法及幾類前向檢查算法思想，結(jié)合非二元條件的約束滿足問(wèn)題特征，提出了適于求解非二元條件約束滿足問(wèn)題的回溯算法及前向檢查算法。其中，前向檢查算法根據(jù)其在求解過(guò)程中實(shí)施局部一致性方法程度的不同，又細(xì)分為NCCSP－NFC4和NCCSP－NFC5兩種算法。通過(guò)一個(gè)算例演示了三種算法的求解思想，給出了三種算法最壞情況下的時(shí)間復(fù)雜性，指出在嵌入某種優(yōu)化算法（如GAC2001）時(shí)，算法NCCSP－NFC4和NCCSP－NFC5最壞情況下具有相同的時(shí)間復(fù)雜性。通過(guò)一個(gè)簡(jiǎn)化的汽車產(chǎn)品配置問(wèn)題實(shí)例闡述了NCCSP的應(yīng)用場(chǎng)景，開(kāi)發(fā)了隨機(jī)生成器并生成了NCCSP測(cè)試實(shí)例，對(duì)三種算法的求解性能進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，在求解難問(wèn)題時(shí)，回溯算法 （NCCSP－BT）性能顯著劣于 NCCSPNFC4算法和NCCSP－NFC5算法，而算法NCCSPNFC4和NCCSP－NFC5間的求解性能差異并不顯著。進(jìn)一步分析發(fā)現(xiàn)，在中小規(guī)模問(wèn)題中，問(wèn)題本身所呈現(xiàn)的動(dòng)態(tài)性特征越低，越適用于采用算法NCCSP－NFC4求解，而在高動(dòng)態(tài)性特征問(wèn)題中，算法NCCSP－NFC4和NCCSP－NFC5之間的求解性能差異并不顯著。在大規(guī)模問(wèn)題中，算法NCCSPNFC5在求解性能上優(yōu)于算法NCCSP－NFC4。總體而言，算法NCCSP－NFC4和NCCSP－NFC5在求解非二元條件約束滿足問(wèn)題時(shí)，不存在一個(gè)普適區(qū)間，某種算法的性能始終優(yōu)于另一種算法；但在不同的某特定區(qū)間，算法 NCCSP－NFC4和 NCCSPNFC5在求解性能上表現(xiàn)出了較顯著的差異。需要指出的是，在本文所提的原算法中，若改變不同類型約束的處理順序，即先處理兼容性約束、再處理激活性約束，則會(huì)對(duì)原算法的性能帶來(lái)一定的改善作用。另外，本文所提的三種算法均為直接求解算法，未來(lái)將提出適用于NCCSP的間接求解算法和啟發(fā)式算法，并比較它們與直接求解算法之間的性能差異。

［1］ WANG Ziwen，LI Zhanshan，AI Yang，et al．Algorithm for solving constraint satisfaction problems based on dynamic value ordering heuristic［J］．Computer Integrated Manufacturing Systems，2011，17（4）：832－837（in Chinese）．［王孜文，李占山，艾 陽(yáng)，等．基于動(dòng)態(tài)值啟發(fā)式的約束滿足求解算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2011，17（4）：832－837．］

［2］ LI Zhanshan，LI Hongbo，ZHANG Yonggang，et al．An approach of solving constraint satisfaction problem based on cycle－cut［J］．Chinese Journal of Computers，2011，34（8）：1528－1535（in Chinese）．［李占山，李宏博，張永剛，等．一種基于環(huán)切割的約束滿足問(wèn)題求解算法［J］．計(jì)算機(jī)學(xué)報(bào)，2011，34（8）：1528－1535．］

［3］ MARIEM T，F(xiàn)EHMI H，PIERRE L．Project scheduling under resource constraints：application of the cumulative global constraint in a decision support framework［J］．Computers ＆Industrial Engineering，2011，61（2）：357－363．

［4］ CHEN Hao，JING Ning，LI Jun，et al．Method for changeable resources in electromagnetic detection satellites dynamic scheduling［J］．Journal of System Simulation，2009，21（24）：7833－7837（in Chinese）．［陳 浩，景 寧，李 軍，等．一種適應(yīng)資源變化的電磁探測(cè)衛(wèi)星動(dòng)態(tài)調(diào)度方法［J］．系統(tǒng)仿真學(xué)報(bào)，2009，21（24）：7833－7837．］

［5］ MOUHOUB M，SUKPAN A．Conditional and composite temporal CSPs［J］．Applied Intelligence，2012，36（1）：90－107．

［6］ ZHANG Lei，LIU Guangfu，HU Di，et al．Green product configuration design based on constraint satisfaction problems［J］．Journal of Mechanical Engineering，2010，46（19）：117－124（in Chinese）．［張 雷，劉光復(fù)，胡 迪，等．基于約束滿足問(wèn)題的綠色產(chǎn)品配置設(shè)計(jì)［J］．機(jī)械工程學(xué)報(bào)，2010，46（19）：117－124．］

［7］ ALDANONDO M，VAREILLES M，DJEFEL M．Towards an association of product configuration with production planning［J］．International Journal of Mass Customisation，2010，3（4）：316－332．

［8］ MITTAL S，F(xiàn)ALKENHAINER B．Dynamic constraint satisfaction problems［C］//Proceedings of the 8th National Conference on Artificial Intelligence．Palo Alto，Cal．，USA：AAAI，1990：25－32

［9］ SCHIEX T，VERFAILLIE G．Nogood recording for static and dynamic constraint satisfaction problems［J］．International Journal of Artificial Intelligence Tools，1994，3（2）：187－207．［

10］ SABIN M．Towards more efficient solution of conditional constraint satisfaction problems［D］．Durham，Nh．，USA：U－niversity of New Hampshire，2003．

［11］ SABIN M，F(xiàn)REUDER E C，WALLACE R J．Greater efficiency for conditional constraint satisfaction［J］．Lecture Notes in Computer Science，2833，2003：649－663．

［12］ SABIN D，F(xiàn)REUDER E C．Configuration as composite constraint satisfaction［C］//Proceedings of the Artificial Intelligence and Manufaturing．Palo Ato，Cal．，USA：AAAI Press，1996：153－161．

［13］ ESTHER Gelle．Solving mixed and conditional constraint sat

isfaction problems［J］．Constraints，2003，8（2）：107－141．［14］ DONG Yang，DONG Ming，CHANG Xiaokun．A dynamic constraint satisfaction approach for configuring structural products under mass customization［J］．Engineering Applications of Artificial Intelligence，2012，25（8）：1723－1737．

［15］ WANG Lin，WEE－KEONG N G．Hybrid solving algorithms for an extended dynamic constraint satisfaction problem based configuration system［J］．Concurrent Engineering：Research and Applications，2012，20（3）223－236．

［16］ RAPHAEL F，BARRY O．Reasoning about conditional constraint specification problems and feature models［J］．Artificial Intelligence for Engineering Design，Analysis and Manufacturing，2011，25（2）：163－174．

［17］ BESSIERE C，MESEGUER P，F(xiàn)REUDER E C，et al．On forward checking for non－binary constraint satisfaction［J］．Aritficial Intelligence，2002，141（1/2）：205－224．

［18］ BESSIERE C，REGIN J C，YAP R H C，et al．An optimal coarse－grained arc consistency algorithm［J］．Artificial Intelligence，2005，165（2）：165－185．

［19］ BESSIERE C，STERGIOU K，WALSH T．Domain filtering consistencies for non－binary constraints［J］．Artificial Intelligence，2008，172（6/7）：800－822．

［20］ WOODWARD R J，KARAKASHIAN S，CHOUEIRY B Y，et al．Solving difficult CSPs with relational neighborhood consistency［C］//Proceedings of the Conference on Artificial Inteelligence．Palo Ato，Cal．，USA：AAAI Press，2011：112－119．

［21］ BESSIERE C，REGIN J C．Refining the basic constraint propagation algorithm［EB/OL］．［2012－05－06］．http：//citeseerx．ist．psu．edu/viewdoc/download？doi＝10．1．1．123．8012＆rep＝rep＆type＝pdf．

［22］ MITTAL S，F(xiàn)RAYMAN F．Towards a generic model of

configuration tasks［C］//Proceedings of the 10th International Joint Conference on Artificial Intelligence．San Fancisco，Cal．，USA：Morgan Kaufmann，1989：1395－1401．