一種量詞約束滿足問題的混合易解子類?

高 健, 陳 榮, 李 輝

(大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院,遼寧 大連 116026)

約束是一個(gè)現(xiàn)實(shí)世界普遍存在的概念,它在工業(yè)領(lǐng)域和日常生活中都有體現(xiàn),如生產(chǎn)過程中加工產(chǎn)品的先后順序、字處理軟件排版對(duì)齊的方式、棋類游戲中的限制規(guī)則等,都是常見的約束關(guān)系.約束滿足問題(constraint satisfaction problem)[1]是人工智能領(lǐng)域中核心的研究方向之一,它用來刻畫客觀存在的約束關(guān)系,并被廣泛地應(yīng)用于建模和求解各類實(shí)際問題[2?4],如作業(yè)調(diào)度、智能規(guī)劃、產(chǎn)品配置等.量詞約束滿足問題(quantified constraint satisfaction problem)[5]是經(jīng)典約束滿足問題的重要擴(kuò)展,在該問題中引入了一個(gè)變量順序的前綴,每個(gè)變量還被一個(gè)量詞所限定,量詞的種類有全稱量詞和存在量詞.求解量詞約束滿足問題是十分復(fù)雜的,對(duì)于由全稱量詞限定的變量,求解過程需要為其每個(gè)可能的取值找到一組其后續(xù)變量的賦值,并滿足它們之間的約束關(guān)系.從計(jì)算復(fù)雜性的角度來講,量詞約束滿足問題是PSPACE-完全的.而作為該問題的子問題,量詞布爾范式(quantified Boolean formula)[6]是PSPACE-完全類中的原型問題,即最早被證明是PSPACE-完全的,因此,量詞約束滿足問題的求解難度通常難于傳統(tǒng)的約束滿足問題.近些年,量詞約束滿足問題在博弈論、機(jī)械產(chǎn)品設(shè)計(jì)、動(dòng)態(tài)調(diào)度等領(lǐng)域被廣泛應(yīng)用[7?10].例如,在博弈游戲中,人們往往需要找到一個(gè)策略,使得無論對(duì)方如何選取決策都能保證是可以獲勝的;在工業(yè)產(chǎn)品配置中,為了提高產(chǎn)品的競(jìng)爭(zhēng)力,生產(chǎn)商需要尋求一種滿足客戶各種可能需求的配置方案.量詞約束優(yōu)化問題也得到關(guān)注,Lallouet等人[11,12]提出了Minimax加權(quán)約束滿足問題,該問題模型用于存在競(jìng)爭(zhēng)對(duì)手的交互式?jīng)Q策問題中,目標(biāo)是在競(jìng)爭(zhēng)對(duì)手采取對(duì)自己最不利的決策時(shí),最優(yōu)化給定的目標(biāo)函數(shù).

由于量詞約束滿足問題可以用于描述諸多實(shí)際問題,因此對(duì)該問題的性質(zhì)分析受到了學(xué)者的重視,而其中,對(duì)約束特性的分析是設(shè)計(jì)約束求解算法的基礎(chǔ)[13,14].雖然目前求解算法主要采用基于回溯策略的系統(tǒng)搜索方法,如Gent等人提出的QCSP-Solve[2,15]求解算法,但是算法中通常需要啟發(fā)式和局部結(jié)構(gòu)化簡(jiǎn)技術(shù),如基于相容性技術(shù)的變量值域約減和預(yù)處理方法.另外,利用問題的結(jié)構(gòu)特征設(shè)計(jì)啟發(fā)式規(guī)則也是一種重要的方法.例如,利用子問題結(jié)構(gòu)的相似性搜索結(jié)果的復(fù)用技術(shù)在求解器中也經(jīng)常被使用.Bacchus等人[16]提出了基于解重用的回跳技術(shù),該技術(shù)在搜索算法找到滿足約束的一個(gè)分支后,判斷當(dāng)前存在量詞變量的賦值是否同時(shí)也是其他分支(即其他的全稱量詞變量賦值組合)的解,與當(dāng)前賦值相容的其他分支則被標(biāo)記,在后續(xù)的搜索中不再展開這些被標(biāo)記的分支,從而減少了重復(fù)的計(jì)算;而求解算法Block-Solve[17]先將問題分解,求解若干子問題后,將計(jì)算結(jié)果整合成整體問題的解.另一方面,隱蔽集(backdoor set)[18]是分析問題結(jié)構(gòu)特征的一項(xiàng)重要理論工具.它是一個(gè)變量的集合,當(dāng)該集合中所有變量被賦予某一組取值后,剩余的子問題可以很容易地(通常在多項(xiàng)式時(shí)間內(nèi))被求解.隱蔽集理論可以用來識(shí)別問題中隱含的易解結(jié)構(gòu),通過它,可以找出哪些問題是多項(xiàng)式時(shí)間內(nèi)可解的,或者識(shí)別出多項(xiàng)式時(shí)間內(nèi)可解的部分,并從問題中將容易求解的部分分離出來.該項(xiàng)理論在分析約束滿足問題和量詞約束滿足問題中都起到了重要的作用[19?21].然而在尋找一個(gè)隱蔽集的同時(shí),需要確定剩余的變量組成的子問題是否是多項(xiàng)式時(shí)間可解的,所以隱蔽集的研究又是以多項(xiàng)式時(shí)間易解子類(以下簡(jiǎn)稱易解子類)為基礎(chǔ)的[22].

約束滿足問題的易解子類[23]是指該問題集合中的特例子集,這個(gè)子集中的問題實(shí)例可以在多項(xiàng)式時(shí)間內(nèi)求解.尋找易解子類是約束滿足問題的一項(xiàng)重要的基礎(chǔ)研究.而量詞約束滿足問題是PSPACE-完全的,所以找出該問題的可解子類,可以更大幅度地化簡(jiǎn)問題結(jié)構(gòu)并提高求解效率.因此,易解子類的研究也在量詞約束滿足問題中展開,并為隱蔽集的分析提供了理論基礎(chǔ).尋找更一般化的易解子類是獲得更小隱蔽集的關(guān)鍵所在,本文研究量詞約束滿足問題的易解子類,首先提出了針對(duì)全稱量詞變量的相容性概念并分析了其相關(guān)算法的時(shí)間復(fù)雜度.基于此概念,提出了一種新的混合易解子類,該易解子類一般化了基于Broken-Tringle Property(BTP)的易解子類[24].本文還詳細(xì)分析了所提出的混合易解子類的相關(guān)性質(zhì),其中包括子類識(shí)別問題所需的時(shí)間復(fù)雜度,并證明部分變量賦值后的子問題保持了量詞相容性和易解屬性.本文還在約束滿足問題的隱蔽集定義基礎(chǔ)上定義了量詞約束滿足問題的隱蔽集,通過改造經(jīng)典的回溯求解算法,實(shí)驗(yàn)分析了所提出的易解子類對(duì)隱蔽集大小的影響.通過與原有基于BTP的易解子類的實(shí)驗(yàn)結(jié)果比較,可以看出該易解子類可以獲得更小的隱蔽集,從而有效地將更多的變量分離到易解部分.

1 量詞約束滿足問題的定義

