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

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

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

1 回溯法描述

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

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

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

2 C語言編程模式

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

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

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

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

3.1 0－1背包問題

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

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

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

3.2 n皇后問題

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

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

4 結(jié) 語

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

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

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

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

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

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

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

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