算法設(shè)計(jì)與分析第8章-回溯法詳解課件

1、第8章 回溯法Back Track Method算法設(shè)計(jì)與分析本科生課程Design and Analysis of Algorithm海南大學(xué)信息科學(xué)技術(shù)學(xué)院College of Information Science and Technology, Hainan University2022/7/28Chapter 8 Back Track Method2 在現(xiàn)實(shí)世界中，很多問題沒有（至少目前沒有）有效的算法，這些問題的解只能通過窮舉搜索來得到。只有滿足約束條件的解才是可行解，只有滿足目標(biāo)函數(shù)的解才是最優(yōu)解，這就有可能避免無效的搜索，提高搜索效率?；厮莘ê头种藿绶ň鶎儆谟薪M織的系統(tǒng)化搜索

2、技術(shù)，可看作是窮舉搜索的改進(jìn)。蠻力法：生成問題的所有可能解，再去評(píng)估是否滿足約束條件；回溯法：每次只構(gòu)造可能解的一部分，然后評(píng)估這個(gè)部分解，如果有可能導(dǎo)致一個(gè)完整解，則對(duì)其進(jìn)一步構(gòu)造，否則不必繼續(xù)構(gòu)造這個(gè)部分解。這樣可以避免搜索所有的可能解，適用于求解組合數(shù)量較大的問題?；谒阉鞯乃惴ㄔO(shè)計(jì)技術(shù)2022/7/283教學(xué)重點(diǎn)回溯法的設(shè)計(jì)思想，各種經(jīng)典問題的回溯思想教學(xué)難點(diǎn)批處理作業(yè)調(diào)度問題的回溯算法教學(xué)內(nèi)容及目標(biāo)知識(shí)點(diǎn)教學(xué)要求了解理解掌握熟練掌握問題的解空間樹回溯法的設(shè)計(jì)思想回溯法的時(shí)間性能圖著色問題哈密爾頓回路問題八皇后問題批處理作業(yè)調(diào)度問題學(xué)習(xí)目標(biāo)Chapter 8 Back Track Me

3、thod2022/7/28Chapter 8 Back Track Method4本章要點(diǎn)8.1 概 述 8.2 圖問題中的回溯法8.3 組合問題中的回溯法2022/7/28Chapter 8 Back Track Method58.1 概 述 8.1.1 問題的解空間8.1.2 回溯法的設(shè)計(jì)思想8.1.3 回溯法的時(shí)間性能2022/7/28Chapter 9 Back Track Method6提出問題？ 復(fù)雜問題常常有很多的可能解，這些可能解構(gòu)成了問題的解空間。解空間？就是在窮舉法中提到的所有可能解的搜索空間。一般而言，解空間中應(yīng)該包括所有的可能解。問題的解向量為 X=（x1, x2 ,

4、xn）。xi 的取值范圍為有窮集 Si。把 xi 的所有可能取值的組合，稱為問題的解空間。每一個(gè)組合是問題的一個(gè)可能解。不正確的解空間會(huì)引發(fā)問題？可能會(huì)增加很多重復(fù)解，或者根本就搜索不到正確的解。（例： 用桌面上的6根火柴棒為邊搭建4個(gè)等邊三角形）概述 -問題的解空間 2022/7/28Chapter 8 Back Track Method7示例：桌子上有6根火柴棒，要求以這6根火柴棒為邊搭建4個(gè)等邊三角形。概述 -問題的解空間 (a) 二維搜索空間無解 (b) 三維搜索空間的解 圖8.1 錯(cuò)誤的解空間將不能搜索到正確答案2022/7/28Chapter 8 Back Track Method