約束滿足問題包括有限變量集合和有限約束集合,每個(gè)變量對(duì)應(yīng)一個(gè)有限論域,每條約束限制了一些變量允許賦值的組合.約束滿足問題的解是為每個(gè)變量賦一個(gè)對(duì)應(yīng)論域上的值,使之滿足所有約束.求解約束滿足問題的目標(biāo)是找到一個(gè)解或是全部解.事實(shí)上,量詞約束滿足問題是通過經(jīng)典約束滿足問題對(duì)每一個(gè)變量都限定一個(gè)存在(?)或者全稱(?)量詞擴(kuò)展而來的.同時(shí),量詞約束滿足問題也是量詞布爾范式的擴(kuò)展,量詞布爾范式中,每個(gè)變量都在布爾域上取值,即取“真”或者“假”,而量詞約束滿足問題的變量值域可以是任意的有限集合.因?yàn)榱吭~布爾范式是PSPACE-完全類中的原型問題,所以量詞約束滿足問題也是PSPACE-完全的.

量詞約束滿足問題可以定義成一個(gè)四元組的形式(X,D,C,Q)[2],其中,

·X是一個(gè)有序的變量集合{x1,x2,…,xn};

·D={D1,D2,…,Dn}代表了對(duì)應(yīng)變量的取值范圍,函數(shù)D(xi)表示變量xi的值域(1≤i≤n);

·C={c1,c2,…,ce}是一個(gè)約束集合,每個(gè)約束限制了若干變量允許取值的關(guān)系元組;

·Q={λ1x1,λ2x2,…,λnxn}是一個(gè)有序的量詞集合,λi∈{?,?}(1≤i≤n).

函數(shù)Var(ci)(1≤i≤e)定義為參與約束ci的變量集合.

量詞約束滿足問題P=(X,Q,D,C)表示邏輯公式λ1x1λ2x2…λnxn(C),所以變量在P中是有序排列的,變量xi在xj之前是指xi在前綴中出現(xiàn)在xj之前,記作xi?xj或i

給定一個(gè)量詞約束滿足問題,如果對(duì)于所有的約束ci(1≤i≤e)都有|Var(ci)|=2,則該問題是二元的;如果存在約束ci使得|Var(ci)|>2,則說該問題是非二元的.本文主要探討二元量詞約束滿足問題,因此,cij被用來表示變量xi與xj之間的約束.這里包含了平凡約束,即在此約束里,所有的關(guān)系元組都是允許的.函數(shù)R(xi,xj)表示約束cij中允許取值的二元組集合.X?表示全部全稱量詞變量集合,X?表示全部存在量詞變量集合.z為變量,X?(z)表示在z之前的全稱量詞變量集合.

值a被賦給變量y時(shí),稱a為y的賦值,記作y=a;一組賦值α=a1a2...ak被賦給變量集合Y?X時(shí),稱α為Y的一組賦值,記作Y=α.若α和β分別是一組賦值且α和β所包含的變量交集為空,則αβ表示兩組賦值的并集.在本文中,a,b和c通常用于表示單個(gè)變量的賦值,而α和β表示對(duì)一組變量的賦值.若y=a是一個(gè)賦值且z是變量,則z中與a相容的所有值組成了a關(guān)于z的支持集,記作Iz(a);若α是Y的一組賦值,則變量z中所有與α相容的值的集合記作Iz(α).支持集集合Πy(?)={Iy(α),其中,α為任意一組X?(y)的賦值}.若β為一組對(duì)存在量詞變量的賦值,Πy(?,β)={Iy(αβ)|其中,α為任意一組X?(z)的賦值}.

若α為一組賦值,則P(α)表示通過α賦值對(duì)P化簡(jiǎn)后的問題,即從P中刪除被賦值的變量和這些變量參與的約束,同時(shí)刪除未賦值變量中與α不相容的取值并在未賦值變量的約束中刪除不相容的取值參與的元組關(guān)系后,得到的P的化簡(jiǎn)問題.

例1:二元量詞約束滿足問題P的約束關(guān)系圖如圖1所示,P包含了4個(gè)變量,其前綴順序?yàn)?x?y?z?t,x和y的值域?yàn)閧1,2,3},而z和t的值域?yàn)閧1,2,3,4},圖中變量用節(jié)點(diǎn)表示,兩個(gè)節(jié)點(diǎn)間的邊表示兩個(gè)變量間存在約束關(guān)系.

例1的一個(gè)解(相容策略樹)可用樹狀形式表示,如圖2所示.由于x是全稱量詞變量,其上一層節(jié)點(diǎn)具有多個(gè)子節(jié)點(diǎn),而變量y,z和t為存在量詞變量,所以上一層的節(jié)點(diǎn)只具有一個(gè)子節(jié)點(diǎn).

Fig.1 Constraint graph of the QCSP in Example 1圖1 例1中量詞約束滿足的問題的約束圖結(jié)構(gòu)

Fig.2 A solution tree of Example 1圖2 例1的一個(gè)解樹

2 全稱量詞相容性

首先介紹基本的量詞相容性概念,而后提出一個(gè)新的相容性概念——全稱量詞相容性.并討論了全稱量詞相容性與量詞相容性的關(guān)系以及計(jì)算復(fù)雜度.

2.1 量詞相容性

量詞相容性是從約束滿足問題的相容性擴(kuò)展而來的,它的提出主要是為了化簡(jiǎn)問題的值域從而加速回溯算法的求解[25],這些量詞相容性也被用來識(shí)別混合易解子類.給定一個(gè)量詞約束滿足問題,其解樹的構(gòu)造順序與其量詞前綴的變量順序相關(guān),因此,這里主要關(guān)注有向的量詞相容性.

定義1(有向的量詞弧相容).給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),P是有向量詞弧相容的,如果對(duì)于每個(gè)有序的變量對(duì)(xi,xj)使得xi?xj,滿足以下條件之一.

· ?xi?xj:對(duì)于每個(gè)值a∈D(xi),存在一個(gè)值b∈D(xj),使得(a,b)∈R(xi,xj);

· ?xi?xj:對(duì)于每個(gè)值a∈D(xi),任意的值b∈D(xj)滿足(a,b)∈R(xi,xj);

· ?xi?xj:對(duì)于每個(gè)值a∈D(xi),存在一個(gè)值b∈D(xj),使得(a,b)∈R(xi,xj);

· ?xi?xj:對(duì)于每個(gè)值a∈D(xi),任意的值b∈D(xj)滿足(a,b)∈R(xi,xj).

給定一個(gè)有序的變量對(duì)(xi,xj)使得xi?xj,如果(xi,xj)滿足上述4個(gè)條件之一,則(xi,xj)是有向量詞弧相容的.下面定義有向量詞k相容:

定義2(有向量詞k相容).給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C)和一個(gè)自然數(shù)k,使得(k≤n).如果對(duì)于每個(gè)有序的變量集合(y1,…,yk?1,xm),使得yi?yi+1且yi?xm(1≤i≤k?1)滿足以下條件之一,則P是有向量詞k相容的.

·λ1y1,λ2y2,…,λyk?1?xm對(duì)于任意y1y2…yk?1的相容賦值(a1,a2,...,ak?1),存在一個(gè)值b∈D(xm),使得(ai,b)∈R(yi,xm)(1≤i≤k?1);

·λ1y1,λ2y2,…,λyk?1?xm對(duì)于任意y1y2…yk?1的相容賦值(a1,a2,...,ak?1),任意一個(gè)值b∈D(xm),使得(ai,b)∈R(yi,xm)(1≤i≤k?1).

