樹型狀態(tài)空間問題的回溯法C語言編程模式

周 雙，周云才 （長江大學(xué)計算機科學(xué)學(xué)院，湖北 荊州434023）

回溯法是基本的算法策略之一，它是通過對解不斷試探測試來進行求解的方法。在問題規(guī)模不是太大的前提下，回溯法可以解決為數(shù)眾多的組合數(shù)問題［1］。

1 回溯法描述

若問題Q可用回溯法求解，它一般能如下表述：對于已知由n元組 （x1，x2，…，xn）組成的一個狀態(tài)空間E＝ ｛（x1，x2，…，xn）｜xi∈si，i＝1，2，…，n｝，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中符合D的全部約束條件的所有n元組0。其中si是分量xi的定義域，且｜si｜有限，i＝1，2，…，n。稱E中符合D的全部約束條件的任何一個n元組為問題Q的一個解。

解決問題Q可用窮舉法，即對狀態(tài)空間里的所有候選解進行帶入驗證，若滿足約束則該候選解即是一個正解。這種方法需要對所有可能解進行探測，工作量非常大。

很多情況下約束集D具有完備性，即i元組 （x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束，意味著j（j＜i）元組 （x1，x2，…，xj）一定也滿足D中僅涉及到x1，x2，…，xj的所有約束 （i＝1，2，…，n）［2］?？砂裯元組狀態(tài)空間看成一棵高為n的帶權(quán)有序樹，從根結(jié)點出發(fā)深度搜索，一旦某結(jié)點違背約束條件則包含該結(jié)點的路徑絕不會是正解，此時可剪掉該結(jié)點不再繼續(xù)深入搜索。回溯法就是這樣在深度搜索過程中利用約束條件進行枝剪來避免無效搜索的，顯然比窮舉法的效率要高很多。

2 C語言編程模式

一個狀態(tài)空間如果其導(dǎo)出空間是一個樹型顯式空間，則稱為樹型狀態(tài)空間。根據(jù)被搜索的狀態(tài)空間是否為樹型狀態(tài)空間，回溯算法可分為2類：樹型狀態(tài)空間的回溯搜索稱為基于樹的回溯，其它狀態(tài)空間的回溯搜索稱為基于圖的回溯［1］。筆者的目的是針對基于樹的回溯的C語言編程進行模式化。由于不同問題對解的需求不同——有的需得到任意一個解、有的需全體解、有的需最優(yōu)解，所以在該模式中也做了區(qū)分對待，從程序的注釋中可以看到。

回溯法的基本思想就是以某種順序?qū)蜻x解進行逐一測試。對當(dāng)前試探，有以下幾種情況：①若試探成功且到達搜索空間規(guī)模，那它即是一個正解，按需求記錄或打印后可退出或回溯繼續(xù)找解；②若試探失敗則有2種情況：調(diào)整到下一候選解繼續(xù)試探；若當(dāng)前規(guī)模內(nèi)無下一候選解則回溯，對上層的兄弟子樹繼續(xù)試探；③若試探成功且未達到搜索空間規(guī)模，則擴大當(dāng)前候選解規(guī)模并繼續(xù)試探。

設(shè)回溯問題的解是一個n元數(shù)組 ［a1，a2，…，an］，i代表求解過程中的第i個試探點、a ［i］代表該試探點上的選用值，則回溯法解決問題的編程模式為：

3 0－1背包問題和n皇后問題的求解

3.1 0－1背包問題

圖1 狀態(tài)空間樹

0－1背包問題描述如下：給定一個容量為c的背包和n個物品。對于物品i，它的重量是w［i］，價值是p［i］。在物品不可分割的情況下，怎樣選擇裝進背包的物品使得最后背包內(nèi)的物品價值和最大。當(dāng)n＝3時，0－1背包問題有23種可能的解，其狀態(tài)空間樹如圖1所示。當(dāng)有3個物品，空間樹有3層子樹，每層的狀態(tài)對應(yīng)相應(yīng)物品的裝入與否。在每個內(nèi)部結(jié)點處用兩個子結(jié)點將解空間分成2個不相交的子解空間，A結(jié)點左子樹上的結(jié)點B代表在al＝l情況下解空間所有元素，右子樹上的結(jié)點C則代表在al＝0情況下解空間所有元素，每層情況依此類推，例如結(jié)點J代表在a1＝1、a2＝0、a3＝1情況下解空間的元素等。

