自適應表壓縮方法優化STR算法*

李少興，李占山，于海鴻

(吉林大學計算機科學與技術學院，吉林長春130012)

1 引言

約束編程 CP(Constraint Programming)［1］是人工智能領域求解組合問題的重要范式，近年來在CP領域表約束過濾算法受到廣泛關注。表約束通過明確列出所有允許的或禁止的元組外延式地定義約束，在許多應用領域(如配置和數據庫)中本身就存在表約束，此外表約束可以被視為用于表示任何約束的通用機制，表約束的重要性使得它們在主流的求解器中都得到實現(例如Abscon、Choco、GeCode、JaCoP、OR-Tools)。用于非二元表約束主流的廣義弧相容GAC(Generalized Arc Consistency)算法包括簡單表縮減STR(Simple Tabular Reduction)算法［2］:STR2［3］、STR3［4］和 STRN［5］;以及多值決策圖MDD(Multi-valued Decision Diagram)算法:MDDc［6］和 MDD4［7］。該領域最近的一個重大改進是在表約束中使用比特向量［8］來表示元組的有效性，在為變量值尋找支持時使用高效的比特向量并行操作。算法 STRbit［9］和 Compact-Table［10］都是結合了STR和比特向量操作的優點，比過去十年中開發的最佳GAC算法快一個數量級，是目前最先進的表約束算法。

表約束有一個主要的缺點:存儲它們所需的內存空間可能會隨著約束元數的增長呈指數增長，為了解決表約束求解面臨的內存空間爆炸問題，近年來約束領域相繼提出各種表壓縮方法。當表約束規模很大時，恰當的表壓縮方法不僅能極大地節省空間消耗，同時也可以極大地提高GAC算法運行速度。本文研究表約束中兩種主要的表壓縮方法:

(1)笛卡爾乘積表示(c-tuple):約束表可以用笛卡爾乘積表示進行壓縮，這種壓縮方法最早應用在對稱破除和 nogood學習中［11，12］。2007 年 Katsirelos等人［13］使用元組的笛卡爾乘積表示來壓縮表約束，稱其為c-tuple，用于改進GAC-Schema算法。2013年 Xia等人［14］使用該壓縮方法擴展STR2和STR3算法得到STR2-C和STR3-C算法，實驗結果表明在壓縮率足夠大的情況下可以有效地加速原算法。

(2)短支持(short support):短支持允許元組中存在由符號*表示的通用值，這意味著一些變量可以取論域中任意值。假如本文有一個約束，變量范圍是{x，y，z}，它的一個短支持 S=(x→2，z→1)對應的全長度元組表示為S={2，*，1}。2013年Jefferson等人［15］用短支持擴展STR2算法，提出了shortSTR2算法。實驗結果表明，當表約束適合于短支持時，shortSTR2可以產生顯著的效率提升。

本文在實現STR2-C和shortSTR2算法時，發現兩種表壓縮算法在各類問題實例上的效率差別很大。經過分析發現，影響兩種表壓縮算法效率的主要因素是兩種表壓縮算法在同一實例上的壓縮率有差異，本文用原表中文字總和與壓縮表中文字總和之比作為壓縮率(一個文字就是一個變量值對)。笛卡爾乘積表示通常都能有效地壓縮原始表，甚至可以達到指數級別的壓縮。但是，采用笛卡爾乘積表示的STR2-C算法有一個缺點:STR2動態維持的有效元組中的每個值都是GAC一致的，STR2-C動態維持的是有效的c-tuple，而c-tuple中可能存在GAC不一致的值，這將使得c-tuple中一些值需要重新檢查，可能會使STR2-C與STR2相比更慢。shortSTR2算法壓縮原始表中滿足短支持的元組集后得到等價的短支持集，當約束適合短支持時，短支持集可以比整個元組集小指數級。但是，由于滿足短支持的條件過于苛刻，在大多數問題實例上的壓縮率都很小。