當(dāng)k為1時(shí),相容性為量詞節(jié)點(diǎn)相容;當(dāng)k為2時(shí),相容性為有向量詞弧相容.給定一個(gè)二元量詞約束滿足問題P,如果對(duì)于每個(gè)自然數(shù)i≤k,P是有向量詞i相容的,則稱P是強(qiáng)有向量詞k相容的;如果P是強(qiáng)有向量詞n相容的,則P是有向全局相容的.其中,n為變量的數(shù)量.如果P是有向全局相容的,則P是可滿足的,P的一個(gè)解可以按量詞前綴的變量順序通過無回溯地?cái)U(kuò)展策略樹而得到.

2.2 全稱量詞相容性

為了更好地揭示問題內(nèi)部隱藏的易解屬性,本節(jié)深入研究量詞約束滿足問題的結(jié)構(gòu)性質(zhì).不同于經(jīng)典的約束滿足問題,量詞約束滿足問題的結(jié)構(gòu)特征除了變量間的約束,還決定于量詞變量在前綴中的順序.因此,這里將提出一個(gè)新的相容性概念,即全稱量詞變量相容性,它用于刻畫一組存在量詞變量和所有的全稱量詞變量的約束關(guān)系.類似于量詞相容性,全稱量詞變量相容性也由一系列的定義組成.

定義3(λ?相容).給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),如果對(duì)于每個(gè)有序的變量對(duì)(λxi,?xj)使得xi?xj,且對(duì)于每個(gè)值a∈D(xi),任意的值b∈D(xj)滿足(a,b)∈R(xi,xj),其中,λ是?或者?,則稱P是λ?相容的.

λ?相容保證了P是非平凡的,若P不滿足該相容性,則全稱量詞變量存在不可被滿足的賦值,所以該問題平凡無解.

定義4(?量詞節(jié)點(diǎn)相容).給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),如果P是λ?相容的,且對(duì)于任意存在量詞變量xi,對(duì)于任意的一組X?(xi)的賦值α,存在一個(gè)xi的取值a∈D(xi),使得α與a相容,則稱P是?量詞節(jié)點(diǎn)相容的.

從定義4可以看出,如果P是?量詞節(jié)點(diǎn)相容的,則P中每一變量對(duì)(?xi,?xj)(xi?xj)是有向量詞弧相容的.類似地,(?xi,?xj)和(?xi,?xj)也是有向量詞弧相容的.但是這并不意味著P是有向量詞弧相容,原因在于不能保證P中的(?xi,?xj)也是有向量詞弧相容的.事實(shí)上,將P化簡(jiǎn)成?量詞節(jié)點(diǎn)相容的形式可以刪除不支持任何一個(gè)量詞分支的值.

接下來,定義有向?量詞k相容.

定義5(有向?量詞k相容).給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),如果P是λ?相容的,且對(duì)于每個(gè)有序的變量集合{y1,y2,…,yk?1,xm},對(duì)于任意一個(gè)X?(xm)∪{y1,y2,…,yk?1}的相容賦值αa1a2…ak?1,存在一個(gè)ak∈D(xm),使得αa1a2…ak?1ak是相容的,則稱P是有向?量詞k相容的.

特殊地,有向?量詞1相容是?量詞節(jié)點(diǎn)相容;有向?量詞2相容稱為有向?量詞弧相容.類似于量詞相容性,強(qiáng)有向?量詞k相容是指對(duì)于每個(gè)i≤k,P是有向?量詞i相容的;如果P是強(qiáng)有向?量詞r相容的,則它是有向全局?量詞相容的.其中,r是存在量詞變量的個(gè)數(shù),即r=|X?|.定義5保證了P中的(?xi,?xj)是有向量詞弧相容的,所以強(qiáng)有向?量詞弧相容蘊(yùn)含了有向量詞弧相容.

值得注意的是,如果P是有向全局量詞相容的,那么P一定是有向全局?量詞相容的,但是反之不成立.這是因?yàn)樵跐M足有向?量詞k相容時(shí),可能存在一組存在量詞變量的賦值不與任何全稱量詞分支相容,而對(duì)于該賦值,其后續(xù)的存在量詞變量并不需要存在一個(gè)與之相容的值.上述討論說明,有向全局?量詞相容的限制條件比有向全局量詞相容松弛,但這并不影響其保證量詞約束滿足問題的可滿足性.

引理1.給定一個(gè)二元量詞約束滿足問題P,如果P是有向全局?量詞相容的,則P是可滿足的.

證明:首先,由于P是?量詞節(jié)點(diǎn)相容的,那么第1個(gè)變量的值域不為空,因此存在一個(gè)相容的1層策略樹(包含根節(jié)點(diǎn)).不失一般性,這里證明:對(duì)于任意的、相容的k?1層相容策略,都可以擴(kuò)展成一個(gè)k層策略.如果第k層變量xk是一個(gè)全稱量詞變量,由于全稱量詞節(jié)點(diǎn)相容蘊(yùn)含了包含該變量的變量對(duì)是量詞弧相容的,則xk的任何值都是相容的,所以擴(kuò)展出的k層策略樹是相容的.如果第k層變量xk是一個(gè)存在量詞變量,若前k?1層包含m個(gè)存在量詞變量,則m+1≤r(r為全部存在量詞變量的數(shù)量).又因?yàn)镻是有向?量詞m+1相容的,所以對(duì)于部分策略樹中的每一個(gè)全稱量詞分支α,都存在一個(gè)xk的值a,使得αa是相容的,因此擴(kuò)展出的k層策略是相容的.綜上,存在一個(gè)相容的n層策略是P的一個(gè)解,所以P是可滿足的.□

在引理1中,有向全局?量詞相容是P的可滿足性的一個(gè)充分條件.事實(shí)上,如果對(duì)于任意的k≤n,前k個(gè)變量是有向量詞相容的,即可保證P的可滿足性.顯然,前k個(gè)變量的相容性松弛了有向?量詞k相容和量詞k相容的約束限制.

2.3 全稱量詞相容性算法

本節(jié)討論與有向?量詞相容性相關(guān)的算法和計(jì)算復(fù)雜性,并詳細(xì)闡述判斷其節(jié)點(diǎn)相容和弧相容的驗(yàn)證方法.這里首先定義支持集I上的交集算子.設(shè)Π={I1,I2,...,Im}為存在量詞變量z的一個(gè)支持集集合,而Iz是z的一個(gè)支持集,交集算子被定義為Π∩Iz={I|I=Ii∩Iz,其中,Ii∈Π}.該算子在產(chǎn)生的新集合中重復(fù)的元素被去除,而新集合中可以存在空集元素,即?∈Π∩Iz.給定一個(gè)存在量詞變量z,則全稱量詞變量集合X?(z)關(guān)于z的支持集集合記為Πz(?)={I|存在一組賦值X?(z)=α,使得I是α關(guān)于z的支持集}.

基于上述交集算子,我們提出一個(gè)計(jì)算給定存在量詞變量x的全部支持集的算法.該算法采用增量計(jì)算的方法,具體過程如算法1所示.

算法1.全稱量詞變量支持集集合算法.

輸入:P=(X,Q,D,C),z是一個(gè)存在量詞變量;

輸出:支持集集合Πz(?).

