趙秦怡，趙榆琴

（大理大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院，云南大理 671003）

回溯算法是常用的算法設(shè)計方法，其按照深度優(yōu)先的策略在搜索樹中進(jìn)行搜索，在搜索過程中發(fā)現(xiàn)當(dāng)前路徑不滿足問題的約束條件則進(jìn)行剪枝，退回上一步搜索下一條路徑，以避免無效搜索，提高算法性能。回溯算法可以求得問題的所有可行解，進(jìn)而根據(jù)目標(biāo)函數(shù)獲得最優(yōu)解，適用于求解組合數(shù)較大的問題，如排列問題、組合問題、子集問題等，由于搜索樹的結(jié)點(diǎn)數(shù)是指數(shù)階的，故回溯算法的時間代價在最壞情況下往往是指數(shù)階。

尚春劍等〔1〕對P-中心選址問題進(jìn)行研究，在縮小問題求解規(guī)模的基礎(chǔ)上設(shè)定搜索上界及下界，提高了回溯算法的時間性能。彭大江等〔2〕對k-CARD樹問題進(jìn)行研究，提出了帶搜索上界和下界可求最優(yōu)解的回溯算法。張學(xué)才等〔3〕提出了兩種啟發(fā)式的動態(tài)回溯算法求解大值域約束滿足問題，利用回溯機(jī)制修正變量值，算法具有顯著的優(yōu)越性。胡沁等〔4〕對組合優(yōu)化問題中的節(jié)點(diǎn)加權(quán)Steiner 樹問題進(jìn)行研究，提出了復(fù)雜度低且可求最優(yōu)解的回溯算法。尚春劍等〔5〕研究了組合優(yōu)化問題中有容量集合覆蓋選址問題，提出了根據(jù)約束條件進(jìn)行剪枝的高效回溯算法。

集合子集求解是常見的計算問題〔6-8〕，在很多問題求解中需要對集合子集進(jìn)行枚舉，如旅行商問題、關(guān)聯(lián)規(guī)則挖掘、模式挖掘等。給出了基于二叉樹的無剪枝子集求解回溯算法，并對常規(guī)的基于排列樹的子集求解回溯算法做了改進(jìn)，提出基于不定長子樹子集求解回溯算法。算法極大地減少了搜索樹中的結(jié)點(diǎn)，縮短了搜索路徑，使得在搜索過程中不帶約束條件、不需要剪枝，避免了常規(guī)回溯算法依據(jù)約束條件進(jìn)行的大量剪枝。在問題的求解規(guī)模較大時，基于不定長子樹的集合子集求解回溯算法效率更高。

1 二叉搜索樹定義及基于二叉樹的集合子集求解回溯算法

定義1 若將集合S 定義為

則將其子集Si定義為

1.1 二叉搜索樹集合子集求解回溯算法的搜索樹可采用子集樹或排列樹，本文提出的基于二叉樹的集合子集求解回溯算法中搜索樹采用了二叉樹結(jié)構(gòu)。其第0 層為根結(jié)點(diǎn)；第一層結(jié)點(diǎn)為子集對集合中項(xiàng)a1的選擇情況，其第一個結(jié)點(diǎn)為子集中不包含項(xiàng)a1，第二個結(jié)點(diǎn)為子集中包含項(xiàng)a1；第二層結(jié)點(diǎn)為子集對集合中項(xiàng)a2的選擇情況，第二層共有4 個結(jié)點(diǎn)；依此類推，第n 層為子集對集合中項(xiàng)an的選擇情況，由于子集樹中每一棵子樹都是二叉樹，故第n 層共有2n個葉子結(jié)點(diǎn)。將第一層結(jié)點(diǎn)的搜索子集記為S1，第二層結(jié)點(diǎn)的搜索子集記為S2，…，第n層結(jié)點(diǎn)搜索子集記為Sn，則有S1＝S2＝…＝Sn＝｛0，1｝，|S1|＝|S2|＝…＝|Sn|＝2，子集樹共有2n+1-1 個結(jié)點(diǎn)，其中有2n個葉子結(jié)點(diǎn)，每個葉子結(jié)點(diǎn)對應(yīng)一個可行解子集。

1.2 基于二叉樹的集合子集求解回溯算法算法按深度優(yōu)先搜索所有路徑，由子集樹的構(gòu)造及式（2）可知，子集樹中每一個葉子結(jié)點(diǎn)對應(yīng)一個可行解子集，搜索過程沒有約束條件，不需要剪枝。每搜索到一個葉子結(jié)點(diǎn)，生成對應(yīng)的可行解子集，然后進(jìn)行回溯，直到搜索完子集樹中所有路徑。

基于二叉樹的集合子集求解回溯算法如下：

