袁際軍，黃敏鎂

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

0 引言

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

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

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

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

1 非二元條件約束滿足問題

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

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

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

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

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

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

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

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

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

定義2 約束投影。給定一個約束Ci及約束作用范圍S（Ci）的子集Sj，將Sj在約束Ci中對應(yīng)變量的域值組合加以截留，形成一個作用在變量集合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的求解過程中，動態(tài)地構(gòu)建與NCCSP相關(guān)的約束網(wǎng)絡(luò)。在該約束網(wǎng)絡(luò)中，所有變量均處于活動變量狀態(tài)，在求解過程中這些變量均需被指派域值，NCCSP的解由約束網(wǎng)絡(luò)中的所有變量及其相應(yīng)賦值組成。

2 非二元條件約束滿足問題求解算法

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

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

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

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

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

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

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

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

for each（d∈D｛vrb｝）｛

將域值d賦予當前變量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 對激活性約束檢查的處理

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

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

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

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

//Vactive是活動變量列表

令Vactive＝Vassign∪Vunassign

//Vassign是Vactive中已賦值變量列表（包括當前賦值變量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保存迄今已實例化變量的賦值信息

i

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

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

Vactive←Vactive∪｛a的目標變量｝

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

else｛//a是排斥性約束

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

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

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

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

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

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

算法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是當前賦值變量

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

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

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

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

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

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

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

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

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

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

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

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

將域值d賦予當前變量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中元素個數(shù)之和）return true//獲得一個可行解

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

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

將域值d賦予當前變量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 對激活性約束檢查的處理

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

2．2．3 對非二元條件前向檢查中約束傳播過程的處理

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

Cactivec，f∪（Cactivep，f－Cactivec，f）∪Cactivep，p∪Cactivef，f。其中：Cactivec，f 表示包含一個當前賦值變量xj和至少一個未賦值變量的所有被激活的兼容性約束；Cactivep，f表示包含至少一個已賦值變量（當前變量xj也視為已賦值變量）和至少一個未賦值變量的所有已激活的兼容性約束；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ù)文獻［17］中的弧一致方法nFC1、nFC2和nFC3，若在約束傳播過程中的第j個瞬時狀態(tài)對約束集合Cactivec，f嵌入弧一致操作，則與約束集合Cactivec，f相關(guān)的Vi→j中的變量（如xj1）的域值與已賦值變量具有一致性，但并不能保證與約束集合Cactivec，f無關(guān)的Vi→j中變量（如xj2）的域值也與已賦值變量具有一致性。因此，弧一致方法nFC1，nFC2和nFC3不能直接應(yīng)用于第j個瞬時狀態(tài)。若在約束傳播過程中的第j個瞬時狀態(tài)以約束集合Cactivep，f為弧一致處理對象，則Vi→j中的變量在弧一致處理后，與已賦值變量不一致的域值將被剔除，從而使變量集合Vj處于一致性狀態(tài)。因此，文獻［17］中的弧一致方法nFC4和nFC5可直接應(yīng)用于第j個瞬時狀態(tài)。

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

算法6 NFC4算法。

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

令Vactive＝Vp∪Vf

//Vp是Vactive中已賦值變量（包括當前賦值變量）集合，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｝。每個變量的值域D都是｛e，f，g｝，兼容性約束｛C1，C2，C3｝與激活性約束｛A1，A2，A3｝分別如表1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 應(yīng)用實例分析與基于隨機問題的仿真實驗

4．1 評價指標

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

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

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

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

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

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

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

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

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

4．3 基于隨機問題的仿真實驗

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

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

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

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

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

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

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

