下載

下載

第1 6章 回 溯

尋找問題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個，在檢查完

所有或部分候選解后，即可找到所需要的解。理論上，當候選解數量有限并且通過檢查所有或

部分候選解能夠得到所需解時，上述方法是可行的。不過，在實際應用中，很少使用這種方法，

因為候選解的數量通常都非常大(比如指數級，甚至是大數階乘)，即便采用最快的計算機也

只能解決規模很小的問題。

對候選解進行系統檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。按

照這兩種方法對候選解進行系統檢查通常會使問題的求解時間大大減少(無論對于最壞情形

還是對于一般情形)。事實上，這些方法可以使我們避免對很大的候選解集合進行檢查，同時

能夠保證算法運行結束時可以找到所需要的解。因此，這些方法通常能夠用來求解規模很大

的問題。

本章集中闡述回溯方法，這種方法被用來設計貨箱裝船、背包、最大完備子圖、旅行商和

電路板排列問題的求解算法。

16.1 算法思想

回溯(b a c k t r a c k i n g )是一種系統地搜索問題解答的方法。在 5 . 5 . 6節求解迷宮老鼠問題時

即采用了回溯技術。為了實現回溯，首先需要為問題定義一個解空間( solution space )，這個

空間必須至少包含問題的一個解(可能是最優的)。在迷宮老鼠問題中，我們可以定義一個包

含從入口到出口的所有路徑的解空間；在具有 n 個對象的0 / 1背包問題中(見 1 3 . 4節和1 5 . 2節)，

解空間的一個合理選擇是 2n 個長度為n 的0 / 1 向量的集合，這個集合表示了將0或1分配給x 的所

有可能方法。當n= 3 時，解空間為 { ( 0 , 0 , 0 )，( 0 , 1 , 0 ) ，( 0 , 0 , 1 )，( 1 , 0 , 0 ) ，( 0 , 1 , 1 ) ，( 1 , 0 , 1 ) ，( 1 , 1 , 0 )，

( 1 , 1 , 1 ) } 。

下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹。圖 1 6 - 1用圖的形

式給出了一個3 ×3迷宮的解空間。從( 1 , 1 )點到( 3 , 3 )點的每一條路徑都定義了3 ×3迷宮解空間中

的一個元素，但由于障礙的設置，有些路

徑是不可行的。

圖1 6 - 2用樹形結構給出了含三個對象的

0 / 1 背包問題的解空間。從 i 層節點到 i+ 1層

節點的一條邊上的數字給出了向量 x 中第i

個分量的值x ，從根節點到葉節點的每一條

i

路徑定義了解空間中的一個元素。從根節

點A 到葉節點H 的路徑定義了解 x = [ 1 , 1 , 1 ] 。

根據w 和c 的值，從根到葉的路徑中的一些

解或全部解可能是不可行的。

一旦定義了解空間的組織方法，這個

空間即可按深度優先的方法從開始節點進 圖16-1 3 ×3迷宮的解空間

第 1 6章 回 溯 4 9 3

下載

行搜索。在迷宮老鼠問題中，開始節點為入口節點 ( 1 , 1 ) ；在0 / 1背包問題中，開始節點為根節

點A 。開始節點既是一個活節點又是一個E-節點(expansion node )。從E-節點可移動到一個新

節點。如果能從當前的 E-節點移動到一個新節點，那么這個新節點將變成一個活節點和新的

E-節點，舊的E-節點仍是一個活節點。如果不能移到一個新節點，當前的 E-節點就“死”了

(即不再是一個活節點)，那么便只能返回到最近被考察的活節點(回溯)，這個活節點變成了

新的E-節點。當我們已經找到了答案或者回溯盡了所有的活節點時，搜索過程結束。

圖16-2 三個對象的背包問題的解空間

例16-1 [迷宮老鼠] 考察圖16-3a 的矩陣中給出的3 ×3的“迷宮老鼠”問題。我們將利用圖 1 6 -

1給出的解空間圖來搜索迷宮。

從迷宮的入口到出口的每一條路徑都與圖 1 6 - 1中從( 1 , 1 )到( 3

總結

以上是生活随笔為你收集整理的数据结构 算法与应用C 语言描述答案,数据结构算法与应用-C语言描述.pdf的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。