本文提出了一種自適應表壓縮方法，通過比較笛卡爾乘積表示和短支持的壓縮率，在相同問題實例上自適應地選擇較好的表壓縮方法。STR2-A-daptive是基于STR2算法的自適應表壓縮算法:首先計算笛卡爾乘積表示和短支持在同一問題實例上的壓縮率，由于笛卡爾乘積表示動態維持的ctuple需要額外的重復檢查，因此本文對笛卡爾乘積表示的壓縮率設置一個閾值δ，通過對比實驗發現，當笛卡爾科乘積壓縮率大于1．5時，采用笛卡爾乘積表示方法算法效率開始優于原算法，因此本文實驗中設置閾值為0．5。將笛卡爾乘積表示的壓縮率減去閾值δ，再與短支持壓縮率比較，自適應選擇壓縮率較大的表壓縮方法。STR2-Adaptive算法可以覆蓋兩種表壓縮方法的優勢且額外時間開銷很小。將自適應表壓縮算法應用到汽車配置問題，表明自適應表壓縮方法可以極大地提高求解表約束問題的效率。最后通過大量實驗表明，在絕大部分問題實例上，STR2-Adaptive算法都比STR2算法更快，在壓縮率足夠大時可以快1個數量級。進一步，本文將自適應表壓縮方法擴展到元組集使用比特向量表示的STRbit算法上，提出相應的STRbit-Adaptive算法。實驗結果表明，STRbit-A-daptive算法同樣可以加速最新的STRbit算法。

2 背景知識

一個約束滿足問題CSP(Constraint Satisfaction Problem)是一個三元組(X，D，C)，其中 X是變量集合，D是變量論域的集合，C則是約束組成的集合。給定變量x∈X和變量x的一個值a∈D(x)，D(x)為變量x的論域，稱變量值對(x，a)為一個文字，在搜索期間使用dom(x)表示變量x的當前論域，如果a∈dom(x)則文字(x，a)是有效的，否則文字(x，a)是無效的。每個約束c∈C是變量集合X的一個子集上的關系，由約束范圍scp(c)和關系rel(c)兩部分組成，scp(c)是約束包含的變量集合，|scp(c)|表示約束的元數，rel(c)是滿足約束c的元組集合，一個元組τ∈rel(c)是由scp(c)上變量的一組文字組成，關系rel(c)上的文字總和記作L。約束滿足問題的一個解是所有變量上的一組完全賦值，使得所有約束得到滿足。

一個元組τ∈rel(c)是文字(x，a)的支持當且僅當(x，a)∈τ，元組τ是有效的當且僅當x∈scp(c)，(x，a)都是有效的。一個文字(x，a)是廣義弧相容(GAC)的當且僅當在約束c上存在(x，a)的一個有效支持元組。一個變量x∈X是GAC的當且僅當對每個值a∈D(x)，都有(x，a)是GAC的。一個約束c∈C是GAC的當且僅當對每個變量x∈scp(c)都是GAC的。一個CSP是GAC的當且僅當每個約束都是GAC的。

定義 1(c-tuple［12］) 對一個 r 元約束 c(x1，…，xr)，它的元組采用笛卡爾乘積表示({a1，1，…，a1，k1}，…，{ar，1，…，ar，kr})稱為 c-tuple。一個 c-tuple允許一個變量有多個賦值，一個c-tuple τc是有效的當且僅當x∈scp(c)，存在一個文字(x，a)∈τc是有效的。

約束c的一個全長度支持是scp(c)中的所有變量進行賦值的一組文字，以便約束c被這些文字表示的賦值所滿足。Nightingale等人［16］提出了短支持。

定義2(短支持(short support)) 約束c的一個短支持S是一組文字集合(x→v)，其中x∈scp(c)，x→v指變量x取值為v，x在S中僅出現一次，且S的每一個超集在scp(c)中的每個變量包含一個有效的文字是一個全長度支持。

在本文中采用全長度元組表示短支持，用符號*表示一個不被短支持包含的變量。假設有一個約束 c涉及三個變量(x，y，z)，短支持 S=(x→2，z→1)，那么S用全長度元組表示為(2，*，1)，符號*表示變量y不在其中。本文采用 Jefferson等人［15］提出的貪婪壓縮算法 Greedy Compress，將給定全長度支持(r個變量)的元組集一步一步壓縮為r－1個變量的短支持表示，r－2個變量的短支持表示，直到不能壓縮為止。

定義3(壓縮率) 本文用原始約束表的文字總和L與壓縮表的文字總和L'之比L/L'作為表壓縮方法的壓縮率，L/L'能夠準確地表示內存空間的縮減。

圖1a給出一個簡單原始約束表，假設變量集合為(x，y，z)，每個變量的論域相同，論域值均為(m，n，p)，文字總和L=24。圖1b是通過笛卡爾乘積表示法的壓縮表c-table，文字總和Lc=10，對應壓縮率L/Lc=2．4。圖1c則是通過短支持壓縮算法得到的壓縮表short-table，文字總和Ls=10(其中*表示變量不被短支持包含)，對應壓縮率L/Ls=2．4。

