基于二叉樹及不定長子樹的集合子集求解回溯算法

趙秦怡，趙榆琴

（大理大學數學與計算機學院，云南大理 671003）

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

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

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

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

定義1 若將集合S 定義為

則將其子集Si定義為

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

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

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

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

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

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

2.1 不定長子樹搜索樹不定長子樹搜索樹同一層中各結點的搜索范圍均不同，第0 層為樹根結點，第一層第一個結點的搜索范圍取集合中全n項，第一層第二個結點的搜索范圍取去除a1之后剩余的n-1 項，第一層第三個結點的搜索范圍取去除a1及a2之后剩余的n-2 項，第一層后續結點搜索范圍依次減少，第一層最后一個結點搜索范圍取最后一項。若將第一層中各結點的搜索子集記為S1.1，S1.2，…，S1.n，則有|S1.1|＝n，|S1.2|＝n-1，…，|S1.n|＝1，第二層第一個結點的搜索范圍比父結點的搜索范圍減少一項，后續結點搜索范圍依次減少一項，有|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，依此類推，第一層最后一個結點無下層結點，即|S1.n.1|＝0。搜索樹中第一層最后一個結點為葉子結點，往下層依次類推，搜索樹中每一棵子樹最后一個結點均為葉子結點。n 個元素構成的集合對應的不定長子樹搜索樹中共有2n個結點，搜索樹中每一個結點對應一個子集，不存在相同的子集，子集中均不含重復的元素。

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

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

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

例2 例1 中的不定長子樹搜索樹按本算法進行搜索得到的子集分別為：｛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｝。

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

3 算法效率

通常的回溯算法搜索樹中結點和搜索路徑存在大量冗余，算法在最壞情況下的時間復雜度往往到O（n!），搜索過程中需要大量剪枝，算法效率低。本文中的兩個回溯算法采用了相容性技術，在搜索過程中不需要剪枝，算法在最好、最壞及平均情況下時間復雜度均一樣。基于二叉樹的集合子集求解回溯算法需搜索樹中每一個結點，搜索樹共有20+21+22+23+…+2n＝2n+1-1 個結點，其中葉子結點對應可行解，算法時間復雜度為O（2n+1），n 為集合的長度。基于不定長子樹的集合子集求解回溯算法也需搜索樹中每一個結點，每一結點對應一個可行解子集，樹中共有2n個結點，算法時間復雜度為O（2n），n為集合的長度。

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

表1 兩個算法在不同集合長度下的運行時間

圖2 兩個算法運行時間差值變化趨勢

4 結語

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