算法1輸入的問題P需要滿足λ?相容性,而算法過程中不再判斷2個(gè)全稱量詞變量之間的約束關(guān)系.算法1進(jìn)行迭代求解,最后返回z的全稱量詞變量支持集集合.如果該集合中包含?元素,則表明存在至少一個(gè)全稱量詞分支,使得z中不存在一個(gè)賦值與該路徑相容.因此,輸入問題P不是有向?量詞節(jié)點(diǎn)相容的.

接下來討論判斷一個(gè)二元量詞約束滿足問題有向?量詞節(jié)點(diǎn)相容性和有向?量詞弧相容性的方法.

a) 對(duì)于?量詞節(jié)點(diǎn)相容性而言,我們首先需要判斷全稱量詞變量間的相容性,這個(gè)過程可以直接判斷兩個(gè)全稱量詞變量間是否存在約束關(guān)系:如果存在且這個(gè)約束關(guān)系是非平凡的,則可以判定P不是?量詞節(jié)點(diǎn)相容的;否則,根據(jù)?量詞節(jié)點(diǎn)相容性的定義,對(duì)于每個(gè)存在量詞變量x,我們都需要判斷每一個(gè)全稱量詞分支是否存在一個(gè)x的賦值與之相容,而全稱量詞的取值組合是隨全稱量詞變量個(gè)數(shù)指數(shù)級(jí)增長(zhǎng)的,逐個(gè)分支判斷會(huì)導(dǎo)致計(jì)算時(shí)間是指數(shù)級(jí)的.但是還可以通過計(jì)算x的支持集集合完成這一判斷過程.如果支持集集合中包含了?,則存在一個(gè)全稱量詞分支不能擴(kuò)展到變量x,因此P不是?量詞節(jié)點(diǎn)相容的;否則,P是?量詞節(jié)點(diǎn)相容的.

b) 對(duì)于有向?量詞弧相容性而言,我們可以使用與?量詞節(jié)點(diǎn)相容性同樣的方式進(jìn)行判斷.對(duì)于每一個(gè)存在量詞變量對(duì)(y,z),我們可以計(jì)算Iz(a)的值,計(jì)算過程可以通過改造算法1得到.其中,在第11行的對(duì)于每個(gè)xj的值,首選判斷該值是否與a相容:如果相容,則進(jìn)行交集的計(jì)算;否則,嘗試下一個(gè)值.在計(jì)算集合Iz(a)后,我們只需考察集合中是否包含?元素:如果包含,則P不是有向?量詞弧相容的.值得注意的是,支持集的集合Iz(a)本身也可能是空集,這是由于沒有與a相容的全稱量詞分支造成的,所以它不是判斷不滿足有向?量詞弧相容性的依據(jù).若n?是常數(shù),則有向?量詞弧相容性的判斷過程也是多項(xiàng)式時(shí)間的.

顯然,判斷?量詞節(jié)點(diǎn)相容性和有向?量詞弧相容性的時(shí)間復(fù)雜度主要決定于支持集的數(shù)量.設(shè)L為全部存在量詞變量支持集的數(shù)量,則不難推出判斷有向?量詞節(jié)點(diǎn)相容性的時(shí)間復(fù)雜度為O(LMn),而判斷有向?量詞弧相容性的時(shí)間復(fù)雜度為O(LM2n2).

但在一些特定情況下,支持集的計(jì)算過程可以是多項(xiàng)式時(shí)間的.這里首先簡(jiǎn)要介紹BTP(broken-triangle property),它最早是由Cooper等人提出的[24,26],并用來確定約束滿足問題中的易解子類.如果一個(gè)約束滿足問題中的3個(gè)變量組成一個(gè)有序三元組(x,y,z),如果對(duì)于任意一個(gè)值對(duì)(a,b)∈R(x,y)使得a和b關(guān)于z的支持集滿足Iz(a)?Iz(b)或者Iz(a)?Iz(b),則稱(x,y,z)滿足BTP.在一個(gè)二元量詞約束滿足問題中,若給定一個(gè)存在量詞變量xk,在xk之前的任意兩個(gè)全稱量詞變量x與y有三元組(x,y,z)滿足BTP,算法1中的支持集交集運(yùn)算并不會(huì)產(chǎn)生新的支持集,因此計(jì)算過程中,|Π[xi,a]|的元素個(gè)數(shù)的一個(gè)上界是d|X?|,所以Πz(?)可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算.

給定一個(gè)二元量詞約束滿足問題P,如果對(duì)于每個(gè)存在量詞變量z,計(jì)算其全稱量詞關(guān)于z的支持集集合都是多項(xiàng)式時(shí)間的,則稱P滿足全稱量詞支持集易解屬性.基于這一屬性,在下一節(jié)討論量詞約束滿足問題的易解子類.

3 易解子類

近年來,量詞約束滿足問題的混合易解子類得到了深入的研究.現(xiàn)有易解子類是基于經(jīng)典約束滿足問題的BTP屬性擴(kuò)展得到的.本節(jié)將討論如何通過全稱量詞相容性擴(kuò)展已有的混合易解子類.這里基于BTP,說明全稱量詞相容性在判斷易解子類中的作用.

首先簡(jiǎn)要說明已知的BTP易解子類.給定一個(gè)二元約束滿足問題,如果存在一個(gè)變量的全序,使得任意3個(gè)變量在該序下滿足BTP,則可以在多項(xiàng)式時(shí)間內(nèi)判斷約束滿足問題是否是可滿足的.這里只需要將給定的約束滿足問題化簡(jiǎn)為弧相容的形式,如果化簡(jiǎn)結(jié)果不出現(xiàn)值域?yàn)榭占淖兞?則該問題是可滿足的.BTP還被擴(kuò)展到軟約束問題中[27],而后被用來識(shí)別量詞約束滿足問題中的易解子類[28].給定一個(gè)量詞約束滿足問題P,P在序?下滿足BTP是指對(duì)于P中任意有序三元組(x,y,z)使得x?y?z,(x,y,z)滿足BTP.由于量詞約束滿足問題的變量需要按其前綴中的順序賦值,所以只需判斷在該變量序下,量詞約束滿足問題是否滿足BTP即可.定理1確定了基于BTP的量詞約束滿足問題易解子類.

定理1[28].給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),如果P是有向量詞弧相容的,且P在其前綴中的變量序下滿足BTP,則P是可滿足的.

同時(shí),確定一個(gè)易解子類不僅需要證明其中包含的量詞約束滿足問題可在多項(xiàng)式時(shí)間內(nèi)求解,還需證明給定的一個(gè)二元量詞約束滿足問題判別其是否屬于該易解子類也是多項(xiàng)式時(shí)間的.不難看出,判斷P是否為有向量詞弧相容的并且是否滿足BTP是多項(xiàng)式時(shí)間的.

接下來,基于全稱量詞變量的支持集集合本文提出一個(gè)新的混合易解子類,這里首先定義基于支持集集合的BTP性質(zhì).

給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),x,y和z是3個(gè)存在量詞變量,Πz(?)是全稱量詞變量關(guān)于z的支持集集合,如果對(duì)于任意值對(duì)(a,b)∈R(x,y)和任意的I∈Πz(?),滿足Iz(a)∩I?Iz(b)∩I或者Iz(a)∩I?Iz(b)∩I,則稱三元組(x,y,z)滿足uBTP.