Figure 1 Original table and two compressed tables圖1 原始約束表和兩種壓縮表

3 自適應表壓縮算法

3．1 STR2-Adaptive算法

STR2-Adaptive算法主要思想是基于STR2算法框架自適應地選擇壓縮率大的表壓縮方法，STR2-Adaptive在各類問題實例上不僅能最大化地節省表約束內存空間，還能加快原算法的運行速度。首先，使用笛卡爾乘積表示和短支持方法將原始約束表分別壓縮為c-table和short-table;然后計算兩種表壓縮方法的壓縮率，由于笛卡爾乘積表示動態維持的c-tuple需要額外的重復檢查，STR2-A-daptive算法引入了一個閾值δ，將笛卡爾乘積表示的壓縮率減去閾值δ，再與短支持壓縮率進行比較，STR2-Adaptive算法選擇壓縮率較大者對應的表壓縮算法。STR2-Adaptive算法沿用STR2框架，采用如下數據結構:

Sval:Sval保存上一次調用STR2時論域發生改變的變量集合，用來檢查一個元組的有效性，本文只需要檢查Sval中變量的文字即可，其他變量的文字都是有效的，因為變量論域沒有變化。

Ssup:Ssup初始保存搜索過程中尚未賦值的變量集合，隨著STR2算法不斷推進，gacValues［x］保存變量x中滿足GAC的值的集合，如果gacValues［x］=D(x)，則可以將x從Ssup中刪去。為元組更新gacValues［x］時不必更新不屬于Ssup的變量x對應的gacValues［x］。最后只需要對Ssup中的變量論域進行更新。

lastSize:用來保存每個變量被特定約束c處理后論域的大小。

short-table:用 Jefferson等人提出的 Greedy-Compress算法壓縮原表后得到的壓縮表，并在使用短支持壓縮方法時為變量尋找支持時調用，同時計算出短支持方法的壓縮率ratio(short-table)。

c-table:使用MDD圖來抽取c-tuple構建笛卡爾乘積表示得到的壓縮表，在使用笛卡爾乘積表示壓縮方法為變量尋找支持時調用，同樣也計算出對應的壓縮率ratio(c-table)。

checkVal:用于記錄c-tuple中每個變量可能包含的多個值的索引數組。

算法STR2-Adaptive基于STR2算法框架，先對表約束分別采用兩種壓縮方法進行壓縮得到壓縮后的short-table和c-table，計算壓縮率，并調用壓縮率大的對應表壓縮算法進行元組有效性檢查，最后更新尚未賦值的變量論域，具體過程如算法1所示。

算法1 自適應表壓縮算法STR2-Adaptive

輸入:約束網絡中的一條約束c。

輸出:約束c中論域發生變化的變量集合。

步驟1初始化階段，采用已有的算法GreedyCompress和MDD圖分別將表約束c壓縮，得到對應的short-table和c-table;

步驟2計算兩種表壓縮方法壓縮率;

步驟3Sval初始保存最近賦值變量和尚未賦值變量論域發生改變的變量集合，Ssup初始保存尚未賦值的變量集合;

步驟4在檢查元組有效性時，比較短支持和笛卡爾乘積表示方法壓縮率，選擇調用壓縮率較大者對應的表壓縮算法進行元組有效性檢查，更新Ssup并刪去無效元組;

步驟5更新Ssup中變量的論域，用gacValues［x］作為變量新的論域，如果更新后的論域為空，則約束不一致，否則更新lastSize，返回論域發生改變的變量集合Xevt。

短支持表壓縮算法shortSTR2對采用短支持壓縮后的short-table進行元組有效性檢查，對原表可以達到指數級別的壓縮，對符號*表示的變量有效性檢查的時間復雜度為O(1)。

算法2短支持表壓縮算法shortSTR2

輸入:短支持壓縮表short-table和Sval。

輸出:需要更新的變量集合Ssup。

步驟1對表中每個元組循環檢查，檢查Sval中每個變量值，如果τ［x］≠ ＊或τ［x］dom(x)，則τ是無效元組，從表中刪去該元組，τ［x］表示元組τ中變量x的取值;

步驟2Sval初始保存最近賦值變量和尚未賦值變量論域發生改變的變量集合，Ssup初始保存尚未賦值的變量集合;

步驟3若τ是有效元組，當τ［x］=*或|gacValues［x］|=|dom(x)|時，表示變量x的所有可能值都能找到支持;

步驟4更新Ssup中變量的論域，將x從Ssup中刪去。