2 不定長子樹搜索樹定義及基于不定長子樹的集合子集求解回溯算法

子集求解回溯算法的搜索樹若組織為排列樹，通常的求解方法中，排列樹同一層中結(jié)點(diǎn)的搜索范圍一樣，第0 層為樹根結(jié)點(diǎn)，將第一層中結(jié)點(diǎn)的搜索子集記為S1，第二層中結(jié)點(diǎn)的搜索子集記為S2，…，第n 層中結(jié)點(diǎn)的搜索子集記為Sn，由于搜索樹中每一層結(jié)點(diǎn)的子樹長度均相同，則有|S1|＝n，|S2|＝n-1，…，|Sn|＝1，排列樹中共有n!個葉子結(jié)點(diǎn)，需搜索n!條路徑。由式（2）可知在搜索樹中只有部分葉子結(jié)點(diǎn)對應(yīng)可行解，在搜索過程中需根據(jù)式（2）作為約束條件進(jìn)行大量剪枝，以避免無效搜索，算法的時間復(fù)雜度比較高，通常為O（n!）。通常的回溯算法在搜索可行解的過程中需進(jìn)行大量剪枝，算法復(fù)雜度較高，對回溯算法提出的改進(jìn)策略包括相容性技術(shù)、啟發(fā)式和回溯機(jī)制等。相容性技術(shù)是通過刪除一些一定不在解中的變量值來縮小搜索空間；啟發(fā)式是通過改變變量順序和取值順序來提高算法效率〔9〕；回溯機(jī)制是通過解決回溯搜索過程中遇到的矛盾來保證算法的完備性。

提出一個高效的基于不定長子樹作為搜索樹的集合子集求解回溯算法，算法利用相容性技術(shù)合理設(shè)置結(jié)點(diǎn)的搜索范圍，搜索過程中無需剪枝。

2.1 不定長子樹搜索樹不定長子樹搜索樹同一層中各結(jié)點(diǎn)的搜索范圍均不同，第0 層為樹根結(jié)點(diǎn)，第一層第一個結(jié)點(diǎn)的搜索范圍取集合中全n項(xiàng)，第一層第二個結(jié)點(diǎn)的搜索范圍取去除a1之后剩余的n-1 項(xiàng)，第一層第三個結(jié)點(diǎn)的搜索范圍取去除a1及a2之后剩余的n-2 項(xiàng)，第一層后續(xù)結(jié)點(diǎn)搜索范圍依次減少，第一層最后一個結(jié)點(diǎn)搜索范圍取最后一項(xiàng)。若將第一層中各結(jié)點(diǎn)的搜索子集記為S1.1，S1.2，…，S1.n，則有|S1.1|＝n，|S1.2|＝n-1，…，|S1.n|＝1，第二層第一個結(jié)點(diǎn)的搜索范圍比父結(jié)點(diǎn)的搜索范圍減少一項(xiàng)，后續(xù)結(jié)點(diǎn)搜索范圍依次減少一項(xiàng)，有|S1.1.1|＝n-1，|S1.1.2|＝n-2，…，|S1.1.n-1|＝1，同理，有|S1.2.1|＝n-2，|S1.2.2|＝n-3，…，|S1.2.n-2|＝1，依此類推，第一層最后一個結(jié)點(diǎn)無下層結(jié)點(diǎn)，即|S1.n.1|＝0。搜索樹中第一層最后一個結(jié)點(diǎn)為葉子結(jié)點(diǎn)，往下層依次類推，搜索樹中每一棵子樹最后一個結(jié)點(diǎn)均為葉子結(jié)點(diǎn)。n 個元素構(gòu)成的集合對應(yīng)的不定長子樹搜索樹中共有2n個結(jié)點(diǎn)，搜索樹中每一個結(jié)點(diǎn)對應(yīng)一個子集，不存在相同的子集，子集中均不含重復(fù)的元素。

例1 含4 個元素的集合｛a1，a2，a3，a4｝的不定長子樹搜索樹結(jié)構(gòu)如圖1 所示。

圖1 集合｛a1，a2，a3，a4｝的不定長子樹搜索樹

2.2 基于不定長子樹的集合子集求解回溯算法算法搜索過程按深度優(yōu)先進(jìn)行，由式（2）及不定長子樹搜索樹的結(jié)構(gòu)可知，每搜索到一個新結(jié)點(diǎn)可生成一個子集，搜索到葉子結(jié)點(diǎn)則回溯到上一步，繼續(xù)按深度優(yōu)先進(jìn)行搜索，直到搜索完所有結(jié)點(diǎn)，即得到所有的可行解子集。可行解中不存在相同的子集，子集中均不含重復(fù)的元素，且搜索過程中不需要剪枝。由以上不定長子樹搜索樹的結(jié)構(gòu)可知，改進(jìn)的不定長子樹搜索樹將結(jié)點(diǎn)數(shù)減到最少，搜索路徑縮到最短，搜索過程中不帶約束條件，極大地提高了搜索效率。

