杜江珊, 李占山

(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 符號計(jì)算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室, 長春 130012)

約束滿足問題(constraint satisfaction problems, CSP)[1]是人工智能領(lǐng)域中的重要研究方向, 而求解CSP問題的最有效方法為將相容性算法[2]與搜索算法相結(jié)合的回溯搜索算法(MAC)[3]. 隨著CSP求解問題的深入研究, 多種高效、 表示方式豐富的算法被提出. 其中, 由于表約束在表達(dá)上簡潔、 方便, 因此基于表的相容性算法求解技術(shù)[4]被廣泛應(yīng)用. 對于表約束, 許多經(jīng)典的過濾算法都是在運(yùn)行過程中, 通過推斷出工作在保持不變的約束上減少檢索的. 但在近年研究中, 提出了一種去除遍歷不相關(guān)元組的方式, 達(dá)到減少遍歷次數(shù), 最終提高檢索效率的效果[5]. STR3算法基于該方法, 實(shí)現(xiàn)了對STR和STR2算法的優(yōu)化[6], 但STR3算法不能直接運(yùn)用到負(fù)表中, 當(dāng)約束中支持元組過于龐大時(shí), 其處理元組依然很多. 因此, 受STR3算法的啟發(fā), 本文提出了一種負(fù)表約束算法STRN3, 對STR-N算法進(jìn)行優(yōu)化.

在STRN3算法中, 如何準(zhǔn)確、 高效、 快速地尋找值支持的方式成為其最大的難點(diǎn), 在直接對負(fù)表約束進(jìn)行處理的算法STR-N中, 當(dāng)判斷某個(gè)值是否存在支持時(shí), 必須將全部有效元組均遍歷一遍, 該方法遍歷元組數(shù)量過多[7], 且由于其為負(fù)表約束, 也不能同正表約束直接在有效的正表元組中找到支持的元組. 對于STRN3算法, 其將負(fù)表分解為每個(gè)變量值的升序子表table(C.X.a), 檢索操作在子表中進(jìn)行, 當(dāng)判斷某個(gè)值是否存在支持時(shí), 不用再遍歷所有有效元組, 而是在上次約束傳播的基礎(chǔ)上, 繼續(xù)尋找該值的最小支持區(qū)間即可, 對于上次約束傳播前已經(jīng)遍歷過的元組, 變?yōu)楫?dāng)前無關(guān)元組, 不會再在該次及以后的約束傳播中被訪問, 因此減少了時(shí)間復(fù)雜度. 實(shí)驗(yàn)結(jié)果表明, 在特定結(jié)構(gòu)實(shí)例中, STRN3算法相對于STR-N算法和STR3算法, 優(yōu)勢明顯, 特別是在一些結(jié)構(gòu)突出的實(shí)例中, 效率甚至提升4～5倍.

1 預(yù)備知識

定義1(約束網(wǎng)絡(luò))[8]一個(gè)約束網(wǎng)絡(luò)P通常由一個(gè)三元組構(gòu)成, 表示為P=(X,D,C), 其中:X={X1,X2,…}是一個(gè)有限的變量集合;D={a1,a2,…,ad}是變量的有限值域集合;C={C1,C2,…}是一個(gè)有限約束集合.

定義2(弧相容)[9]給定一個(gè)約束C, 對于任意一個(gè)變量X∈scp(C)中的任意一個(gè)有效值a, 稱約束C是有支持的, 當(dāng)且僅當(dāng)存在至少一個(gè)元組t∈C, 使得a=t[X], 且對于任意一個(gè)不同于變量X的變量Y, 其中Y∈scp(C), 使得t[Y]為變量Y的當(dāng)前有效值. 如果對每個(gè)X∈scp(C), 每個(gè)值a∈dom(X)在C中至少存在一個(gè)支持, 則稱約束C是弧相容的.

定義3(稀疏集) 稀疏集是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu), 用S表示, 其由三部分組成, 分別為兩個(gè)整型數(shù)組dense,sparse和一個(gè)整型變量members. dense表示數(shù)組的常規(guī)表示形式, sparse表示dense中索引與數(shù)值對調(diào)后的數(shù)組, members表示dense中有效值的最大索引值.

例1dense,sparse,members列于表1, 其中： 值2,0,3有效; 1,5,4無效. 由于值0存放在數(shù)組dense中索引值為1的位置, 則sparse[0]=1.

表1 稀疏集示例

2 STRN3算法設(shè)計(jì)

2.1 定 義

定義4(table_all(C,X,a)) 將約束C的變量X值a的有效正子表與負(fù)子表進(jìn)行合并, 并進(jìn)行升序排列, 記作table_all(C,X,a).

