基于減少檢索的負表約束優化算法

杜江珊, 李占山

(吉林大學 計算機科學與技術學院, 符號計算與知識工程教育部重點實驗室, 長春 130012)

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

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

1 預備知識

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

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

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

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

表1 稀疏集示例

2 STRN3算法設計

2.1 定 義

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

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

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

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

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

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

2.2 算法思想

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

1) 上次傳播最小支持區間為(-1,p). 從該子表索引p處(table(C,X,a)[p]), 向升序方向尋找有效元組, 設第一個有效元組為索引p1處的元組t1, 將該元組與當前最小有效元組進行比較, 若不相等, 則找到最小支持區間, 區間為(-1,p1); 若相等, 則未找到最小支持區間, 繼續向升序方向尋找下一個有效元組, 設該元組為索引p2處的元組t2, 判斷t2與t1是否為相鄰元組, 若不等, 則找到最小支持區間, 區間為(p1,p2)； 若相等, 則繼續尋找, 直到找到索引pn處的有效元組tn, 且與上一有效元組不為相鄰元組, 此時最小支持區間為(pn-1,pn).

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

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

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

以上4種情形均為向升序方向尋找到有效元組的情形, 若最終找不到有效元組, 則按以下兩種情形處理：

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

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

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

3 實驗結果與分析

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

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

表2 STRN3算法與STR-N算法對比結果

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

表3為STRN3算法與STR3算法的平均對比結果, 其中對于每個實例, 負表約束中的元組數均小于其轉化為正表約束的元組數, 因此, STRN3算法比STR3算法處理元組數少, 效率更高. 表4為STRN3算法與STR-N算法最優對比結果. 表4中每行的問題實例不再是問題系列, 而是一個具體的實例, 且所有實例都是STRN3算法較STR-N算法更優, 優化效果約為5倍, 其中large-96-unsat_ext優化效果最高.

表3 STRN3算法與STR3算法對比結果

表4 STRN3算法與STR-N算法最優對比結果

綜上所述, 本文基于STR3算法, 通過放棄遍歷不相關元組的方法, 優化了STR-N算法, 提出了STRN3算法, 該算法的最大優點為快速地尋找值支持的方式, 并且STRN3算法放棄了STR3算法中的dep數據結構, 成為一種近似路徑最優算法. 由實驗結果可得如下結論：

1) 當實例中支持元組數多于不支持元組數時, STRN3算法相對STR3算法效率更高；

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

3) 元組的處理數量為影響STRN3算法效率的第一因子, 此外, 相鄰元組的檢查次數也同樣重要, 成為影響STRN3算法效率的另一個重要因素, 時間效率與檢查次數成反比, 當處理元組數與相鄰元組的檢查次數比值達到一定值時, 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.