算法設(shè)計(jì)與分析第五章-展示頁
2025-01-27 20:55本頁面
【正文】 3 4 4 2 3 2 4 4 3 3 2 2 完全圖 1 2 3 4 6 30 10 20 5 4 59 )!1( ?n回溯法 ?用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹； 剪枝函數(shù)： ?用限界函數(shù)剪去得不到最優(yōu)解的子樹。第五章 回溯法 學(xué)習(xí)要求： ?理解回溯法的 深度優(yōu)先 搜索策略 ?掌握用回溯法解題的 算法框架 (1)子集樹算法框架 (2)排列樹算法框架 ? 通過應(yīng)用范例學(xué)習(xí)回溯法的設(shè)計(jì)策略 回溯法 問題的解空間 01背包問題： 3?n 其解空間是： {(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)} 用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間。 問題的解空間至少應(yīng)包含問題的一個(gè) (最優(yōu) )解。 回溯法 01背包問題 A B C D E F G H I J K L M N O 1 0 1 1 1 1 1 1 0 0 0 0 0 0 }15,15,16{?w}25,25,45{?p30?c約束函數(shù) 回溯法 1 A B D E H J I K N P O Q 4 3 4 2 3 2 4 C G F M L 2 3 4 4 3 3 2 2 1 2 3 4 6 30 10 20 5 4 25 30 限界函數(shù)剪枝 回溯法 步驟 ? 針對所給問題，定義問題的解空間； ? 確定易于搜索的解空間結(jié)構(gòu)； ? 以深度優(yōu)先方式搜索解空間，并在搜索 過程中用剪枝函數(shù)避免無效搜索。 子集樹： 01背包問題 n2 12 1 ??n),( 21 nxxx ?變長碼 滿足所有約束條件的解狀態(tài)結(jié)點(diǎn)稱為回答結(jié)點(diǎn)。 旅行售貨員問題 (TSP) 定長碼 樹中從根至葉結(jié)點(diǎn)的路徑的集合 構(gòu)成解空間。 回溯法 搜索過程 搜索按深度優(yōu)先策略從根開始 , 當(dāng)搜索到 任一結(jié)點(diǎn)時(shí) ,判斷該點(diǎn)是包否含問題的解，包 含則繼續(xù)向下深度優(yōu)先搜索 ,否則跳過該結(jié) 點(diǎn)以下的子樹 (剪枝 ),向上逐級回溯。 31},7,24,13,11{,4 ??? MWn例 3： 問題的解可表示為 n 元向量 }1,0{},{21 ?in xxxx ?， 則問題的解空間樹為子集樹。 裝載問題 回溯法 n 個(gè)集裝箱 要 裝到 2 艘載重量分別為 21 , cc 的貨輪
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1