定義5(相鄰元組) 設(shè)負(fù)表table(C,X,a)中的兩個(gè)元組t1與t2, 其在table_all(C,X,a)中相鄰, 則t1與t2稱為相鄰元組.

例2圖1為(C,X,0)的負(fù)表約束元組和全部元組. 由圖1可見, 負(fù)表table(C,X,a)中的元組t1： {0,0,0}和t2： {1,0,1}, 在table_all中相鄰, 則t1與t2為相鄰元組.

圖1 (C,X,0)的負(fù)表約束元組和全部元組Fig.1 Negative table constraint tuples and all tuples of (C,X,0)

定義6(有效支持區(qū)間) 設(shè)負(fù)表table(C,X,a)已升序排列, 并存在兩個(gè)元組t1與t2, 且t1

例3假設(shè)在圖1的實(shí)例中, 所有元組均有效, 則大于table(C,X,0)[1]={0,1}存在有效支持元組(0,2)和(0,3), 且包含現(xiàn)在的最小支持元組(0,2), 故為最小有效支持區(qū)間.

2.2 算法思想

本文基于STR3算法, 將其思想應(yīng)用于負(fù)表約束, 提出STRN3算法. 該算法實(shí)現(xiàn)了對STR-N算法的改進(jìn), 相比于STR3算法, STRN3算法可直接在負(fù)表中進(jìn)行處理, 并舍棄了數(shù)據(jù)結(jié)構(gòu)----dep(C,k), 使得對該結(jié)構(gòu)的維持時(shí)間減少到0, 該算法也由路徑最優(yōu)算法轉(zhuǎn)變成近似路徑最優(yōu)算法[9]. STRN3算法的核心思想如下： 將負(fù)表約束按變量值的形式劃分為子表table(C,X,a), 對每個(gè)子表進(jìn)行升序排列, 并對每個(gè)子表進(jìn)行遞歸處理, 對于判斷變量值是否存在支持時(shí), 不再遍歷整個(gè)負(fù)表, 而是在上一次每個(gè)子表的最小支持區(qū)間處, 繼續(xù)在排序完全的子表中, 向升序方向繼續(xù)遍歷并判斷是否存在支持. 對于每個(gè)子表的最小支持區(qū)間, 共有4種處理情況, 需按照各自情形進(jìn)行后續(xù)判斷和處理.

1) 上次傳播最小支持區(qū)間為(-1,p). 從該子表索引p處(table(C,X,a)[p]), 向升序方向?qū)ふ矣行гM, 設(shè)第一個(gè)有效元組為索引p1處的元組t1, 將該元組與當(dāng)前最小有效元組進(jìn)行比較, 若不相等, 則找到最小支持區(qū)間, 區(qū)間為(-1,p1); 若相等, 則未找到最小支持區(qū)間, 繼續(xù)向升序方向?qū)ふ蚁乱粋€(gè)有效元組, 設(shè)該元組為索引p2處的元組t2, 判斷t2與t1是否為相鄰元組, 若不等, 則找到最小支持區(qū)間, 區(qū)間為(p1,p2)； 若相等, 則繼續(xù)尋找, 直到找到索引pn處的有效元組tn, 且與上一有效元組不為相鄰元組, 此時(shí)最小支持區(qū)間為(pn-1,pn).

2) 上次傳播最小支持區(qū)間為(p1,p2). 從子表索引p2處, 向升序方向?qū)ふ矣行гM, 設(shè)第一個(gè)有效元組為索引p3處的元組t3, 判斷t1與t3是否為相鄰元組, 若不等, 則找到最小支持區(qū)間(p1,p3)； 若相等, 則與1)中相等后的處理邏輯一致, 直至找到最小支持區(qū)間(pn-1,pn).

3) 上次傳播最小支持區(qū)間為(p,-1). 判斷索引p處的元組t是否小于當(dāng)前最大有效元組, 若小于, 則在元組t與最大有效元組中必存在有效支持元組, 本次最小支持區(qū)間仍為(p,-1); 若不小于, 則不存在有效元組, 則該值不再存在支持, 約束傳播失敗, 將該值刪除.

4) 上次傳播最小支持區(qū)間為(-1,-1). 此時(shí)該變量值負(fù)子表中的全部不支持元組均無效, 若該值仍然是該變量的有效值, 則必存在有效支持.

以上4種情形均為向升序方向?qū)ふ业接行гM的情形, 若最終找不到有效元組, 則按以下兩種情形處理：

