第8章-回溯法(已修改)
2025-08-28 01:36 本頁(yè)面
【正文】 算法設(shè)計(jì)與分析 清華大學(xué)出版社 第 8章 回溯法 概 述 圖問題中的回溯法 組合問題中的回溯法 實(shí)驗(yàn)項(xiàng)目 —— 0/1背包問題 算法設(shè)計(jì)與分析 清華大學(xué)出版社 概 述 問題的解空間 解空間樹的動(dòng)態(tài)搜索（ 1） 回溯法的求解過程 回溯法的時(shí)間性能 算法設(shè)計(jì)與分析 清華大學(xué)出版社 復(fù)雜問題常常有很多的可能解 ， 這些可能解構(gòu)成了問題的解空間 。 解空間也就是進(jìn)行窮舉的搜索空間 ， 所以 ， 解空間中應(yīng)該包括所有的可能解 。 確定正確的解空間很重要 ， 如果沒有確定正確的解空間就開始搜索 ， 可能會(huì)增加很多重復(fù)解 ，或者根本就搜索不到正確的解 。 問題的解空間 算法設(shè)計(jì)與分析 清華大學(xué)出版社 (a) 二維搜索空間無(wú)解 (b) 三維搜索空間的解 圖 錯(cuò)誤的解空間將不能搜索到正確答案 例如：桌子上有 6根火柴棒，要求以這 6根火柴棒為邊搭建 4個(gè)等邊三角形。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 對(duì)于任何一個(gè)問題 ， 可能解的 表示方式 和它相應(yīng)的 解釋 隱含了解空間及其大小 。 例如 ， 對(duì)于有 n個(gè)物品的 0/1背包問題 ， 其可能解的表示方式可以有以下兩種： （ 1） 可能解由一個(gè)不等長(zhǎng)向量組成 ， 當(dāng)物品 i(1≤i≤n)裝入背包時(shí) ， 解向量中包含分量 i， 否則 ， 解向量中不包含分量 i， 當(dāng) n=3時(shí) ， 其解空間是： { ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) } （ 2）可能解由一個(gè)等長(zhǎng)向量 {x1, x2, …, xn}組成，其中xi=1(1≤i≤n)表示物品 i裝入背包， xi=0表示物品 i沒有裝入背包，當(dāng) n=3時(shí)，其解空間是： {(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) } 算法設(shè)計(jì)與分析 清華大學(xué)出版社 為了用回溯法求解一個(gè)具有 n個(gè)輸入的問題 ，一般情況下 ， 將其可能解表示為滿足某個(gè)約束條件的等長(zhǎng)向量 X=(x1, x2, … , xn)， 其中分量 xi (1≤i≤n)的取值范圍是某個(gè)有限集合 Si={ai1, ai2, … , airi}， 所有可能的解向量構(gòu)成了問題的 解空間 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 問題的解空間一般用 解空間樹 （ Solution Space Trees,也稱狀態(tài)空間樹）的方式組織，樹的根結(jié)點(diǎn)位于第 1層，表示搜索的初始狀態(tài)，第 2層的結(jié)點(diǎn)表示對(duì)解向量的第一個(gè)分量做出選擇后到達(dá)的狀態(tài)，第 1層到第 2層的邊上標(biāo)出對(duì)第一個(gè)分量選擇的結(jié)果，依此類推，從樹的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑就構(gòu)成了解空間的一個(gè)可能解。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 對(duì)于 n=3的 0/1背包問題 ， 其解空間樹如圖 ，樹中的 8個(gè)葉子結(jié)點(diǎn)分別代表該問題的 8個(gè)可能解 。 對(duì)物品 1的選擇 對(duì)物品 3的選擇 對(duì)物品 2的選擇 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 2 3 4 5 7 8 11 12 14 15 3 10 6 9 算法設(shè)計(jì)與分析 清華大學(xué)出版社 對(duì)于 n=4的 TSP問題，其解空間樹如圖 ，樹中的24個(gè)葉子結(jié)點(diǎn)分別代表該問題的 24個(gè)可能解，例如結(jié)點(diǎn) 5代表一個(gè)可能解，路徑為 1→ 2→ 3→ 4→ 1，長(zhǎng)度為各邊代價(jià)之和。 2 4 3 4 2 2 3 4 3 4 1 3 1 4 2 4 1 2 1 2 3 3 1 2 1 3 4 1 3 1 3 1 2 3 2 1 2 1 4 2 4 1 4 3 4 2 2 4 3 4 1 2 3 1 2 4 1 3 4 圖 n=4的 TSP問題的解空間樹 5 7 10 12 15 17 21 23 26 28 31 33 37 39 42 44 47 49 52 54 57 59 62 64 4 6 9 11 14 16 20 22 25 27 30 32 36 38 41 43 46 48 51 53 56 58 61 63 3 8 13 19 24 29 35 40 45 50 55 60 2 18 34 24 1 1 2 3 4 3 4 算法設(shè)計(jì)與分析 清華大學(xué)出版社 解空間樹的動(dòng)態(tài)搜索（ 1） 回溯法從根結(jié)點(diǎn)出發(fā) ， 按照深度優(yōu)先策略遍歷解空間樹 ， 搜索滿足約束條件的解 。 在搜索至樹中任一結(jié)點(diǎn)時(shí) ， 先判斷該結(jié)點(diǎn)對(duì)應(yīng)的部分解是否滿足約束條件 ， 或者是否超出 目標(biāo)函數(shù) 的界 ， 也就是判斷該結(jié)點(diǎn)是否 包含 問題的 （ 最優(yōu) ） 解 ， 如果肯定不包含 ， 則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的搜索 ， 即所謂 剪枝 （ Pruning） ；否則 ， 進(jìn)入以該結(jié)點(diǎn)為根的子樹 ， 繼續(xù)按照深度優(yōu)先策略搜索 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 例如，對(duì)于 n=3的 0/1背包問題，三個(gè)物品的重量為 {20, 15, 10}，價(jià)值為 {20, 30, 25}，背包容量為25，從圖 ，搜索過程如下： 1 不可行解 價(jià)值 =20 價(jià)值 =55 價(jià)值 =30 價(jià)值 =25 價(jià)值 =0 1 1 1 1 0 0 0 0 0 0 1 1 2 8 11 12 14 15 13 10 6 9 不可行解 算法設(shè)計(jì)與分析 清華大學(xué)出版社 再如，對(duì)于 n=4的 TSP問題，其代價(jià)矩陣如圖 ， C= ∞ 3 6 7 12 ∞ 2 8 8 6 ∞ 2 3 7 6 ∞ 圖 TSP問題的代價(jià)矩陣 算法設(shè)計(jì)與分析 清華大學(xué)出版社 2 3 4 4 2 2 1 2 3 1 3 4 1 3 1 3 1 2 3 2 1 2 1 4 2 4 1 4 2 2 4 3 4 1 2 3 1 2 4 1 3 4 圖 TSP問題的搜索空間 5 47 54 4 11 27 46 48 51 53 58 3 8 13 24 29 35 40 45 50 55 60 2 18 34 24 1 2 3 4 1 算法設(shè)計(jì)與分析 清華大學(xué)出版社 ? 回溯法的搜索過程涉及的結(jié)點(diǎn) （ 稱為搜索空間 ）只是整個(gè)解空間樹的一部分 ， 在搜索過程中 ， 通常采用兩種策略避免無(wú)效搜索： （ 1） 用 約束條件 剪去得不到可行解的子樹； （ 2） 用 目標(biāo)函數(shù) 剪去得不到最優(yōu)解的子樹 。 這兩類函數(shù)統(tǒng)稱為 剪枝函數(shù) （ Pruning Function） 。 ? 需要注意的是 ， 問題的解空間樹是虛擬的 ， 并不需要在算法運(yùn)行時(shí)構(gòu)造一棵真正的樹結(jié)構(gòu) ， 只需要存儲(chǔ)從根結(jié)點(diǎn)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1