笛卡爾乘積表壓縮算法CSTR2對采用笛卡爾乘積表示的c-table進行元組有效性檢查，在檢查元組有效性時需對元組中變量包含的多個值重復檢查，數據結構checkVal用于記錄c-tuple中每個變量可能包含的多個值。

算法3笛卡爾乘積表示壓縮算法CSTR2

輸入:笛卡爾乘積表示壓縮表的c-table和Sval。

輸出:需要更新的變量集合Ssup。

步驟1對表中每個元組循環檢查，由于笛卡爾乘積表示的壓縮表對應的元組稱為c-tuple，每個c-tuple中變量可以包含多個值，用checkVal數組來記錄c-tuple變量多個值的索引;

步驟2檢查Sval中每個變量，如果元組中變量每個值checkVal［v］都不在該變量論域dom(x)中，則該元組是無效元組，從表中直接刪去;

步驟3該元組是有效元組，更新Ssup中變量對應的gacValues［x］，如果|gacValues［x］|=|dom(x)|，則表示變量x的所有值都能找到支持;

步驟4更新Ssup中變量的論域，將x從Ssup中刪去。

3．2 STR2-Adaptive算法時間復雜度

定理1對于一個r元約束，變量最大論域為d，用Ls表示短支持壓縮表中文字總和，用Lc表示笛卡爾乘積表示壓縮表中文字總和，STR2-Adaptive的最壞時間復雜度為Max(O(rd+Ls，rd+Lcd))。

證明算法STR2-Adaptive的時間開銷主要分為三個階段:第一階段是算法1對Ssup和Sval的初始化，時間復雜度為O(r);第二階段是檢查元組有效性并更新Ssup，對應算法2或算法3中的循環，時間復雜度分別為O(Ls)或O(Lcd)，二者選其一;最后階段對應算法1更新Ssup中變量的論域，時間復雜度為O(rd)。因此，STR2-Adaptive最壞時間復雜度為Max(O(rd+Ls，rd+Lcd))。證畢。

3．3 STRbit-Adaptive算法

2016年Wang等人［9］提出了新的表約束形式:bit table和bit c-table，然后基于bit table和 bit c-table分別提出了STRbit和STRbit-C算法。STRbit算法對約束表中每個文字的支持采用比特向量編碼，由于在比特向量上允許高效的并行運算，處理器處理一個word(假設是64比特的word)的時間復雜度為O(1)，這可以極大提高STR算法的效率。實驗表明，結合高效的比特向量并行操作的STRbit算法是目前最先進的表約束算法之一。bit table仍然可以采用兩種表壓縮方法壓縮得到對應的bit c-table和bit short-table。本文用自適應表壓縮方法擴展STRbit算法，提出了STRbit-Adaptive算法。STRbit-Adaptive算法的主要思想和STR2-Adaptive的類似，通過比較bit c-table和bit short-table的壓縮率，選擇壓縮率大的表壓縮方法。

圖2a是圖1a原始約束表用比特向量編碼的bit table，圖2b bit c-table和圖2c bit short-table分別是比特向量編碼的笛卡爾乘積表示壓縮表和短支持壓縮表。每個文字(x，a)在比特向量中第i位為1表示該文字在第i個元組上有支持，為0則表示沒有支持。顯然bit c-table和bit short-table需要的比特數量要少于bit table，可見兩種表壓縮方法在STRbit上仍然適用，STRbit-Adaptive算法比較兩種表壓縮方法的壓縮率來自適應選擇優化效果更好的表壓縮方法。算法STRbit-Adaptive改進STRbit的主要思想與STR2-Adaptive改進STR2的類似，區別是STRbit-Adaptive在比特向量表示的數據結構 BIT_SUP(C，X，a)［9］上對變量尋找支持。

Figure 2 Corresponding bit vector representation of the three constraint tables圖2 三種約束表對應的比特向量表

4 自適應表壓縮算法在配置中的應用

汽車配置問題通?？梢灾庇^地表示為一個表約束問題。表1中給出了一個關于環保汽車的簡單配置問題:約束1是對不同類型汽車使用的發動機及其排放標準的限制，約束2是對于不同類型發動機及其排放標準的汽車，限制是否需要安裝車載診斷系統OBD(On Board Diagnostics)。表1中列出了所有允許的組合。

Table 1 An instance of car configuration表1 簡單的汽車配置問題