5、8例：0/1背包問題中，xi 有0/1 兩種取值，則S=0，1，當(dāng)n=3時(shí)，0/1背包問題的解空間是：(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)即：當(dāng)輸入規(guī)模為n 時(shí)，有2n 種可能的解。例：貨郎擔(dān)問題，S=1,2,n，當(dāng)n=3時(shí)，S=1,2,3 。貨郎擔(dān)TSP問題的解空間中的可能解有27個(gè)，是：(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(3,3,1),(3,3,2),(3,3,3)當(dāng)輸入規(guī)模為 n 時(shí)，它有 nn 種可能的解。考慮到約束方程

6、xixj 。因此，貨郎擔(dān)問題的 解空間壓縮為： (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)當(dāng)輸入規(guī)模為n 時(shí)，它有 n! 種可能的解。概述 -問題的解空間 2022/7/28Chapter 8 Back Track Method9可能解的表示方式？ 如，對(duì)于n 個(gè)物品的 0/1 背包問題，其可能解有以下兩種：可能解由一個(gè)不等長(zhǎng)向量組成，當(dāng)物品 i(1in)裝入背包時(shí)，解向量中包含分量 i，否則，解向量中不包含分量 i，當(dāng)n=3時(shí)，其解空間是： ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2,

7、 3) 可能解由等長(zhǎng)向量 x1, x2, , xn 組成，xi=1/0(1in) 分別表示物品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) 概述 -問題的解空間 2022/7/28Chapter 8 Back Track Method10回溯法“可能解”及“解空間”的表達(dá) 可能解的表示：用等長(zhǎng)向量 X=(x1, x2, , xn)，其中分量 xi (1in) 的取值范圍是某個(gè)有限集合 Si=ai1, ai2, ,

8、airi，所有可能的解向量構(gòu)成了問題的解空間。 概述 -問題的解空間 解空間表達(dá)：用解空間樹（Solution Space Trees）/也稱狀態(tài)空間樹的方式組織：第1層（根結(jié)點(diǎn)）：表示搜索的初始狀態(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è)可能解。2022/7/28Chapter 8 Back Track Method11可行解：滿足約束條件的解，解空間中的一個(gè)子集最優(yōu)解：使目標(biāo)函數(shù)取極值(極大或極小)的可行解，一個(gè)或少數(shù)幾個(gè)例：貨郎擔(dān)問題，有nn種可能解。n!種可行解，只有一個(gè)或幾個(gè)

9、是最優(yōu)解。例：背包問題，有2n種可能解，有些是可行解，只有一個(gè)或幾個(gè)是最優(yōu)解有些問題，只要可行解，不需要最優(yōu)解：例：八皇后問題和圖的著色問題概述 -問題的解空間 2022/7/28Chapter 8 Back Track Method12例：對(duì)于n=3 的0/1 背包問題，其解空間樹如圖8.2 所示，樹中的8個(gè)葉子結(jié)點(diǎn)分別代表該問題的 8 個(gè)可能解。 對(duì)物品1的選擇對(duì)物品3的選擇對(duì)物品2的選擇1111110000000112345781112141531069概述 -問題的解空間 2022/7/28Chapter 8 Back Track Method13例：對(duì)于n=4 的TSP 問題，圖8.

10、3是經(jīng)壓縮后的解空間樹，樹中的24 個(gè)葉子結(jié)點(diǎn)分別代表該問題的24 個(gè)可能解，例如結(jié)點(diǎn)5 代表一個(gè)可能解，路徑為 12341，長(zhǎng)度為各邊代價(jià)之和。 圖8.3 n=4 的 TSP 問題經(jīng)壓縮后解空間樹2434223434131424121233121341313123212142414343224341231241345710121517212326283133373942444749525457596264469111416202225273032363841434648515356586163381319242935404550556021834241123434概述 -問題的解空間 202

11、2/7/28Chapter 8 Back Track Method148.1 概 述 8.1.1 問題的解空間8.1.2 回溯法的設(shè)計(jì)思想8.1.3 回溯法的時(shí)間性能2022/7/28Chapter 8 Back Track Method15回溯法的設(shè)計(jì)思想 回溯法從根結(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)先策略搜索。2

