自適應(yīng)表壓縮方法優(yōu)化STR算法*

李少興，李占山，于海鴻

(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林長春130012)

1 引言

約束編程 CP(Constraint Programming)［1］是人工智能領(lǐng)域求解組合問題的重要范式，近年來在CP領(lǐng)域表約束過濾算法受到廣泛關(guān)注。表約束通過明確列出所有允許的或禁止的元組外延式地定義約束，在許多應(yīng)用領(lǐng)域(如配置和數(shù)據(jù)庫)中本身就存在表約束，此外表約束可以被視為用于表示任何約束的通用機(jī)制，表約束的重要性使得它們?cè)谥髁鞯那蠼馄髦卸嫉玫綄?shí)現(xiàn)(例如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］。該領(lǐng)域最近的一個(gè)重大改進(jìn)是在表約束中使用比特向量［8］來表示元組的有效性，在為變量值尋找支持時(shí)使用高效的比特向量并行操作。算法 STRbit［9］和 Compact-Table［10］都是結(jié)合了STR和比特向量操作的優(yōu)點(diǎn)，比過去十年中開發(fā)的最佳GAC算法快一個(gè)數(shù)量級(jí)，是目前最先進(jìn)的表約束算法。

表約束有一個(gè)主要的缺點(diǎn):存儲(chǔ)它們所需的內(nèi)存空間可能會(huì)隨著約束元數(shù)的增長呈指數(shù)增長，為了解決表約束求解面臨的內(nèi)存空間爆炸問題，近年來約束領(lǐng)域相繼提出各種表壓縮方法。當(dāng)表約束規(guī)模很大時(shí)，恰當(dāng)?shù)谋韷嚎s方法不僅能極大地節(jié)省空間消耗，同時(shí)也可以極大地提高GAC算法運(yùn)行速度。本文研究表約束中兩種主要的表壓縮方法:

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

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

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

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

2 背景知識(shí)

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

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

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

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

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

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

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

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

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

3 自適應(yīng)表壓縮算法

3．1 STR2-Adaptive算法

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

Sval:Sval保存上一次調(diào)用STR2時(shí)論域發(fā)生改變的變量集合，用來檢查一個(gè)元組的有效性，本文只需要檢查Sval中變量的文字即可，其他變量的文字都是有效的，因?yàn)樽兞空撚驔]有變化。

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

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

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

c-table:使用MDD圖來抽取c-tuple構(gòu)建笛卡爾乘積表示得到的壓縮表，在使用笛卡爾乘積表示壓縮方法為變量尋找支持時(shí)調(diào)用，同樣也計(jì)算出對(duì)應(yīng)的壓縮率ratio(c-table)。

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

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

算法1 自適應(yīng)表壓縮算法STR2-Adaptive

輸入:約束網(wǎng)絡(luò)中的一條約束c。

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

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

步驟2計(jì)算兩種表壓縮方法壓縮率;

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

步驟4在檢查元組有效性時(shí)，比較短支持和笛卡爾乘積表示方法壓縮率，選擇調(diào)用壓縮率較大者對(duì)應(yīng)的表壓縮算法進(jìn)行元組有效性檢查，更新Ssup并刪去無效元組;

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

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

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

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

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

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

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

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

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

笛卡爾乘積表壓縮算法CSTR2對(duì)采用笛卡爾乘積表示的c-table進(jìn)行元組有效性檢查，在檢查元組有效性時(shí)需對(duì)元組中變量包含的多個(gè)值重復(fù)檢查，數(shù)據(jù)結(jié)構(gòu)checkVal用于記錄c-tuple中每個(gè)變量可能包含的多個(gè)值。

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

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

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

步驟1對(duì)表中每個(gè)元組循環(huán)檢查，由于笛卡爾乘積表示的壓縮表對(duì)應(yīng)的元組稱為c-tuple，每個(gè)c-tuple中變量可以包含多個(gè)值，用checkVal數(shù)組來記錄c-tuple變量多個(gè)值的索引;

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

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

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