例2 例1 中的不定長子樹搜索樹按本算法進(jìn)行搜索得到的子集分別為：｛a1｝，｛a1，a2｝，｛a1，a2，a3｝，｛a1，a2，a3，a4｝，｛a1，a2，a4｝，｛a1，a3｝，｛a1，a3，a4｝，｛a1，a4｝，｛a2｝，｛a2，a3｝，｛a2，a3，a4｝，｛a2，a4｝，｛a3｝，｛a3，a4｝，｛a4｝。

在回溯算法中，問題的搜索樹是虛擬的，不需要在算法運(yùn)行時構(gòu)造一棵真正的樹結(jié)構(gòu)，通常的回溯算法需按某種順序依次考察笛卡爾積S1×S2×S3×…×Sn中的元素，并根據(jù)約束條件進(jìn)行剪枝。本算法中，由于采用了不定長子樹作為搜索樹，搜索樹中子樹的長度均不一致，即搜索樹中所有結(jié)點(diǎn)的搜索范圍均不一樣，故在搜索過程中需合理設(shè)定每一個結(jié)點(diǎn)的搜索范圍。當(dāng)前搜索結(jié)點(diǎn)有兩種情況：（1）按深度優(yōu)先從上層結(jié)點(diǎn)搜索到本條路徑中的下層結(jié)點(diǎn)；（2）從下層結(jié)點(diǎn)回溯到上層結(jié)點(diǎn)。搜索樹中一個結(jié)點(diǎn)對應(yīng)一個可行解子集，每搜索到一個新結(jié)點(diǎn)時生成一個子集，故需要在結(jié)點(diǎn)中標(biāo)記搜索路徑及當(dāng)前搜索項(xiàng)。算法中搜索樹結(jié)點(diǎn)數(shù)據(jù)描述為：

3 算法效率

通常的回溯算法搜索樹中結(jié)點(diǎn)和搜索路徑存在大量冗余，算法在最壞情況下的時間復(fù)雜度往往到O（n!），搜索過程中需要大量剪枝，算法效率低。本文中的兩個回溯算法采用了相容性技術(shù)，在搜索過程中不需要剪枝，算法在最好、最壞及平均情況下時間復(fù)雜度均一樣?；诙鏄涞募献蛹蠼饣厮菟惴ㄐ杷阉鳂渲忻恳粋€結(jié)點(diǎn)，搜索樹共有20+21+22+23+…+2n＝2n+1-1 個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)對應(yīng)可行解，算法時間復(fù)雜度為O（2n+1），n 為集合的長度?；诓欢ㄩL子樹的集合子集求解回溯算法也需搜索樹中每一個結(jié)點(diǎn)，每一結(jié)點(diǎn)對應(yīng)一個可行解子集，樹中共有2n個結(jié)點(diǎn)，算法時間復(fù)雜度為O（2n），n為集合的長度。

當(dāng)n 值較小的時候，由算法時間復(fù)雜度可知兩個算法效率區(qū)別不明顯，當(dāng)n 值較大時，兩個算法效率差別較大。表1 是兩個算法在不同集合長度下的運(yùn)行時間，圖2 是兩個算法運(yùn)行時間的差值在不同集合長度下的變化趨勢。當(dāng)n 值較小時，兩個算法運(yùn)行時間及變化趨勢區(qū)別不明顯，算法效率相當(dāng)。當(dāng)n 值較大，即集合長度超過14 項(xiàng)時，基于不定長子樹的集合子集求解回溯算法運(yùn)行時間變化趨勢緩慢，時間效率較好，算法更為有效。

表1 兩個算法在不同集合長度下的運(yùn)行時間

圖2 兩個算法運(yùn)行時間差值變化趨勢

4 結(jié)語

回溯算法設(shè)計技術(shù)適用于求解組合數(shù)較大的問題，提出基于二叉樹及不定長子樹作為問題搜索樹的集合子集求解回溯算法，算法可求解所有的可行解子集，由于算法設(shè)計采用了相容性技術(shù)，在深度優(yōu)先搜索過程中不需要按子集約束條件進(jìn)行剪枝，兩個算法的時間復(fù)雜度均比一般的回溯算法理想。算法時間復(fù)雜度及算法運(yùn)行效率表明，問題求解規(guī)模（集合長度）較大時，基于不定長子樹的集合子集求解回溯算法的時間效率明顯高于基于二叉樹的集合子集求解回溯算法。