12、022/7/28Chapter 8 Back Track Method16例：對(duì)于n=3 的0/1 背包問題，其參數(shù)如下： 重量W=20, 15,10，價(jià)值V=20, 30, 25，背包容量C=25下圖是解空間樹結(jié)構(gòu)結(jié)果，從根結(jié)點(diǎn)出發(fā)，其搜索過程如下： 1不可行解價(jià)值=20價(jià)值=55價(jià)值=30價(jià)值=25價(jià)值=0111100000011238111214151310697不可行解回溯法的設(shè)計(jì)思想X1=1, V1=20C=25-20=5X2=1, W2=15V2=30,C=5X2=0,V=20C=5X3=0,V=20C=5可行解1X1=0, V=0C=25X2=1, V=30C=10可行解2可行解

13、3可行解4可行解52022/7/28Chapter 8 Back Track Method17在2叉完全樹中，結(jié)點(diǎn)總數(shù)有：1+21+22+222=151不可行解價(jià)值=20價(jià)值=55價(jià)值=30價(jià)值=25價(jià)值=0111100000011238111214151310697不可行解回溯法的設(shè)計(jì)思想 1045不可行解2022/7/28Chapter 8 Back Track Method18回溯法的搜索過程涉及的結(jié)點(diǎn)稱為搜索空間，只是整個(gè)解空間樹的一部分，在搜索過程中，通常采用兩種策略避免無效搜索：用約束條件剪去得不到可行解的子樹；用目標(biāo)函數(shù)剪去得不到最優(yōu)解的子樹。這兩類函數(shù)統(tǒng)稱為剪枝函數(shù)（Pruni

14、ng Function）。回溯法的設(shè)計(jì)思想需要注意的是： 問題的解空間樹是虛擬的，并不需要在算法運(yùn)行時(shí)構(gòu)造一棵真正的樹結(jié)構(gòu)，只需要存儲(chǔ)從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑。2022/7/28Chapter 8 Back Track Method198.1 概 述 8.1.1 問題的解空間8.1.2 回溯法的設(shè)計(jì)思想8.1.3 回溯法的時(shí)間性能2022/7/28Chapter 8 Back Track Method20回溯法的時(shí)間性能 一般情況下，在問題的解向量 X=( x1, x2, , xn )中，分量 xi (1in) 的取值范圍為某個(gè)有限集合Si=ai1, ai2, , airi，因此，問題的解空間

15、由笛卡兒積 A=S1S2Sn 構(gòu)成，并且第 1 層的根結(jié)點(diǎn)有|S1| 棵子樹，則第2層共有 |S1| 個(gè)結(jié)點(diǎn)，第 2 層的每個(gè)結(jié)點(diǎn)有 |S2| 棵子樹，則第3層共有 |S1|S2| 個(gè)結(jié)點(diǎn)； 依此類推，第n+1層共有|S1|S2|Sn| 個(gè)結(jié)點(diǎn)，他們都是葉子結(jié)點(diǎn)，代表問題的所有可能解。2022/7/28Chapter 8 Back Track Method21在用回溯法求解問題時(shí)，常用到兩種典型的解空間樹： （1）子集樹：當(dāng)問題是從n 個(gè)元素的集合中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹。在子集樹中，|S1|=|S2|=|Sn|=c，即每個(gè)結(jié)點(diǎn)有相同數(shù)目的子樹，當(dāng)c=2，則子集樹中

