資源簡介

(共22張PPT)
第13課
算法的設(shè)計
用回溯算法解題的一般步驟
01
02
回溯算法應(yīng)用
回溯算法概念
03
目錄
02
04
回溯算法的一般描述
回溯算法概念
01
Part One
回溯法概念
是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。
回溯算法的一般描述
02
回溯算法的一般描述
可用回溯法求解的問題P，通常要能表達(dá)為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當(dāng)大的。
我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j\u003Ci）元組（x1，x2，…，xj）一定也滿足D中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反D中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反D中僅涉及到x1，x2，…，xi的一個約束，n≥i>j。
因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。
回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。
樹T類似于檢索樹，它可以這樣構(gòu)造：設(shè)Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。從根開始，讓T的第I層的每一個結(jié)點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。
滿足條件：
照這種構(gòu)造方式，E中的一個n元組（x1，x2，…，xn）對應(yīng)于T中的一個葉子結(jié)點，T的根到這個葉子結(jié)點的路徑上依次的n條邊的權(quán)分別為x1，x2，…，xn，反之亦然。另外，對于任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，x2，…，xi）對應(yīng)于T中的一個非葉子結(jié)點，T的根到這個非葉子結(jié)點的路徑上依次的I條邊的權(quán)分別為x1，x2，…，xi，反之亦然。
特別，E中的任意一個n元組的空前綴（），對應(yīng)于T的根。因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結(jié)點，要求從T的根到該葉子結(jié)點的路徑上依次的n條邊相應(yīng)帶的n個權(quán)x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結(jié)點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。
在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結(jié)點被稱為問題P的狀態(tài)結(jié)點；樹T上的任意一個葉子結(jié)點被稱為問題P的一個解狀態(tài)結(jié)點；樹T上滿足約束集D的全部約束的任意一個葉子結(jié)點被稱為問題P的一個回答狀態(tài)結(jié)點，它對應(yīng)于問題P的一個解.
用回溯算法解題的一般步驟
03
用回溯法解題的一般步驟：
01
針對所給問題，定義問題的解空間；
02
確定易于搜索的解空間結(jié)構(gòu)；
03
以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。
回溯算法應(yīng)用
04
回溯法應(yīng)用：
1.數(shù)的劃分
2.運動員最佳配對問題
3.解決汽車加油次數(shù)最少問題
4. 找出n個自然數(shù)中取r個數(shù)的全排列
5. 八皇后問題
6. 圖的著色問題
7. 裝載問題
8. 批處理作業(yè)調(diào)度問題
9. 再再論背包問題
10. 最大團(tuán)問題
11. 連續(xù)郵資問題
12. 符號三角形問題
小結(jié)
今天你學(xué)到了什么 說一說自己的收獲。
練習(xí)1
針對機(jī)器人畫正六邊形的問題,設(shè)計一個算法。
練習(xí)2
練習(xí)3
感謝聆聽

展開更多......

收起↑