1) 上次傳播最小支持區(qū)間為(-1,p)(p≠-1). 若按上述尋找最小支持區(qū)間對應(yīng)方法中未找到有效元組, 則此時(shí)負(fù)表table(C,X,a)中不存在有效元組, 即值a不存在有效的沖突元組, 若此時(shí)值a在變量X中仍為有效值, 則必存在支持, 此時(shí)最小支持區(qū)間為(-1,-1).

2) 上次傳播最小支持區(qū)間為(n,m)(n≥0,m>n). 若按上述尋找最小支持區(qū)間對應(yīng)方法中, 未找到有效元組, 則在小于table(C,X,a)[n]的元組中, 不存在有效元組, 將元組table(C,X,a)[n]與當(dāng)前最大有效元組相比較, 若小于, 則大于table(C,X,a)[n]的元組中, 必存在有效支持元組, 此時(shí)最小支持區(qū)間為(n,-1); 若不小于, 則不存在有效支持元組, 約束傳播失敗.

STRN3算法為細(xì)粒度算法, 一旦變量X的值a在約束傳播過程中被刪除, 則調(diào)用STRN3算法, 而在預(yù)處理階段, 是對所有初始值進(jìn)行處理, 將此時(shí)不滿足相容性的值刪除, 因此該階段不可能調(diào)用到STRN3算法, 則在預(yù)處理階段中先采用非細(xì)粒度算法進(jìn)行處理. 本文采用STR-N算法, 在應(yīng)用該算法做出預(yù)處理操作后, 必存在值被刪除情形, STRN3算法自然被調(diào)用.

3 實(shí)驗(yàn)結(jié)果與分析

為了證明STRN3算法的改進(jìn)效果, 選取STR-N算法和STR3算法進(jìn)行比較. 算法實(shí)驗(yàn)操作系統(tǒng)為32位的Win7操作系統(tǒng), 硬件資源為Intel (R)Core(TM)i7-3770 CPU@ 3.40 GHz內(nèi)核, 3.46 GB內(nèi)存, 采用JAVA語言. 3種算法均采用dom/ddeg變量啟發(fā)式和字典序值啟發(fā)式[10]. 實(shí)驗(yàn)選取的測試實(shí)例均來自約束求解問題的標(biāo)準(zhǔn)測試實(shí)例網(wǎng)站(http:// www.cril.univ-artois.fr/～lecoutre/benchmarks.html), 3種算法的對比結(jié)果分別列于表2～表4. 其中： 運(yùn)行各算法時(shí)間的單位均為ms, 將運(yùn)行時(shí)間的上限設(shè)為600 000 ms, 當(dāng)超出此時(shí)間后, 不再運(yùn)行; 表2和表3中的運(yùn)行時(shí)間均為運(yùn)行時(shí)間平均值, 測試實(shí)例多數(shù)為10個(gè), 但marc問題系列由于時(shí)間長度問題, 只測試了5個(gè)實(shí)例, crossuk問題系列由于負(fù)表約束過大, 元組存儲超出內(nèi)存限制, 僅進(jìn)行2個(gè)實(shí)例的測試.

表2中, 處理元組數(shù)差值表示在STR-N算法中對元組的處理個(gè)數(shù)與在STRN3算法中對元組處理個(gè)數(shù)的差值, 相鄰元組比較次數(shù)表示在STRN3算法中對于2個(gè)元組是否能成為相鄰元組的判斷次數(shù), 倍數(shù)表示處理元組數(shù)差值與相鄰元組比較次數(shù)之間的倍數(shù), 當(dāng)相鄰元組比較次數(shù)為0時(shí), 用符號“-”表示. STRN3算法的處理過程較STR-N算法復(fù)雜, 其需要對元組的大小進(jìn)行比較, 對元組的有效性進(jìn)行檢查, 并判斷元組是否相鄰等, 其中判斷元組是否相鄰最耗費(fèi)時(shí)間. 通過以上分析可知, 倍數(shù)能成為STRN3算法和STR-N算法的比較參數(shù), 對于處理的元組數(shù), 當(dāng)STR-N算法比STRN3算法高出一定倍數(shù)時(shí), STRN3算法通常會表現(xiàn)出更優(yōu)秀的特質(zhì).

表2 STRN3算法與STR-N算法對比結(jié)果

由表2可見, 雖然處理元組數(shù)差值全部為正數(shù), 即STRN3算法處理了更少的元組, 但卻表現(xiàn)出部分STRN3算法更優(yōu), 部分STR-N算法更優(yōu), 原因是對于STR-N算法表現(xiàn)更優(yōu)秀的實(shí)例, 在STRN3算法中, 相鄰元組的比較次數(shù)過多, 耗費(fèi)了時(shí)間, 使得少處理的元組數(shù)不足與相鄰元組比較次數(shù)的時(shí)間相抵, 因此, 用時(shí)更多、 效率更低； 其他實(shí)例中, 或者是處理元組數(shù)差值較高, 在所處理的元組數(shù)上, STRN3算法明顯小于STR-N算法； 或者在處理元組數(shù)量上雖沒能大幅度減少, 但在相鄰元組的比較次數(shù)上, STRN3算法的值很低, 甚至為零, 因此STRN3算法運(yùn)行效率更高.

表3為STRN3算法與STR3算法的平均對比結(jié)果, 其中對于每個(gè)實(shí)例, 負(fù)表約束中的元組數(shù)均小于其轉(zhuǎn)化為正表約束的元組數(shù), 因此, STRN3算法比STR3算法處理元組數(shù)少, 效率更高. 表4為STRN3算法與STR-N算法最優(yōu)對比結(jié)果. 表4中每行的問題實(shí)例不再是問題系列, 而是一個(gè)具體的實(shí)例, 且所有實(shí)例都是STRN3算法較STR-N算法更優(yōu), 優(yōu)化效果約為5倍, 其中l(wèi)arge-96-unsat_ext優(yōu)化效果最高.

表3 STRN3算法與STR3算法對比結(jié)果

表4 STRN3算法與STR-N算法最優(yōu)對比結(jié)果

綜上所述, 本文基于STR3算法, 通過放棄遍歷不相關(guān)元組的方法, 優(yōu)化了STR-N算法, 提出了STRN3算法, 該算法的最大優(yōu)點(diǎn)為快速地尋找值支持的方式, 并且STRN3算法放棄了STR3算法中的dep數(shù)據(jù)結(jié)構(gòu), 成為一種近似路徑最優(yōu)算法. 由實(shí)驗(yàn)結(jié)果可得如下結(jié)論：

1) 當(dāng)實(shí)例中支持元組數(shù)多于不支持元組數(shù)時(shí), STRN3算法相對STR3算法效率更高；