分別研究在不同兼容性約束密度下，兼容性約束與激活性約束被滿足概率變化時，本文三種算法的求解性能。設(shè)計兩組實驗：①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］；實驗結(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］。實驗結(jié)果如圖5所示。

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

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

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

由圖4和圖5可知，算法 NCCSP－NFC4和NCCSP－NFC5在求解NCCSP問題時，其時間性能均顯著地優(yōu)于算法 NCCSP－BT；而算法 NCCSPNFC4和NCCSP－NFC5兩者間的求解性能差異卻并不顯著。下面進一步比較具有不同程度動態(tài)性特征 的 NCCSP 問 題 下，算 法 NCCSP－NFC4 和NCCSP－NFC5的相對求解性能。設(shè)定實驗條件如下：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］，實驗結(jié)果如圖6所示。

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

（3）問題規(guī)模變化時算法性能

在前述實驗中，本文固定變量規(guī)模為15和變量域值規(guī)模為7，該問題實際上代表了一類規(guī)模不大的NCCSP。由于NCCSP解空間規(guī)模主要取決于全體變量及其域值的規(guī)模，本節(jié)分別研究在不同變量規(guī)模和變量域值規(guī)模下，算法NCCSP－NFC4和NCCSP－NFC5的相對性能。設(shè)計兩組實驗：①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；實驗結(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。實驗結(jié)果如圖8所示。

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

在本文所提的原算法中，對約束的處理均遵循先激活性約束再兼容性約束的順序。若調(diào)整不同類型的約束處理順序，為保證調(diào)整后算法的正確性，需對原算法進行一定的修改。回溯算法NCCSP－BT中，若先處理兼容性約束、再處理激活性約束，則激活性約束所激活的目標變量會改變當前狀態(tài)問題的拓撲結(jié)構(gòu)；但由于回溯算法對兼容性約束的檢查采用“后看”策略，約束處理順序的改變并不會影響算法的正確性。本文將先處理兼容性約束，再處理激活性約束的回溯算法視為算法NCCSP－BT的變體，稱為NCCSP－BT（variant）。在面向非二元條件約束滿足問題的前向檢查算法中，若進行兼容性約束非二元弧一致操作使得問題處于弧一致狀態(tài)，則再進行激活性約束處理會導(dǎo)致新激活的活動變量集破壞之前問題的弧一致狀態(tài)，此時需要在對新產(chǎn)生的活動變量集和已賦值變量集之間進行非二元弧一致操作，以維護所有的未賦值變量與已賦值變量間的弧一致性，從而確保后續(xù)階段賦值操作的正確性。在前向檢查算法中先對兼容性約束實施NFC4操作，再在激活性約束處理中對新激活的活動變量集與已賦值變量集嵌入NFC4操作，這種算法視為NCCSP－NFC4的變體，稱為 NCCSP－NFC4（variant）。另外，在前向檢查算法中，先對兼容性約束實施NFC5操作，再在激活性約束處理中對新激活的活動變量集與已賦值變量集嵌入NFC5操作，這種算法視為 NCCSP－NFC5的變體，稱為 NCCSPNFC5（variant）。為衡量各原算法與其相應(yīng)變體的算法性能差異，限于篇幅，本文僅給出下述設(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ū)λ惴ㄐ阅艿拇_具有一定影響。相對原算法而言，先處理兼容性約束、再處理激活性約束，對原算法的求解性能有一定的改善作用。其中，回溯算法NCCSP－BT（variant）相對原算法 NCCSP－BT而言，在約束檢查上，以兼容性約束檢查次數(shù)增加的輕微代價，換取了條件約束檢查次數(shù)的顯著降低，從而節(jié)省了搜索成本，使得回溯算法NCCSP－BT（variant）的時間性能比原算法NCCSP－BT得到了明顯的改善。在前向檢查算法上，原算法變體（NCCSPNFC4（variant）和 NCCSP－NFC5（variant））相對原算法（NCCSP－NFC4、NCCSP－NFC5）而言，其條件約束的檢查次數(shù)顯著減少，也使得其時間性能均獲得了輕微改善。

5 結(jié)束語

本文對經(jīng)典二元條件約束滿足問題進行了拓展，給出了非二元條件約束滿足問題模型。借鑒求解非二元約束滿足問題的傳統(tǒng)回溯算法及幾類前向檢查算法思想，結(jié)合非二元條件的約束滿足問題特征，提出了適于求解非二元條件約束滿足問題的回溯算法及前向檢查算法。其中，前向檢查算法根據(jù)其在求解過程中實施局部一致性方法程度的不同，又細分為NCCSP－NFC4和NCCSP－NFC5兩種算法。通過一個算例演示了三種算法的求解思想，給出了三種算法最壞情況下的時間復(fù)雜性，指出在嵌入某種優(yōu)化算法（如GAC2001）時，算法NCCSP－NFC4和NCCSP－NFC5最壞情況下具有相同的時間復(fù)雜性。通過一個簡化的汽車產(chǎn)品配置問題實例闡述了NCCSP的應(yīng)用場景，開發(fā)了隨機生成器并生成了NCCSP測試實例，對三種算法的求解性能進行了仿真實驗。實驗結(jié)果發(fā)現(xiàn)，在求解難問題時，回溯算法 （NCCSP－BT）性能顯著劣于 NCCSPNFC4算法和NCCSP－NFC5算法，而算法NCCSPNFC4和NCCSP－NFC5間的求解性能差異并不顯著。進一步分析發(fā)現(xiàn)，在中小規(guī)模問題中，問題本身所呈現(xiàn)的動態(tài)性特征越低，越適用于采用算法NCCSP－NFC4求解，而在高動態(tài)性特征問題中，算法NCCSP－NFC4和NCCSP－NFC5之間的求解性能差異并不顯著。在大規(guī)模問題中，算法NCCSPNFC5在求解性能上優(yōu)于算法NCCSP－NFC4?？傮w而言，算法NCCSP－NFC4和NCCSP－NFC5在求解非二元條件約束滿足問題時，不存在一個普適區(qū)間，某種算法的性能始終優(yōu)于另一種算法；但在不同的某特定區(qū)間，算法 NCCSP－NFC4和 NCCSPNFC5在求解性能上表現(xiàn)出了較顯著的差異。需要指出的是，在本文所提的原算法中，若改變不同類型約束的處理順序，即先處理兼容性約束、再處理激活性約束，則會對原算法的性能帶來一定的改善作用。另外，本文所提的三種算法均為直接求解算法，未來將提出適用于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）．［王孜文，李占山，艾 陽，等．基于動態(tài)值啟發(fā)式的約束滿足求解算法［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)切割的約束滿足問題求解算法［J］．計算機學報，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)資源變化的電磁探測衛(wèi)星動態(tài)調(diào)度方法［J］．系統(tǒng)仿真學報，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ù)，胡 迪，等．基于約束滿足問題的綠色產(chǎn)品配置設(shè)計［J］．機械工程學報，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．