定義6(uBTP).給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),P中任意存在量詞變量組成的三元組(x,y,z)使得x?y?z,滿足uBTP,則稱P滿足uBTP.

例2(uBTP的實(shí)例):若P是一個(gè)二元量詞約束滿足問題,x,y,z是其中的3個(gè)存在量詞變量.若z的支持集集合I={{1,2},{2,3},{1,2,4}}并且Iz(x=1)={1,2,3},Iz(y=1)={1,2,4},則(x,y,z)滿足uBTP屬性;若Iz(x=2)={1,2}并且Iz(y=2)={2,4},則由于Iz(x=2)和Iz(y=2)分別與I中第1個(gè)元素取交集后的兩個(gè)集合不存在包含關(guān)系,所以(x=2,y=2,z)不滿足uBTP屬性.

定理2.給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),如果P是強(qiáng)有向?量詞弧相容的,并且P滿足uBTP,則P是可滿足的.

證明:這里只需證明P是有向?量詞全局相容的,因此采用歸納法證明:對(duì)于任意的k>2,如果P是有向?量詞k?1相容的,那么它是有向?量詞k相容的.不妨設(shè)P是有向?量詞k?1相容的,β是一個(gè)含有k?1個(gè)存在量詞變量的相容賦值,z是這k?1個(gè)變量后的一個(gè)存在變量.考慮任意一個(gè)包含X?(z)的賦值α使得αβ是相容的,因?yàn)镻滿足uBTP,則對(duì)于β中任意的兩個(gè)賦值x=a,y=b,有Iz(αa)?Iz(αb)或者Iz(αa)?Iz(αb).因此在所有的支持集Iz(f)中,f為β中所包含的任意一個(gè)賦值,存在一個(gè)最小的支持集被所有其他支持集包含,即Iz(c)?Iz(f),其中,c是β中的一個(gè)賦值.所以存在一個(gè)z的取值c,使得αβc是相容的.因此可以得到結(jié)論,P是有向?量詞k相容的.又因?yàn)镻是有向?量詞節(jié)點(diǎn)相容的和有向?量詞弧相容的,所以P是有向?量詞全局相容的.根據(jù)引理1知,P是可滿足的.□

定理3.給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C),如果P滿足?量詞支持集易解屬性,判斷P是否滿足uBTP可以在多項(xiàng)式時(shí)間內(nèi)完成.

證明:對(duì)于任意的由存在量詞變量組成的三元組(x,y,z)使得x?y?z,如果對(duì)于任意的值對(duì)(a,b)∈R(x,y)和每個(gè)在非空集合Πz(?,ab)中的支持集I,I∩Iz(a)和I∩Iz(b)存在包含關(guān)系,則對(duì)于任意的X?(z)的賦值α使得Iz(α)=I,有Iz(αa)?Iz(αb)或者Iz(αa)?Iz(αb),因此P滿足uBTP.又因?yàn)槿我獾摩皕(?,ab)是多項(xiàng)式時(shí)間可以獲得的,整個(gè)判斷過程是多項(xiàng)式時(shí)間的.因此,判斷P是否滿足uBTP是多項(xiàng)式時(shí)間的.□

這里需要解釋的是:若集合Πz(?,ab)為空,則表示不存在一個(gè)α使得α與a,b相容,則此種情況不需要進(jìn)行集合包含的判斷.

uBTP是對(duì)BTP概念的擴(kuò)展,因此使用uBTP識(shí)別的易解子類包含了文獻(xiàn)[28]中用BTP識(shí)別的易解子類,這里將舉例說明滿足uBTP的量詞約束滿足問題.

回顧例1中的量詞約束滿足問題,顯然,該問題不滿足BTP.原因是三元組(y,z,t)之間的不等式約束不滿足BTP,但是不難驗(yàn)證P滿足uBTP,因此可以直接構(gòu)造P的一個(gè)解樹而不需要回溯搜索.而uBTP所確定的易解子類是一個(gè)更一般化的易解子類形式,它可以囊括更多的易解問題實(shí)例.

命題1(uBTP的值約減屬性).給定一個(gè)二元量詞約束滿足問題P=(X,Q,D,C)使得P是強(qiáng)有向?量詞弧相容的,并且P滿足uBTP,如果α是前k個(gè)變量的一組相容賦值,則P(α)是強(qiáng)有向?量詞弧相容的且P(α)滿足uBTP.

證明:先證強(qiáng)有向?量詞弧相容,令z為P(α)=(X′,Q′,D′,C′)中的一個(gè)存在量詞變量,β為P(α)中X′?(z)的一組相容賦值,因?yàn)镻滿足uBTP,則P(α)是可滿足的,所以P(α)中Iz(β)不為空,所以P(α)是?量詞節(jié)點(diǎn)相容的.若y為z后的一個(gè)存在量詞變量,a是z在P(α)中一個(gè)取值且βa相容,則由于P是有向?量詞弧相容的,所以在P中存在一個(gè)y的取值b,使得αβab相容.由于b與α是相容的,則在P(α)中,b仍是y的一個(gè)取值,因此P(α)是有向?量詞弧相容的.再證P(α)滿足uBTP,由于P(α)中的變量的值域被約減后并不影響支持集之間的包含關(guān)系,所以P(α)仍滿足uBTP.□

uBTP的值約減屬性說明了變量的賦值過程保持了uBTP及易解性質(zhì),為隱蔽集的識(shí)別方法的設(shè)計(jì)提供了理論依據(jù).

4 隱蔽集的識(shí)別

易解子類可以將一部分帶有特殊約束結(jié)構(gòu)的問題囊括其中,從而證明這些特殊問題是多項(xiàng)式時(shí)間可解的.但由于量詞約束滿足問題本身的計(jì)算復(fù)雜性,能夠被直接證明屬于某個(gè)已知易解子類的特殊問題是有限的,大量的量詞約束滿足問題仍屬于PSPACE完全的范疇.然而通常情況下,可以在這些問題中識(shí)別出一些子結(jié)構(gòu)或子問題屬于某個(gè)已知的易解子類.為了分析問題中所隱藏的易解結(jié)構(gòu)并分離出易解部分,同時(shí)衡量不同易解子類在識(shí)別隱藏結(jié)構(gòu)的效果,隱蔽集的概念被提出.它是由Williams等人提出的[18],用于研究SAT的易解子結(jié)構(gòu),并用于分析SAT求解算法的性能.而后,隱蔽集的概念被擴(kuò)展到量詞布爾范式中[19].隱蔽集是指一個(gè)變量的集合,存在一組該變量集合的賦值使得剩余的子問題是可滿足的且在多項(xiàng)式時(shí)間內(nèi)可以判定.通常情況下,隱蔽集的研究需基于某一種已知的易解子類.對(duì)于SAT而言,易解子類可以是2-SAT(子句長(zhǎng)度不超過2的合取范式)或者Horn子句等.隱蔽集的長(zhǎng)度影響著求解算法的效率,小隱蔽集意味著求解算法嘗試較少的變量賦值即可找到問題的解.

根據(jù)SAT和量詞布爾范式中的隱蔽集的定義,本文給出量詞約束滿足問題的隱蔽集定義.

定義7(隱蔽集).給定一個(gè)量詞約束滿足問題P,若存在一個(gè)部分策略樹Ti,使得對(duì)于該樹中任何分支對(duì)應(yīng)的賦值α,存在一個(gè)多項(xiàng)式時(shí)間的算法返回P(α)的一個(gè)解,則稱P的前i個(gè)變量是P的一個(gè)隱蔽集.