表1中約束1的文字總數為L1=18，約束2的文字總和為L2=18。對約束1和約束2進行笛卡爾乘積表示得到表2所示的壓縮表，表約束的空間規模都小，約束1的文字總和為L1c=12，約束2的文字總和為L2c=14。對約束1和約束2進行短支持表示得到表3所示的壓縮表，短支持用符合*表示該變量可取論域的任意值，不被短支持所包含，表3中約束1的文字總數為L1s=14，約束2的文字總數L2s=10。STR算法在進行元組有效性檢查時，需要檢查每個變量值是否是GAC支持的，該操作的次數即為表約束的文字總數，因此縮減表約束的文字總和不僅可以極大地節省內存空間，還能極大地提高STR算法時間效率?？v向比較，我們發現兩種壓縮表的壓縮效果有明顯差異，笛卡爾乘積表示在約束1上壓縮效果優于短支持表示(L1c＜L1s)，短支持表示在約束2上壓縮效果優于笛卡爾乘積表示(L2c＞L2s)。自適應表壓縮方法則可以通過比較兩種表壓縮方法的壓縮率，自適應地選擇較好的表壓縮方法。在實際問題中表約束規模遠大于上述實例，當元組間存在較多交疊時，可以達到指數級別的壓縮效果，自適應表壓縮方法可以極大地提高求解表約束問題的效率。

Table 2 Equivalent compressed table of Cartesian product representation表2 笛卡爾乘積表示的壓縮表

Table 3 Equivalent compressed table of short support表3 短支持表示的壓縮表

5 實驗結果與分析

本文在 Abscon求解器［17］上對算法 STR2-A-daptive與算法 STR2、shortSTR2、STR2-C進行比較評估，然后評估了算法 STRbit-Adaptive與算法STRbit、shortSTRbit、STRbit-C 的運行時間。實驗環境是在 Intel(R)Core(TM)i7處理器，8．00 GB RAM，64位Windows操作系統下進行的。所有算法都采用維持弧相容算法MAC(Maintaining Arc Consistency)，在搜索過程中維持GAC，變量啟發式均為dom/ddeg，變量值啟發式均為lexico。每個測試用例的超時設定為600 s。本文的經典測試用例主要來自 http://www．cril．univ-artois．fr/～ lecoutre/benchmarks．html，而 MDD0．7、MDD0．9、rand-5-2x、rand-5-4x和rand-5-8X-0．5是STR2-C 算法［12］中介紹的benchmark實例。

表4中給出了大量benchmark實例中的運行結果，本文不考慮那些在每個算法上都超時的實例。表4中#是每類問題包含的實例數量，L/Ls、L/Lc分別是短支持和笛卡爾乘積表示的壓縮率，本實驗假定算法STR2-C壓縮率的閾值δ為0．5。然后給出每個系列實例在算法 STR2、shortSTR2、STR2-C、STR2-Adaptive上的平均運行時間，單位為s，粗體表示該算法運行時間最短。ratio是在一類問題上算法STR2-Adaptive與最快算法的運行時間的比值。Sum of average CPU times per class代表各類問題耗時均值的和。

表4所示實驗結果表明，整體上看短支持和笛卡爾乘積表示兩種表壓縮算法在同一類實例上的壓縮率有明顯差異，壓縮率大的算法運行時間相對較短。短支持在一些實例上的壓縮率L/Ls接近1．00，對應的shortSTR2算法由于額外的短支持檢查，運行時間會略高于STR2，而在bdd、aim、jnh等一些實例上短支持比笛卡爾乘積表示壓縮率要大，相應地運行時間是最短的。笛卡爾乘積表示方法在絕大多數問題上都有較好的壓縮效果，但由于STR2-C算法需要額外的重復檢查開銷，在壓縮率L/Lc＜1．5時(如 bdd系列實例)，STR2-C 算法運行時間反而大于STR2算法，因此本文設置笛卡爾乘積表示閾值δ為0．5。

本文提出的算法STR2-Adaptive可以在絕大多數實例上自適應選擇最佳的表壓縮算法，這需要的額外時間開銷僅占最短時間算法總時間1%左右。STR2-Adaptive算法在絕大多數實例上的運行時間都優于STR2算法，尤其在壓縮率較大的實例如MDD0．9上效率提高顯著。對比算法shortSTR2和STR2-C可以看出，shortSTR2在很多問題上壓縮率接近1．00，而STR2-C則在另一些實例上壓縮率不如shortSTR2，且在壓縮率較低時發生退化。STR2-Adaptive可以覆蓋兩者的優勢，彌補兩者的短板，在不同問題上用最大化壓縮表約束空間來加速STR2算法。由表4中最后一行可以看出，STR2-Adaptive算法在所有問題上總的平均時間之和是最小的，大約是STR2算法總的運行時間的一半，相比STR2-C算法和shortSTR2算法，總的運行時間也有明顯的減少。