2) 對于實(shí)例中元組的處理數(shù)量, STR-N算法較STRN3算法高出一定差值時(shí), STRN3算法相對STR-N算法效率更高；

3) 元組的處理數(shù)量為影響STRN3算法效率的第一因子, 此外, 相鄰元組的檢查次數(shù)也同樣重要, 成為影響STRN3算法效率的另一個(gè)重要因素, 時(shí)間效率與檢查次數(shù)成反比, 當(dāng)處理元組數(shù)與相鄰元組的檢查次數(shù)比值達(dá)到一定值時(shí), STRN3算法效率更高, 但無法得到邊界明確值.

[1] Freuder E C, Mackworth A K. Constraint Satisfaction: An Emerging Paradigm [J]. Handbook of Constraint Programming, 2006, 2: 13-27.

[2] Mackworth A K. Consistency in Networks of Relations [J]. Artificial Intelligence, 1977, 8(1): 99-118.

[3] Lecoutre C, Szymanek R. Generalized Arc Consistency for Positive Table Constraints [C]//Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming. Berlin: Springer, 2006: 284-298.

[4] Lecoutre C, Szymanek R. Generalized Arc Consistency for Positive Table Constraints [C]//Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming. Berlin: Springer-Verlag, 2006: 284-298.

[5] Lecoutre C, Likitvivatanavong C, Yap R H C. STR3: A Path-Optimal Filtering Algorithm for Table Constraints [J]. Artificial Intelligence, 2015, 220: 1-27.

[6] Lecoutre C. STR2: Optimized Simple Tabular Reduction for Table Constraints [J]. Constraints, 2011, 16(4): 341-371.

[7] LI Hongbo, LIANG Yanchun, GUO Jinsong, et al. Making Simple Tabular Reductionworks on Negative Table Constraints [C]//Twenty-Seventh AAAI Conference on Artificial Intelligence. Washington, DC: AAAI Press, 2013: 1629-1630.

[8] Lecoutre C. Constraint Networks: Techniques and Algorithms [M]. Piscataway, NJ: IEEE Press, 2009.

[9] Lecoutre C, Likitvivatanavong C, Yap R H C. A Path-Optimal GAC Algorithm for Table Constraints [C]//Proceedings of the 20th European Conference on Artificial Intelligence. Amsterdam: IOS Press, 2012: 510-515.

[10] Boussemart F, Hemery F, Lecoutre C, et al. Boosting Systematic Search by Weighting Constraints [C]//Proceedings of the 16th European Conference on Artificial Intelligence. Amsterdam: IOS Press, 2004: 146-150.