若已知一個(gè)量詞約束滿足問題的隱蔽集,求解該問題則簡(jiǎn)化為尋找一個(gè)滿足隱蔽集定義的部分策略樹Ti,其計(jì)算復(fù)雜度與i值相關(guān),而問題的變量數(shù)量只影響計(jì)算復(fù)雜度的多項(xiàng)式部分.因此,隱蔽集的存在降低了求解算法的計(jì)算時(shí)間.

顯然,本文提出的uBTP易解子類和已知的BTP易解子類可以用于識(shí)別隱蔽集.為了研究本文提出的混合易解子類對(duì)隱蔽集的影響,我們將分析使用不同易解子類時(shí)隱蔽集的大小,即隱蔽集中變量的個(gè)數(shù).

本文基于量詞約束滿足問題求解器QCSP-Solve[5]分析隱蔽集的大小.QCSP-Solve是一個(gè)基于回溯算法的完備的量詞約束滿足問題求解器,它可以求解二元問題.同時(shí),QCSP-Solve中還加入了諸多在CSP求解中使用較為成熟的技術(shù).例如,基于沖突的回跳技術(shù)[29]在產(chǎn)生沖突賦值時(shí),會(huì)分析失敗的原因,并回跳至產(chǎn)生沖突變量對(duì)應(yīng)的層.這種技術(shù)不同于一次只回溯1層的普通回溯算法,它可以大幅度減少不必要的搜索空間.在預(yù)處理過程中,QCSP-Solve使用了量詞弧相容算法QAC-2001[30]和對(duì)稱消除策略等技術(shù),用于加速求解器的效率.

在實(shí)驗(yàn)分析中,本文改造了QCSP-Solve中的算法,在回溯搜索的基礎(chǔ)上加入了易解子問題的識(shí)別過程.在展開每個(gè)節(jié)點(diǎn)并對(duì)變量賦值后,算法調(diào)用識(shí)別算法,判斷后續(xù)未賦值變量間是否滿足BTP(uBTP)屬性,從而識(shí)別出易解子問題.若未賦值變量屬于給定的易解子類且是可滿足的,則表明當(dāng)前的量詞分支可以構(gòu)成隱蔽集對(duì)應(yīng)的部分策略樹的一個(gè)分支,因此算法回溯并嘗試下一個(gè)量詞分支.否則繼續(xù)嘗試下一個(gè)未賦值的變量.當(dāng)算法找到問題一個(gè)解樹時(shí),根據(jù)命題1的結(jié)論,uBTP易解子類中的一個(gè)問題實(shí)例P在對(duì)前i個(gè)變量賦值為α后,其剩余的子問題P(α)仍然滿足有向?量詞弧相容和uBTP.所以在回溯搜索過程中,具有最多變量賦值的量詞分支的長(zhǎng)度即為所找到的隱蔽集的大小.但是找出某個(gè)量詞約束滿足問題的全部隱蔽集需要遍歷整個(gè)解空間,這對(duì)于PSPACE完全類中的問題是十分困難的,而計(jì)算最小的隱蔽集也是困難的.因此,本文只分析找到第1個(gè)解時(shí)隱蔽集的大小.

5 實(shí)驗(yàn)分析

本節(jié)通過實(shí)驗(yàn)分析隱蔽集大小.分析隱蔽集大小的實(shí)驗(yàn)采用一系列隨機(jī)生成的量詞約束滿足問題作為測(cè)試實(shí)例.所有實(shí)驗(yàn)采用一臺(tái)工作站進(jìn)行,其中,CPU為E5-1650v4,內(nèi)存為16GB,Windows Server 2016作為操作系統(tǒng).實(shí)驗(yàn)算法采用C++編寫,并將檢測(cè)隱蔽集的代碼與QCSP-Solve算法結(jié)合,實(shí)驗(yàn)系統(tǒng)采用Visual Studio 2010編譯.本節(jié)首先介紹量詞約束滿足問題的生成模型,然后分析實(shí)驗(yàn)結(jié)果,比較不同約束密度的情況下,兩個(gè)混合易解子類的隱蔽集大小,以及QCSP-Solve在回溯搜索過程中找到易解部分時(shí)未賦值變量個(gè)數(shù)平均值.

5.1 生成模型

在衡量量詞約束滿足問題的算法效率時(shí),隨機(jī)生成的問題實(shí)例通常被作為測(cè)試基準(zhǔn).使用最多的隨機(jī)生成模型是Model B[31].該模型最早用于生成約束滿足問題,其改進(jìn)的版本具備了精確的可滿足性相變點(diǎn),稱其為Model RB[32].而后,量詞約束滿足問題也使用此類模型作為測(cè)試基準(zhǔn).

在約束滿足問題的Model B中,4個(gè)參數(shù)被用來控制生成問題的規(guī)模和難度,所以通常用四元組(n,d,p,q)表示,其中,n為變量的個(gè)數(shù),d為每個(gè)變量值域的大小,p為約束的密度參數(shù),它控制問題中約束的數(shù)量.

模型從n(n?1)/2個(gè)可能的二元約束中均勻地隨機(jī)地選取|pn(n?1)/2|個(gè)約束,q為約束的松緊度參數(shù).對(duì)于每個(gè)二元約束模型,將均勻地隨機(jī)地選取qd2個(gè)值對(duì)設(shè)為允許的關(guān)系元組.對(duì)于量詞約束滿足問題,還需要額外的3個(gè)控制參數(shù),n?指定了全稱量詞變量的個(gè)數(shù),q??和q??被用來取代q,q??表示一個(gè)全稱量詞變量和一個(gè)存在量詞變量之間的約束松緊度,q??表示兩個(gè)存在量詞變量之間的約束松緊度.

另外,全稱量詞變量在前綴中的排列位置也會(huì)影響量詞約束滿足問題的約束結(jié)構(gòu).在本文的實(shí)驗(yàn)中,兩種排列方式將被采用.第1組中,n?個(gè)全稱量詞變量的位置是隨機(jī)選擇的;第2組中,全稱量詞變量和存在量詞變量被劃分到變量塊中,兩種變量塊交替排列.

但是研究指出,量詞約束滿足問題的生成模型存在平凡不可滿足的缺陷(flaw issue)[31].如果n?足夠大且q??過小,則生成的問題中會(huì)存在某個(gè)全稱量詞分支,使某個(gè)存在量詞變量中沒有相容的賦值,這樣導(dǎo)致了所生成的問題是平凡無解的.為了解決這一缺陷,Gent等人提出了基于雙映射的結(jié)構(gòu)化約束關(guān)系元組生成方案,代替完全隨機(jī)的生成模型.但是結(jié)構(gòu)化的生成方案破壞了隨機(jī)均勻地值對(duì)選取規(guī)則,而且這種方案使得90%以上的值對(duì)都是允許的關(guān)系元組,即q??大于0.9.事實(shí)上,如果控制q??在0.9以上,平凡不可滿足的缺陷發(fā)生概率是極低的.因此在本節(jié)的實(shí)驗(yàn)中,q??的取值為0.95.

5.2 實(shí)驗(yàn)結(jié)果

本節(jié)實(shí)驗(yàn)對(duì)比BTP易解子類和uBTP易解子類確定量詞約束滿足問題中的隱蔽集大小的效果.