16、共有 2n 個(gè)葉子結(jié)點(diǎn)，因此，遍歷子集樹需要(2n)時(shí)間。如：0/1背包（2）排列樹：當(dāng)問題是確定 n 個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。在排列樹中，通常情況下，|S1|=n，|S2|=n-1，|Sn|=1，所以，排列樹中共有n! 個(gè)葉子結(jié)點(diǎn)，因此，遍歷排列樹需要(n!)時(shí)間。如：TSP問題回溯法的時(shí)間性能 回溯法實(shí)際上屬于蠻力窮舉法，當(dāng)然不能指望它有很好的最壞時(shí)間復(fù)雜性（指數(shù)階）。其有效性往往體現(xiàn)在當(dāng)問題規(guī)模n很大時(shí)，在搜索過程中對(duì)問題的解空間樹大量剪枝。但是很難估計(jì)出在搜索過程中所產(chǎn)生的結(jié)點(diǎn)數(shù)，這也是分析回溯法的時(shí)間性能的主要困難。回溯法的時(shí)間性能 2022/7/28C

17、hapter 8 Back Track Method23本章要點(diǎn)8.1 概 述 8.2 圖問題中的回溯法8.3 組合問題中的回溯法2022/7/28Chapter 8 Back Track Method248.2 圖問題中的回溯法 8.2.1 圖著色問題 8.2.2 哈密頓回路問題2022/7/28Chapter 8 Back Track Method25圖著色問題 圖著色問題描述為：給定無向連通圖G=(V, E)和正整數(shù)m，求最小的整數(shù)m，當(dāng)用m種顏色對(duì)G中的頂點(diǎn)著色，使得任意兩個(gè)相鄰頂點(diǎn)著色不同。2022/7/28Chapter 8 Back Track Method26 由于用m 種顏色

18、為無向圖 G=(V, E) 著色，其中，V 的頂點(diǎn)個(gè)數(shù)為n，可以用一個(gè) n 元組 C=(c1, c2, , cn) 來描述圖的一種可能著色，其中，ci1, 2, , m(1in) 表示賦予頂點(diǎn)i 的顏色。 例如：5 元組 (1, 2, 2, 3, 1) 表示對(duì)5 個(gè)頂點(diǎn)無向圖的著色方案之一，其中： 頂點(diǎn) 1: 著顏色1；頂點(diǎn) 2 : 著顏色2；頂點(diǎn) 3 : 著顏色 2 5 元組 (1, 3, 2, 3, 1)表示另一種著色方案 如用m種顏色給n個(gè)頂點(diǎn)的圖著色，有mn種可能的著色組合圖著色問題 2022/7/28Chapter 8 Back Track Method27狀態(tài)空間樹 圖著色問題的解

19、空間樹是一棵高度為n的完全m叉樹。在這里，樹的高度是指從樹的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長(zhǎng)通路的長(zhǎng)度。每一個(gè)分支結(jié)點(diǎn)，都有m個(gè)兒子結(jié)點(diǎn)。最底層有mn個(gè)葉子結(jié)點(diǎn)m=3,n=3。圖著色問題 三著色具有三個(gè)頂點(diǎn)的圖的狀態(tài)空間樹頂點(diǎn)1的m種著色2022/7/28Chapter 8 Back Track Method28回溯法求解圖著色問題步驟：首先把所有頂點(diǎn)的顏色初始化為0，然后依次為每個(gè)頂點(diǎn)著色；著色問題的解空間樹中，如從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)一個(gè)部分解，也就是所有的顏色指派都沒有沖突，則在當(dāng)前結(jié)點(diǎn)處選擇第一棵子樹繼續(xù)搜索，也就是為下一個(gè)頂點(diǎn)著顏色1，否則，對(duì)當(dāng)前子樹的兄弟子樹繼續(xù)搜索，也就是為當(dāng)前頂點(diǎn)著下一

20、個(gè)顏色；如果所有m 種顏色都已嘗試過并且都發(fā)生沖突，則回溯到當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)處，上一個(gè)頂點(diǎn)的顏色被改變，依此類推。 圖著色問題 2022/7/28Chapter 8 Back Track Method29D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a) 一個(gè)無向圖 (b) 回溯法搜索空間圖8.8 回溯法求解圖著色問題示例圖著色問題 搜索過程約束方程：color i color j 若頂點(diǎn)i 與頂點(diǎn) j 相鄰接 例：三著色右圖所示的無向圖。結(jié)論：狀態(tài)空間樹結(jié)點(diǎn)總數(shù)為：1+3+9+27+81+243=364搜索過程所訪問的結(jié)點(diǎn)數(shù)只有14 個(gè)什么是三著色圖的