Table 4 Mean runtime of STR2，shortSTR2，STR2-C and STR2-Adaptive on different series of instances表4 STR2，shortSTR2，STR2-C和STR2-Adaptive在不同系列實例上的平均運行時

本文用散點圖更加直觀地比較算法STR2-A-daptive和 STR2、shortSTR2、STR2-C，如圖 3 所示。圖中的每個點都代表一個具體的實例，橫縱坐標軸對應兩種算法的運行時間，單位為 s。圖3a是STR2-Adaptive和STR2時間對比，絕大部分的點位于正對角線右下方，即算法STR2-Adaptive運行時間相對更短，優化效果在一些實例可以達到指數級別。圖3b是STR2-Adaptive與shortSTR2的時間對比，大部分實例在正對角線偏下方，STR2-Adaptive在這些實例上運行時間優于shortSTR2。這是由于這些實例的笛卡爾乘積表示的壓縮率大于短支持壓縮率，STR2-Adaptive會在這些實例上選擇笛卡爾乘積表壓縮算法，而在短支持壓縮率大于笛卡爾乘積壓縮率的實例上，STR2-Adaptive與shortSTR2運行時間相差不大。圖3c是 STR2-Adaptive與STR2-C的時間對比，與圖3b類似，STR2-Adaptive在問題實例的短支持壓縮率較大的情況下選擇短支持壓縮方法，在這些實例上STRbit-Adaptive較STR2-C耗時更少，由于笛卡爾乘積表示壓縮方法適應更多的問題實例，因此在圖3c的正對角線附近有較多的點，在這些實例上STR2-Adaptive算法與STR2-C算法運行時間接近。

表5所示為結合了比特向量操作的STRbit-A-daptive 算法與 STRbit、shortSTRbit、STRbit-C 算法的平均運行時間，單位為s，粗體表示該算法運行時間最短。ratio是在一類問題上STRbit-Adaptive算法與最快算法的運行時間的比值。Sum of average CPU times per class代表各類問題耗時均值的和。本文選取了一些問題規模較大的實例進行比較實驗。

Table 5 Mean runtime of STRbit and STRbit-Adaptive on different series of instances表5 STRbit和STRbit-Adaptive在不同系列實例上的平均運行時間

由表5可以看出，STRbit-Adaptive算法通過自適應選擇表壓縮方法仍能在絕大部分問題實例上改進目前公認性能最佳的STRbit算法，整體上看，問題的壓縮率越大，性能提升越明顯，如在rand-5-8X-0．5問題上加速達到4．40倍。對于那些壓縮率小的問題，STRbit-Adaptive算法也能一定程度地優化STRbit算法，只是在一些壓縮率為0的實例上(如lexVg)，有些許額外時間開銷。相比shortSTRbit、STRbit-C，STRbit-Adaptive 算法自適應選擇需要的額外時間開銷約占最佳的表壓縮算法運行時間的1%，但由最后一行可以看出，STRbit-Adaptive算法在各類問題耗時均值的總和是最小的。即總體來看STRbit-Adaptive算法是最好的。

6 結束語

簡單表縮減算法STR是表約束求解最常用的GAC算法，表壓縮方法可以在一定程度上解決約束編程中表約束求解面臨的內存空間爆炸問題。本文基于STR算法提出一種自適應表壓縮算法，通過比較同一問題上兩種最常用的表壓縮算法的壓縮率，自適應地選擇壓縮率大的表壓縮算法。本文基于算法STR2結合自適應表壓縮方法提出STR2-Adaptive算法，STR2-Adaptive可以覆蓋兩種表壓縮算法的優勢。實驗結果表明，STR2-Adaptive算法在絕大多數問題實例上相比STR2算法加速明顯，相比shortSTR2和STR2-C，STR2-Adaptive能自適應選擇運行時間較短的表壓縮算法，且只需要很小的額外時間開銷。然后，本文在結合了比特向量并行操作的STRbit算法上采用自適應表壓縮方法提出了對應的STRbit-Adaptive算法。實驗結果表明，STRbit-Adaptive算法同樣普遍優于最新的STRbit算法，在壓縮率較大的問題上效率提升明顯。對于負表約束同樣可以采取表壓縮方法優化，今后將把自適應表壓縮方法應用到負表約束表示的問題中。