首先分析第1組實(shí)驗(yàn).在生成實(shí)例時(shí),變量的順序隨機(jī)排列.這里取n=20,d=10,而n?的取值分為兩種情況,n?=6和n?=8.約束密度參數(shù)p的值從0.2遞增到0.5,增量為0.025.當(dāng)p=0.2時(shí),約束關(guān)系圖的密度較為疏松,所生成的問題實(shí)例較為簡(jiǎn)單;而p=0.5時(shí),約束圖密度增大,約束增多,問題實(shí)例的求解難度也隨之增加.對(duì)于每個(gè)p值,q??的值從0.7遞增到0.9,增量為0.05,共5個(gè)取值,以生成不同難度的約束關(guān)系.q??值越小,相容的賦值就越小.而當(dāng)q??過小時(shí),生成的實(shí)例可能是不可滿足的,因此q??的值最小為0.7,以保證部分生成的實(shí)例是可滿足的.對(duì)于每組p和q??的取值,生成20個(gè)實(shí)例,并計(jì)算它們的隱蔽集大小.

表1列出了n?=6時(shí)的實(shí)驗(yàn)結(jié)果,表2列出了n?=8的結(jié)果.

Table 1 Comparison of the backdoor size detected by BTP and uBTP (n?=6)表1 BTP與uBTP的隱蔽集大小的對(duì)比結(jié)果(n?=6)

Table 2 Comparison of the backdoor size detected by BTP and uBTP (n?=8)表2 BTP與uBTP的隱蔽集大小的對(duì)比結(jié)果(n?=8)

對(duì)于每個(gè)p值,計(jì)算q??的5個(gè)取值的100個(gè)實(shí)例求解到的隱蔽集大小的平均值,同時(shí)還統(tǒng)計(jì)了QCSP-Solve在回溯搜索過程中找到易解部分時(shí)未賦值變量個(gè)數(shù)平均值.從表1和表2中可以看出,隨著p值的增大,問題實(shí)例的難度也隨之增加.由于約束數(shù)量增多,在回溯過程中賦值后,剩余的變量構(gòu)成一個(gè)易解問題的可能性變小,所以求解到的隱蔽集的規(guī)模隨p值增加而增大.而對(duì)于所有p值,使用uBTP作為易解子類的隱蔽集規(guī)模比BTP小,這一結(jié)果與uBTP易解子類包含BTP易解子類的事實(shí)相符,所以u(píng)BTP應(yīng)識(shí)別到更小的隱蔽集.而對(duì)于簡(jiǎn)單問題(p值較小時(shí)),規(guī)模差別更大一些,uBTP的隱蔽集更具有優(yōu)勢(shì).而對(duì)于每個(gè)p值平均搜索深度略小于隱蔽集大小,uBTP的平均搜索深度也小于使用BTP時(shí)的平均值.這意味著uBTP減小了回溯搜索過程所展開的節(jié)點(diǎn)數(shù)量.隨著n?的增加問題變難,所以隱蔽集規(guī)模略有增加.但是對(duì)于約束密度較大時(shí),兩種易解子類的效果不明顯.

接下來分析第2組實(shí)驗(yàn).同樣取n=20,d=10.而全稱量詞變量的排列不再是隨機(jī)的,而是結(jié)構(gòu)化的.每個(gè)全稱(存在)量詞變量塊包含1個(gè)(2個(gè))全稱(存在)量詞變量,全稱量詞變量塊和存在量詞變量塊交替出現(xiàn),并設(shè)定n?=6,前綴中變量的順序是:2個(gè)存在量詞變量,然后1個(gè)全稱量詞變量,以此類推.p的取值范圍為0.2～0.5,q??的值為0.7～0.9.對(duì)于每個(gè)p,100個(gè)實(shí)例的平均值被計(jì)算.表3列出了該組實(shí)驗(yàn)的結(jié)果.與前一組結(jié)果類似,uBTP可以識(shí)別到更小的隱蔽集,而這種優(yōu)勢(shì)在低密度約束問題中體現(xiàn)得更加明顯.

Table 3 Comparison of the backdoor size detected by BTP and uBTP (alternative blocks)表3 BTP與uBTP的隱蔽集大小的對(duì)比結(jié)果(變量塊交替)

6 相關(guān)工作

約束滿足問題可解子類的研究可以追溯到20世紀(jì)80年代.Freuder首先指出:如果一個(gè)約束滿足問題的約束圖是樹形結(jié)構(gòu),則存在一個(gè)不需要回溯的算法在多項(xiàng)式時(shí)間內(nèi)求解該問題[33].而后,易解子類的研究逐步興起.一方面,利用約束圖結(jié)構(gòu)的特性識(shí)別易解子類和分析計(jì)算復(fù)雜度[34?36];另一方面,研究約束關(guān)系的特征也是一個(gè)重要的確定可解子類的方法.這方面的研究主要集中在約束語言和約束關(guān)系的代數(shù)學(xué)方法上.例如,Bulatov等人研究了有限域上的復(fù)雜性分類[37].混合易解子類是最近幾年提出的一種全新的識(shí)別易解子類的技術(shù).它結(jié)合了結(jié)構(gòu)子類和關(guān)系子類的特點(diǎn),同時(shí)限制約束圖的結(jié)構(gòu)和每個(gè)約束中的允許的元組關(guān)系,從而得到更一般化的易解子類.

一個(gè)代表性的混合易解子類是Cooper等人提出的BTP概念,他們通過一般化樹形結(jié)構(gòu)并限制3個(gè)變量之間的約束關(guān)系,得到了約束滿足問題上的混合易解子類[24].基于BTP的混合易解子類是基于樹狀約束結(jié)構(gòu)子類更一般化的性質(zhì),通過加入約束關(guān)系的限制,使得樹狀結(jié)構(gòu)的特征這一限制條件可以適當(dāng)?shù)胤艑?因此,該易解子類在增加元組關(guān)系限制的同時(shí)放松了對(duì)結(jié)構(gòu)的限制條件,從而得到比樹狀約束結(jié)構(gòu)子類更一般化的結(jié)論.因此,BTP子類可以囊括更多的易解情況.BTP定義了3個(gè)變量間的約束關(guān)系,而更多的變量間的關(guān)系也被討論.例如,Cyril等人提出了Extendable-Triple Property(ETP)[38],定義了4個(gè)變量間的性質(zhì).BTP的概念還被擴(kuò)展到約束優(yōu)化問題中,與之對(duì)應(yīng)的是Joint-winner屬性[27].該屬性同樣定義了3個(gè)變量之間的約束元組關(guān)系,符合該屬性的軟約束問題是多項(xiàng)式時(shí)間內(nèi)可解的.一個(gè)更一般化的結(jié)果是Naanaa提出的Rank CSPs[39].該子類利用集合論中秩的概念,計(jì)算支持集的集合中,若干支持集取交集的秩.基于Rank CSPs的易解子類被證明包含了諸多已知的混合易解子類,例如BTP、ETP、行凸屬性Row convexity[40]和m-tight[41]約束屬性等.但是BTP具有比其他易解子類更多的性質(zhì),例如BTP在弧相容算法約減后仍滿足BTP.而類似的性質(zhì),其他混合易解子類并不具備,ETP在路徑相容約減運(yùn)算時(shí)(3個(gè)變量間的相容性)下并不是封閉的.Cohen等人還深入研究了更多的混合可解子類的情況,并提出了二元約束滿足問題上的復(fù)雜性分類定理[42].