21、可行解？頂點(diǎn)2022/7/28Chapter 8 Back Track Method30設(shè)數(shù)組colorn表示頂點(diǎn)的著色情況，回溯法求解m著色問題的算法如下： 算法8.1圖著色問題 1將數(shù)組colorn初始化為0； 2k=1; 3while (k=1) 3.1 依次考察每一種顏色，若頂點(diǎn)k的著色與其他頂點(diǎn)的著色不發(fā)生沖突，則轉(zhuǎn)步驟3.2；否則，搜索下一個(gè)顏色； 3.2 若頂點(diǎn)已全部著色，則輸出數(shù)組colorn，返回； 3.3 否則， 3.3.1 若頂點(diǎn)k是一個(gè)合法著色，則k=k+1，轉(zhuǎn)步驟3處理下一個(gè)頂點(diǎn)； 3.3.2 否則，重置頂點(diǎn)k的著色情況，k=k-1，轉(zhuǎn)步驟3回溯；偽代碼圖著色問題 2

22、022/7/28Chapter 8 Back Track Method31算法8.2 圖著色問題 void GraphColor (int n, int c , int m) /所有數(shù)組下標(biāo)從1開始 for (i=1; i=1) colork=colork+1; while (colork=m) if Ok(k) break; else colork=colork+1; /搜索下一個(gè)顏色 if (colork=m & k= =n) /求解完畢，輸出解 for (i=1; i=n; i+) coutcolori; return; C+描述2022/7/28Chapter 8 Back Track

23、 Method32 else if (colork=m & kn) k=k+1; /處理下一個(gè)頂點(diǎn) else colork=0; k=k-1; /回溯 bool Ok (int k) /判斷頂點(diǎn)k的著色是否發(fā)生沖突 for (i=1; i=1) 3.1 xk=xk+1，搜索下一個(gè)頂點(diǎn); 3.2 若(n個(gè)頂點(diǎn)沒有被窮舉完) 執(zhí)行下列操作 3.2.1 若(頂點(diǎn)xk不在哈密頓回路上&(xk-1,xk)E)， 轉(zhuǎn)步驟3.3; 3.2.2 否則，xk=xk+1，搜索下一個(gè)頂點(diǎn)； 3.3 若數(shù)組 xn已形成哈密頓路徑，則輸出數(shù)組xn，算法結(jié)束； 3.4 否則， 3.4.1 若數(shù)組 xn 構(gòu)成哈密頓路徑的部

24、分解， 則 k=k+1，轉(zhuǎn)步驟3； 3.4.2 否則，重置 xk，k=k-1，取消頂點(diǎn) xk 的訪問標(biāo)志， 轉(zhuǎn)步驟3；偽代碼哈密頓回路問題 2022/7/28Chapter 8 Back Track Method39算法8.4哈密頓回路問題 void Hamiton(int n, int x , int c ) /所有數(shù)組下標(biāo)從1開始 for (i=1; i=1) xk=xk+1; /搜索下一頂點(diǎn) while (xk=n) if (visitedxk= =0 & cxk-1xk= =1) break; else xk=xk+1; C+描述2022/7/28Chapter 8 Back Trac