在每個非葉子結(jié)點處用a［i］為1和0分別標(biāo)識左右子樹，來說明第i種物品放入背包與否。深度優(yōu)先搜索狀態(tài)空間樹，確定前i個物品的狀態(tài)后直接進入下一個物品代表結(jié)點搜索左子結(jié)點，若背包剩余空間足夠則繼續(xù)深入，否則回溯搜索下一個物品代表結(jié)點右子結(jié)點，若右子結(jié)點仍不符合則回溯至父結(jié)點的兄弟結(jié)點繼續(xù)試探。搜索中對路徑上a［i］取1的物品價值進行保留，到達底層葉子結(jié)點時比較得出當(dāng)前最優(yōu)總價值，用best p記錄當(dāng)前最優(yōu)總價值，并用best x［i］保留相應(yīng)路徑a［i］。整個狀態(tài)空間樹搜索完畢后按照保留的路徑best x［i］就可得解。按照上述規(guī)則進行搜索，每搜索到一個較優(yōu)解則保存當(dāng)前路徑并回溯繼續(xù)尋找解，直到回溯至根結(jié)點則搜索停止，并輸出最優(yōu)解路徑。用cw表示當(dāng)前包內(nèi)物品重量，cp表示當(dāng)前包內(nèi)物品價值。0－1背包問題是為了得到最優(yōu)解，則回溯法應(yīng)用C語言程序如下：

3.2 n皇后問題

n皇后問題描述如下：在n＊n棋盤上放n個皇后，要求每行、每列、每個對角線至多放置一個皇后［1］。由描述可以，n皇后問題的每一互不攻擊的布局均唯一對應(yīng)1、2、3、…、n的一個排列A ［1］A ［2］…A ［n］ ［4］。那么可以用一個n元數(shù)組 ［a1，a2，…，an］表示解的布局，i （i＝1，2，3，…，n）表示搜索深度，也就是當(dāng)前搜索列，a［i］代表第i列上皇后的行號。

“每行、每列、每個對角線至多放置一個皇后”用約束函數(shù)run（）來判別，若位置可行返回TRUE，否則返回FALSE。每列的初次試探從該列第一行開始，當(dāng)搜索到第i列的a［i］行時，若行數(shù)小于n且違背約束條件，就把下一行當(dāng)候選解繼續(xù)測試；若為第n行且違背約束條件則回溯到前列皇后下一行繼續(xù)試探；若已搜索到第n列仍滿足所有條件則已找到一種解，輸出后回溯繼續(xù)尋找其他解；若未到第n列且滿足約束條件則擴展候選解尋找下一列上的皇后；若回溯到第1列的第n行，該列上已沒有候選皇后，則結(jié)束?；厮莘☉?yīng)用的C語言程序如下：

4 結(jié) 語

回溯法在計算機科學(xué)與技術(shù)中有著廣泛的應(yīng)用［5］。筆者抽象出了回溯法解題的C語言編程模式，并對上面2個典型問題進行探討驗證了該模式的可行性。顯然狀態(tài)空間為樹型的問題根據(jù)其約束條件、回溯點、各個取值點取值方式、問題規(guī)模等就可帶入該模式并根據(jù)實際情況細(xì)化程序?qū)崿F(xiàn)。結(jié)果是輸出任一解、最優(yōu)解還是所有解則根據(jù)具體問題的需求來操作，如果是任一解則找到解便結(jié)束，否則輸出或保存后便回溯到上一出發(fā)點繼續(xù)找其他解。

回溯法的思想很多文獻都描述過，在文獻 ［6］中作者通過對幾個典型問題進行具體分析和程序?qū)崿F(xiàn)來闡述了回溯法的解題思路，但并沒有將它們抽象化為一個模型。筆者通過分析問題探討了樹型狀態(tài)空間問題的回溯法編程模型，有助于讀者更好地理解回溯法、更好地利用回溯法解決一般問題，提高回溯法實現(xiàn)的可復(fù)用性。

［1］王巖冰，鄭春明，劉弘 .回溯算法的形式模型 ［J］.計算機研究與發(fā)展，2001，38（9）；1066－1079.

［2］鄭宗漢，鄭曉明 .算法設(shè)計與分析 ［M］.北京：清華大學(xué)出版社，2005.

［3］任小康，吳尚智等 .基于動態(tài)狀態(tài)樹的回溯算法 ［J］.計算機工程與設(shè)計，2007，28（4）；755－759.

［4］張萬軍.N皇后問題回溯算法探討 ［J］.宜賓學(xué)院學(xué)報，2006，6；64－66.

［5］劉從軍.GOF的模板方法及其在回溯算法中應(yīng)用研究 ［J］.現(xiàn)代電子技術(shù)，2009，20；123－125.

［6］程國忠，張世祿 .三個典型問題的回溯算法 ［J］.四川師范學(xué)院學(xué)報 （自然科學(xué)版），2000，21（2）；187－191.