BTP易解子類以及其他的混合易解子類還用于變量的消元中[43].若存在一個(gè)變量全序使得最后的一些變量滿足BTP,則這些變量是可以被消元的.但是給定一個(gè)約束滿足問題,尋找含有變量數(shù)最多的子集使得子集中的變量在某個(gè)變量順序下滿足BTP屬性卻是NP難的.基于BTP,更多的用于變量消元的微結(jié)構(gòu)被識(shí)別出來,但是這些結(jié)構(gòu)具有十分復(fù)雜的元組關(guān)系[44].另一方面,基于BTP的值合并技術(shù)也被提出[45].該技術(shù)可以對(duì)約束滿足問題進(jìn)行化簡(jiǎn),在保證問題可滿足性不變的情況下,合并具有相似結(jié)構(gòu)的值,從而化簡(jiǎn)問題的規(guī)模.基于BTP值合并技術(shù)一個(gè)混合易解子類也被提出.

BTP描述了二元約束之間的關(guān)系,為了描述二元以上的約束滿足問題,對(duì)偶的BTP被提出[46],一個(gè)多元約束滿足問題可以轉(zhuǎn)化成對(duì)偶的二元形式,即將約束映射成變量,值域?yàn)榧s束中的元組關(guān)系,從而在其對(duì)偶的問題上定義BTP以確定多元問題的易解結(jié)構(gòu).另外,BTP還應(yīng)用于識(shí)別隱含的易解結(jié)構(gòu),Mouelhi等人研究了在不同相容性等級(jí)下,BTP易解子類涵蓋各類約束滿足問題的能力[47],并指出,高階相容性可以將更多的約束滿足問題確定為是多項(xiàng)式時(shí)間可解的.

對(duì)于量詞約束滿足問題易解子類的研究,目前主要的思路是擴(kuò)展經(jīng)典約束滿足問題的易解子類.例如,在20世紀(jì)70年代就證明了量詞布爾范式實(shí)例中,若子句的長(zhǎng)度都是2則是多項(xiàng)式時(shí)間內(nèi)可解的[48],基于Horn子句的量詞布爾范式實(shí)例也是多項(xiàng)式時(shí)間內(nèi)可解的[49].但是這種方法卻面臨很大的挑戰(zhàn),原因在于:全稱量詞很大程度上改變了約束結(jié)構(gòu),原有的易解子類在量詞約束滿足問題中并不一定成立,因此還需要考慮更多的限制條件.通過這樣的思路,首先,基于結(jié)構(gòu)特征的易解子類被確定出來,Gottlob等人研究了全稱量詞受限情況下基于結(jié)構(gòu)的易解子類[50];其次,Chen等人深入分析了結(jié)構(gòu)易解子類的特征,還分析了基于約束關(guān)系的易解子類的相關(guān)性質(zhì)[51];更進(jìn)一步地,B?rner等人分析了更多的基于約束關(guān)系的可解情況和博弈游戲中多項(xiàng)式時(shí)間可解的問題[52];另外,混合方式的結(jié)構(gòu)分析技術(shù)也被應(yīng)用在量詞約束滿足問題中[28].

易解子類的另一個(gè)重要的應(yīng)用是識(shí)別隱蔽集[18].所謂的隱蔽集是約束滿足問題中的一個(gè)變量子集,并且存在一個(gè)多項(xiàng)式時(shí)間的算法,使得該算法可以求解剩余的問題.換言之,在對(duì)隱蔽集中的變量賦值后,剩下的子問題是多項(xiàng)式時(shí)間可解的.例如,環(huán)割集事實(shí)上就是一個(gè)隱蔽集,在去除環(huán)割集中的變量后,余下的約束圖結(jié)構(gòu)是無環(huán)的,這使得余下的子問題可在多項(xiàng)式時(shí)間內(nèi)求解.利用這一性質(zhì),李占山等人研究了基于環(huán)割集的約束滿足問題結(jié)構(gòu)分解技術(shù)和相關(guān)的約束傳播算法[53?55].Kilby等人[20]通過實(shí)驗(yàn)分析得出,問題求解難度和隱蔽集的大小間存在著密切的關(guān)系.而Ruan等人[21]也研究了隱蔽集對(duì)問題結(jié)構(gòu)和求解難度的影響,并指出:當(dāng)隱蔽集足夠小時(shí),存在多項(xiàng)式時(shí)間算法可以求解該問題.研究者還根據(jù)隱蔽集的概念和相關(guān)性質(zhì),提高了約束滿足問題求解算法的效率.因此,基于何種易解子類,決定了隱蔽集的識(shí)別效率和求解算法的效率.諸多易解子類都被用于識(shí)別隱蔽集中,例如在SAT問題中,主要使用了2-SAT和Horn子類;Misra等人討論了隱蔽集的上界和下界性質(zhì)[56];Samer等人討論了量詞布爾范式中的隱蔽集的復(fù)雜性[19].基于約束關(guān)系的易解子類也被應(yīng)用于隱蔽集的識(shí)別中,而利用混合易解子類的變量消元技術(shù)本質(zhì)上也可以被看作是一個(gè)尋找隱蔽集的過程.因此,易解子類的研究為隱蔽集的識(shí)別和搜索算法的設(shè)計(jì)提供了理論基礎(chǔ).

7 總結(jié)

本文深入研究了量詞約束滿足問題中的約束關(guān)系及混合易解子類所需要的條件,并提出一個(gè)新的量詞約束滿足問題的混合易解子類.正如我們所知:由于全稱量詞變量的引入,量詞約束滿足問題結(jié)構(gòu)性質(zhì)不同于其對(duì)應(yīng)的約束滿足問題.因此,本文提出的方法將量詞約束滿足問題易解子類的識(shí)別分為兩部分:在第1部分中,我們分析一個(gè)存在變量與全稱量詞變量的約束關(guān)系和相容性關(guān)系,并提出全稱量詞相容的概念,同時(shí)討論了多項(xiàng)式時(shí)間的全稱量詞變量相容性判別的情況;在第2部分中,在全稱量詞相容的情況下,分析存在量詞變量之間的約束關(guān)系,并在原有的BTP混合易解子類基礎(chǔ)上一般化其限制條件,提出uBTP的概念,從而達(dá)到擴(kuò)展易解子類的目的.同時(shí),本文的易解子類識(shí)別方法還可以應(yīng)用在擴(kuò)展其他混合易解子類之中,由于ETP、Row convexity屬性和Rank CSP與BTP有類似的性質(zhì),所以還可以利用本文的方法通過擴(kuò)展這些性質(zhì)得到諸多一般化的理論結(jié)果,其中的Rank CSP定義在非二元約束上,而該方法對(duì)非二元問題中易解子類的識(shí)別也是有效的.本文還將混合易解子類應(yīng)用到識(shí)別隱蔽集中,并分析不同易解子類所確定的隱蔽集的大小.通過實(shí)驗(yàn)驗(yàn)證了所提出的易解子類在識(shí)別隱蔽集方面比原有子類更具優(yōu)勢(shì),同時(shí)還可以減少回溯算法中搜索樹的平均深度,以達(dá)到減小搜索空間的目的.