25、k Method40 if (xk=n & k= =n & cxk1= =1) for (k=1; k=n; k+ ) coutxk; return; else if (xk=n & k=1) 3.1 把皇后k擺放在下一列的位置，即xk+; 3.2 從xk開始依次考察每一列，如果皇后k擺放在xk位置不發(fā)生沖突，則轉(zhuǎn)步驟3.3;否則xk+試探下一列; 3.3 若n個(gè)皇后已全部擺放，則輸出一個(gè)解，算法結(jié)束； 3.4 若尚有皇后沒擺放，則k+，轉(zhuǎn)步驟3擺放下一個(gè)皇后； 3.5 若xk出界，則回溯，xk=-1,k-,轉(zhuǎn)步驟3重新擺放皇后k;4. 退出循環(huán)，說明n皇后問題無解；C+描述八皇后問題 202

26、2/7/28Chapter 8 Back Track Method53時(shí)間復(fù)雜度計(jì)算運(yùn)行時(shí)間，取決于所訪問結(jié)點(diǎn)個(gè)數(shù)c 。每訪問一個(gè)結(jié)點(diǎn)，就計(jì)算若干次約束方程。約束方程的執(zhí)行次數(shù)，最少1次，最多n-1次。因此，總次數(shù)為O(cn)。結(jié)點(diǎn)個(gè)數(shù) c 是動(dòng)態(tài)生成的，對(duì)不同實(shí)例，具有不確定性。一般可由 n 的多項(xiàng)式確定。在4叉完全樹中，結(jié)點(diǎn)總數(shù)有141664256341個(gè)。回溯法處理時(shí)，c= 27個(gè)。約為前者的8%實(shí)際模擬表明：當(dāng)n=8時(shí)，被訪問的結(jié)點(diǎn)數(shù)與結(jié)點(diǎn)總數(shù)之比約為1.5%。在最壞情況下的花費(fèi)是O(nn)?？臻g復(fù)雜性：顯然，這個(gè)算法需要使用一個(gè)具有 n 個(gè)分量的向量來存放解向量，所以，算法所需要的工

27、作空間為 。八皇后問題2022/7/28Chapter 8 Back Track Method548.3 組合問題中的回溯法 8.3.1 八皇后問題 8.3.2 批處理作業(yè)調(diào)度問題2022/7/28Chapter 8 Back Track Method55批處理作業(yè)調(diào)度問題 批處理作業(yè)調(diào)度問題? 設(shè)有n 個(gè)作業(yè) 1, 2, , n 要在兩臺(tái)機(jī)器上處理： 作業(yè)i 先由機(jī)器1處理(所需時(shí)間為ai ) 再由機(jī)器2 處理 (所需時(shí)間為bi ) (1in） 批處理作業(yè)調(diào)度問題： 要求確定這n個(gè)作業(yè)的最優(yōu)處理順序，使得從第1個(gè)作業(yè)在機(jī)器1上處理開始，到最后一個(gè)作業(yè)在機(jī)器2上處理結(jié)束所需時(shí)間最少。 2022

28、/7/28Chapter 8 Back Track Method56理想求解結(jié)果批處理作業(yè)的一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器1沒有空閑時(shí)間，且機(jī)器2的空閑時(shí)間最小。可以證明，存在一個(gè)最優(yōu)作業(yè)調(diào)度使得在機(jī)器1和機(jī)器2上作業(yè)以相同次序完成。例：三個(gè)作業(yè)1, 2, 3機(jī)器1上所需的處理時(shí)間為(2, 3, 2)；機(jī)器2上所需的處理時(shí)間為(1, 1, 3)； 則最佳調(diào)度方案是(1, 3, 2)、(3, 1, 2)和(3, 2, 1)，其完成時(shí)間為8。 批處理作業(yè)調(diào)度問題 2022/7/28Chapter 8 Back Track Method57作業(yè)1:2作業(yè)2:3作業(yè)3:2空閑:2作業(yè)1:1機(jī)器1機(jī)器2作業(yè)2:1作業(yè)3:3(a) 調(diào)度方案(1, 2, 3)，最后完成時(shí)間為10作業(yè)1:2作業(yè)2:3作業(yè)3:2空閑:2作業(yè)1