3．2 STR2-Adaptive算法時(shí)間復(fù)雜度

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

證明算法STR2-Adaptive的時(shí)間開銷主要分為三個(gè)階段:第一階段是算法1對(duì)Ssup和Sval的初始化，時(shí)間復(fù)雜度為O(r);第二階段是檢查元組有效性并更新Ssup，對(duì)應(yīng)算法2或算法3中的循環(huán)，時(shí)間復(fù)雜度分別為O(Ls)或O(Lcd)，二者選其一;最后階段對(duì)應(yīng)算法1更新Ssup中變量的論域，時(shí)間復(fù)雜度為O(rd)。因此，STR2-Adaptive最壞時(shí)間復(fù)雜度為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算法對(duì)約束表中每個(gè)文字的支持采用比特向量編碼，由于在比特向量上允許高效的并行運(yùn)算，處理器處理一個(gè)word(假設(shè)是64比特的word)的時(shí)間復(fù)雜度為O(1)，這可以極大提高STR算法的效率。實(shí)驗(yàn)表明，結(jié)合高效的比特向量并行操作的STRbit算法是目前最先進(jìn)的表約束算法之一。bit table仍然可以采用兩種表壓縮方法壓縮得到對(duì)應(yīng)的bit c-table和bit short-table。本文用自適應(yīng)表壓縮方法擴(kuò)展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分別是比特向量編碼的笛卡爾乘積表示壓縮表和短支持壓縮表。每個(gè)文字(x，a)在比特向量中第i位為1表示該文字在第i個(gè)元組上有支持，為0則表示沒有支持。顯然bit c-table和bit short-table需要的比特?cái)?shù)量要少于bit table，可見兩種表壓縮方法在STRbit上仍然適用，STRbit-Adaptive算法比較兩種表壓縮方法的壓縮率來自適應(yīng)選擇優(yōu)化效果更好的表壓縮方法。算法STRbit-Adaptive改進(jìn)STRbit的主要思想與STR2-Adaptive改進(jìn)STR2的類似，區(qū)別是STRbit-Adaptive在比特向量表示的數(shù)據(jù)結(jié)構(gòu) BIT_SUP(C，X，a)［9］上對(duì)變量尋找支持。

Figure 2 Corresponding bit vector representation of the three constraint tables圖2 三種約束表對(duì)應(yīng)的比特向量表

4 自適應(yīng)表壓縮算法在配置中的應(yīng)用

汽車配置問題通?？梢灾庇^地表示為一個(gè)表約束問題。表1中給出了一個(gè)關(guān)于環(huán)保汽車的簡單配置問題:約束1是對(duì)不同類型汽車使用的發(fā)動(dòng)機(jī)及其排放標(biāo)準(zhǔn)的限制，約束2是對(duì)于不同類型發(fā)動(dòng)機(jī)及其排放標(biāo)準(zhǔn)的汽車，限制是否需要安裝車載診斷系統(tǒng)OBD(On Board Diagnostics)。表1中列出了所有允許的組合。

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

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

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

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

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

本文在 Abscon求解器［17］上對(duì)算法 STR2-A-daptive與算法 STR2、shortSTR2、STR2-C進(jìn)行比較評(píng)估，然后評(píng)估了算法 STRbit-Adaptive與算法STRbit、shortSTRbit、STRbit-C 的運(yùn)行時(shí)間。實(shí)驗(yàn)環(huán)境是在 Intel(R)Core(TM)i7處理器，8．00 GB RAM，64位Windows操作系統(tǒng)下進(jìn)行的。所有算法都采用維持弧相容算法MAC(Maintaining Arc Consistency)，在搜索過程中維持GAC，變量啟發(fā)式均為dom/ddeg，變量值啟發(fā)式均為lexico。每個(gè)測(cè)試用例的超時(shí)設(shè)定為600 s。本文的經(jīng)典測(cè)試用例主要來自 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實(shí)例。

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

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

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

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

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

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

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

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

6 結(jié)束語

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