算法_五回溯_2016

1、教材教材: 1王王 王曉東王曉東,計(jì)算機(jī)算法設(shè)計(jì)與分析計(jì)算機(jī)算法設(shè)計(jì)與分析(第第4版版),電子工業(yè)電子工業(yè). 2S 唐常杰等譯唐常杰等譯, Sipser著著, 計(jì)算理論導(dǎo)引計(jì)算理論導(dǎo)引, 機(jī)械工業(yè)機(jī)械工業(yè). 參考資料參考資料:3C 潘金貴等譯潘金貴等譯, Cormen等著等著, 算法導(dǎo)論算法導(dǎo)論, 機(jī)械工業(yè)機(jī)械工業(yè). 4M 黃林鵬等譯黃林鵬等譯, Manber著著, 算法引論算法引論-一種創(chuàng)造性方法一種創(chuàng)造性方法, 電子電子. 5劉劉 劉汝佳等劉汝佳等, 算法藝術(shù)與信息學(xué)競(jìng)賽算法藝術(shù)與信息學(xué)競(jìng)賽, 清華大學(xué)清華大學(xué).6L Lewis等著等著, 計(jì)算理論基礎(chǔ)計(jì)算理論基礎(chǔ), 清華大學(xué)清華大學(xué). 計(jì)

2、算理論與計(jì)算理論與算法分析設(shè)計(jì)算法分析設(shè)計(jì) 劉劉 慶慶 暉暉 第第5章章 回溯法回溯法 1. 裝載問題裝載問題 2. 回溯回溯算法設(shè)計(jì)算法設(shè)計(jì)步驟步驟 3. 旅行旅行售貨員問題售貨員問題(TSP) 4. n皇后皇后問題問題 5. 最大團(tuán)問題最大團(tuán)問題 6. 符號(hào)三角形符號(hào)三角形 7. 回溯算法的效率回溯算法的效率搜索算法搜索算法 窮舉搜索窮舉搜索(brute-force Search) 圖遍歷圖遍歷(Graph traversal) - 深度優(yōu)先深度優(yōu)先搜索搜索(DFS) - 廣度優(yōu)先搜索廣度優(yōu)先搜索(BFS) 樹遍歷樹遍歷(Tree traversal) - 回溯回溯(Backtrackin

3、g) - 分枝限界法分枝限界法(Branch and Bound); - 博弈樹搜索博弈樹搜索( - Search)等等 啟發(fā)式搜索啟發(fā)式搜索(Heuristic Search) 蠻力蠻力: 裝載問題裝載問題w1:n,cx1:n 0,1n, 1. x=first(n), bestw=0, 2. 當(dāng)當(dāng)x last(n), 3. cw=sumi=1n xi*wi 4. 若若cw c 且且 cw bestw, 則則bestw=cw 5. x=next(n,x) 字典序字典序: 從從00到到11 逆字典序逆字典序: 從從11到到00 格雷碼序格雷碼序: 從從00到到100, 減少減少cw計(jì)算量計(jì)算量

4、缺點(diǎn)缺點(diǎn): 不容易剪枝不容易剪枝 回溯舉例回溯舉例: 裝載問題裝載問題w1:n,c 在樹上進(jìn)行深度優(yōu)先搜索在樹上進(jìn)行深度優(yōu)先搜索, 通常同層結(jié)構(gòu)相同通常同層結(jié)構(gòu)相同 backtrack(t) /t層號(hào)層號(hào), cw當(dāng)前重量當(dāng)前重量( c), bestw最優(yōu)重量最優(yōu)重量 1. 若若tn, (若若cwbestw,bestw=cw.) 返回返回 2. 若若 cw + wt c, 則則 /約束條件約束條件(剪枝剪枝) 3. cw+=wt, backtrack(t+1), cw-=wt,-/xt=1 4. backtrack(t+1)-/xt=0 初始初始: bestw=cw=0 執(zhí)行執(zhí)行backtrac

5、k(1) 如何得最優(yōu)解如何得最優(yōu)解?如何優(yōu)化如何優(yōu)化? 回溯舉例回溯舉例: 裝載問題裝載問題w1:n,cbacktrack(t) 1. 若若tn, 判斷判斷 記錄記錄 返回返回 2. 若若 cw+wt c, 則則 cw+=wt,backtrack(t+1),cw-=wt, 3. backtrack(t+1) w=16,15,15,c=30 01603116 311615030 15 150 101110111 110 101 1000100011 010 001 000第第1層層 第第2層層 如何改進(jìn)如何改進(jìn)?改進(jìn)回溯改進(jìn)回溯: 裝載問題裝載問題w1:n,c 初始初始: bestw=cw=0.

6、 r=sumt=1n wt /當(dāng)前剩余重量當(dāng)前剩余重量 backtrack(1)backtrack(t) /t是是層號(hào)層號(hào) 1. 若若tn, (若若cwbestw, bestw=cw, bestx=x.) 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 /約束條件約束條件(剪枝剪枝) 4. cw+=wt, xt=1, backtrack(t+1), cw-=wt, 5. 若若 cw + r bestw, 則則 /限制條件限制條件(剪枝剪枝)6. xt=0, backtrack(t+1) 7. r+=wt 回溯舉例回溯舉例: 裝載問題裝載問題w1:3,cw=16,15,15,

7、c=30. 初始初始: bestw=cw=0. r=46. 運(yùn)行運(yùn)行backtrack(1) 維護(hù)維護(hù)(bestw,cw,r)backtrack(t) 1. 若若tn, 判斷判斷 記錄記錄 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 4. cw+=wt, backtrack(t+1), cw-=wt, 5. 若若 cw + r bestw, 則則 backtrack(t+1) 6. r+=wt 016016 161530 回溯舉例回溯舉例: 裝載問題裝載問題w1:3,cw=16,15,15, c=30. 初始初始: bestw=cw=0. r=46. 運(yùn)行運(yùn)行backtr

8、ack(1) 維護(hù)維護(hù)(bestw,cw,r) (0,0,46)1(0,16,30)10(0,16,15)100(0,16,0)backtrack(t) 1. 若若tn, 判斷判斷 記錄記錄 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 4. cw+=wt, backtrack(t+1), cw-=wt, 5. 若若 cw + r bestw, 則則 backtrack(t+1) 6. r+=wt 回溯舉例回溯舉例: 裝載問題裝載問題w1:3,cw=16,15,15, c=30. 初始初始: bestw=cw=0. r=46. 運(yùn)行運(yùn)行backtrack(1) 維護(hù)維護(hù)(b

9、estw,cw,r) (16,0,46)1(16,16,30)10(16,16,15)100(16,16,0)0(16,0,30)backtrack(t) 1. 若若tn, 判斷判斷 記錄記錄 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 4. cw+=wt, backtrack(t+1), cw-=wt, 5. 若若 cw + r bestw, 則則 backtrack(t+1) 6. r+=wt 回溯舉例回溯舉例: 裝載問題裝載問題w1:3,cw=16,15,15, c=30. 初始初始: bestw=cw=0. r=46. 運(yùn)行運(yùn)行backtrack(1) 維護(hù)維護(hù)(

10、bestw,cw,r) (16,0,46)0(16,0,30)01(16,15,15)011(16,30,0)backtrack(t) 1. 若若tn, 判斷判斷 記錄記錄 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 4. cw+=wt, backtrack(t+1), cw-=wt, 5. 若若 cw + r bestw, 則則 backtrack(t+1) 6. r+=wt 回溯舉例回溯舉例: 裝載問題裝載問題w1:3,cw=16,15,15, c=30. 初始初始: bestw=cw=0. r=46. 運(yùn)行運(yùn)行backtrack(1) 維護(hù)維護(hù)(bestw,cw,r

11、)backtrack(t) 1. 若若tn, 判斷判斷 記錄記錄 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 4. cw+=wt, backtrack(t+1), cw-=wt, 5. 若若 cw + r bestw, 則則 backtrack(t+1) 6. r+=wt (30,0,46)0(30,0,30)01(30,15,15)011(16,30,0)遞歸回溯遞歸回溯(backtracking)backtrack(t)1. 若若 tn, 則判斷則判斷 記錄記錄 返回返回 2. 對(duì)對(duì) i = f(n,t) : g(n,t) 3. xt=h(i), 4. 若若C(t)且

12、且B(t), 則則backtrack(t+1) f(n,t), g(n,t)當(dāng)前層擴(kuò)展節(jié)點(diǎn)的起始終止編號(hào)當(dāng)前層擴(kuò)展節(jié)點(diǎn)的起始終止編號(hào) h(i)當(dāng)前層擴(kuò)展節(jié)點(diǎn)的第當(dāng)前層擴(kuò)展節(jié)點(diǎn)的第i個(gè)可選值個(gè)可選值 C(t): 約束函數(shù)約束函數(shù) B(t): 限界函數(shù)限界函數(shù) 調(diào)用一次調(diào)用一次backtrack(1)即可完成整個(gè)回溯搜索過程即可完成整個(gè)回溯搜索過程 判斷記錄也可能在中間做判斷記錄也可能在中間做. 可以迭代回溯可以迭代回溯. 第第5章章 回溯法回溯法 1. 裝載問題裝載問題 2. 回溯回溯算法設(shè)計(jì)算法設(shè)計(jì)步驟步驟 3. 旅行旅行售貨員問題售貨員問題(TSP) 4. n皇后皇后問題問題 5. 最大團(tuán)問

13、題最大團(tuán)問題 6. 符號(hào)三角形符號(hào)三角形 7. 回溯算法的效率回溯算法的效率回溯算法設(shè)計(jì)步驟回溯算法設(shè)計(jì)步驟1. 定義問題的解空間定義問題的解空間 2. 確定易于搜索的解空間結(jié)構(gòu)確定易于搜索的解空間結(jié)構(gòu) 3. 設(shè)計(jì)約束和限制函數(shù)設(shè)計(jì)約束和限制函數(shù) 4. 以深度優(yōu)先方式搜索解空間以深度優(yōu)先方式搜索解空間 回溯舉例回溯舉例: 裝載問題裝載問題w1:n,cbacktrack(t) 1. 若若tn, 判斷判斷 記錄記錄 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 4. cw+=wt, backtrack(t+1), cw-=wt, 5. 若若 cw + r bestw, 則則 b

14、acktrack(t+1) 6. r+=wt 時(shí)間時(shí)間: 回溯回溯 O(2n), 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 O(nC), 但可能但可能C=O(2n) 空間空間: 回溯回溯 O(n), 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃O(C), 裝載問題裝載問題w1:n,c解空間解空間: xi 0,1, 1 i n 解空間結(jié)構(gòu)解空間結(jié)構(gòu): 子集樹子集樹, 1左左0右右 bestw, cw: 最佳和當(dāng)前質(zhì)量最佳和當(dāng)前質(zhì)量 r: 當(dāng)前剩余質(zhì)量當(dāng)前剩余質(zhì)量 cw + wi c /用于左分支用于左分支 cw + r bestw /用于右分支用于右分支 cw c /維持維持nixcxwxwiniiiniii 1 ,1 , 0max11 1011

15、10111 110 101 1000100011 010 001 000提前更新最優(yōu)值提前更新最優(yōu)值 初始初始: bestw=cw=0. r=sumt=1n wt /目前剩余質(zhì)量目前剩余質(zhì)量 backtrack(1)backtrack(t) /t是層數(shù)是層數(shù) 1. 若若tn, (若若cwbestw,bestw=cw) 返回返回 2. r-=wt3. 若若 cw + wt c, 則則 /約束條件約束條件(剪枝剪枝) 4. cw+=wt, backtrack(t+1), cw-=wt, /xt=1 5. 若若 cw + r bestw, 則則 /限制條件限制條件(剪枝剪枝)6. backtrack

16、(t+1) /xt=07. r+=wt 提前更新最優(yōu)值提前更新最優(yōu)值 初始初始: bestw=cw=0. r=sumt=1n wt /目前剩余質(zhì)量目前剩余質(zhì)量 backtrack(1)backtrack(t) /t是層數(shù)是層數(shù) 1. 若若tn, 則返回則返回 2. r-=wt, wt = cw+wt, 3. 若若 wt c, 則則 (若若wtbestw, 則則bestw=wt) 4. cw+=wt, backtrack(t+1), cw-=wt, /xt=1 5. 若若 cw + r bestw, 則則 6. backtrack(t+1) /xt=07. r+=wt 提前更新最優(yōu)值提前更新最優(yōu)

17、值016016 161530 016016 1530 提前更新最優(yōu)值提前更新最優(yōu)值: 第第5章章 回溯法回溯法 1. 裝載問題裝載問題 2. 回溯回溯算法設(shè)計(jì)算法設(shè)計(jì)步驟步驟 3. 旅行旅行售貨員問題售貨員問題(TSP) 4. n皇后皇后問題問題 5. 最大團(tuán)問題最大團(tuán)問題 6. 符號(hào)三角形符號(hào)三角形 7. 回溯算法的效率回溯算法的效率旅行售貨員問題旅行售貨員問題(TSP)某售貨員要到若干城市推銷商品某售貨員要到若干城市推銷商品 已知各城市間的旅費(fèi)已知各城市間的旅費(fèi) 選擇一條從駐地出發(fā)選擇一條從駐地出發(fā), 經(jīng)過每個(gè)城市經(jīng)過每個(gè)城市, 最后回到駐地的路線最后回到駐地的路線, 使總旅費(fèi)最小使總旅費(fèi)

18、最小 解空間和解空間結(jié)構(gòu)解空間和解空間結(jié)構(gòu)(排列樹排列樹): 11214123 124 142 14313132 134 1234 1243 1324 1342 1423 1432 1 3 2 4 30 6 10 20 5 4 TSPbacktrack(i)1. 若若 i n, 則判斷則判斷(記錄記錄bestc, bestx), 返回返回 /cc 2. 對(duì)對(duì) j = i : n 3. 交換交換xi,xj, 4. 若若x1:i費(fèi)用費(fèi)用 n, 則記錄則記錄, 返回返回 2. 對(duì)對(duì) i = 1 : n 3. xt=i, /在第在第t行第行第xt列放一個(gè)皇后列放一個(gè)皇后 4. 若若place(t),

19、則則backtrace(t+1) place(t): 確定確定(t,xt)與與(i,xi)無沖突無沖突(1 i t-1), backtrack(1) 第第5章章 回溯法回溯法 1. 裝載問題裝載問題 2. 回溯回溯算法設(shè)計(jì)算法設(shè)計(jì)步驟步驟 3. 旅行旅行售貨員問題售貨員問題(TSP) 4. n皇后皇后問題問題 5. 最大團(tuán)問題最大團(tuán)問題 6. 符號(hào)三角形符號(hào)三角形 7. 回溯算法的效率回溯算法的效率最大團(tuán)問題最大團(tuán)問題 無向圖無向圖G=(V,E). G的完全子圖稱為團(tuán)的完全子圖稱為團(tuán): 即即U V滿足滿足 u,v U, 都有都有(u,v) E 最大團(tuán)最大團(tuán): 頂點(diǎn)數(shù)最多的團(tuán)頂點(diǎn)數(shù)最多的團(tuán). 解

20、空間結(jié)構(gòu)解空間結(jié)構(gòu): 子集樹子集樹 backtrack(t)1. 若若 t n, 則判斷則判斷,記錄記錄bestn,x, 返回返回 2. 若若vt與與x1:t-1中已有的中已有的cn個(gè)點(diǎn)都相連個(gè)點(diǎn)都相連, 則則 3. xt=1, cn+, backtrack(t+1), cn-, xt=0 4. 若若cn+n-tbestn, 則則5. xt=0, backtrace(t+1) bestn: 目前最大團(tuán)頂點(diǎn)數(shù)目前最大團(tuán)頂點(diǎn)數(shù) cn: 當(dāng)前團(tuán)頂點(diǎn)數(shù)當(dāng)前團(tuán)頂點(diǎn)數(shù) 第第5章章 回溯法回溯法 1. 裝載問題裝載問題 2. 回溯回溯算法設(shè)計(jì)算法設(shè)計(jì)步驟步驟 3. 旅行旅行售貨員問題售貨員問題(TSP) 4

21、. n皇后皇后問題問題 5. 最大團(tuán)問題最大團(tuán)問題 6. 符號(hào)三角形符號(hào)三角形 7. 回溯算法的效率回溯算法的效率符號(hào)三角形符號(hào)三角形 由符號(hào)由符號(hào)“+”, “-”組成組成 第一行有第一行有n個(gè)符號(hào)個(gè)符號(hào) 2個(gè)同號(hào)下面是個(gè)同號(hào)下面是“+” 2個(gè)異號(hào)下面是個(gè)異號(hào)下面是“-” 右圖有右圖有14“+”, 14“-” 給定給定n, 求求“+”“-”個(gè)數(shù)相同的符號(hào)三角形個(gè)數(shù)個(gè)數(shù)相同的符號(hào)三角形個(gè)數(shù) 第一行第一行:子集樹子集樹(1+, 0-); 維護(hù)符號(hào)三角形維護(hù)符號(hào)三角形 限制條件限制條件: 0,1的個(gè)數(shù)都不能超過的個(gè)數(shù)都不能超過n(n+1)/4 + + - + - + + - - - - +- + +

22、 + - - + + - - + - - - +符號(hào)三角形符號(hào)三角形backtrack (t)1. 若若counthalf 或或 t(t-1)/2-counthalf, 返回返回 2. 若若tn, 記錄記錄, 返回返回 3. 對(duì)對(duì) i = 0 : 1, 4. p1t=i; count+=i;5. 對(duì)對(duì) j = 2 : t, 6. pjt-j+1=pj-1t-j+1pj-1t-j+2;7. count+=pjt-j+1;8. backtrack(t+1);9. 對(duì)對(duì) j = 2 : t, count-=pjt-j+1;10. count-=i; sum記記+-個(gè)數(shù)相同個(gè)數(shù)相同 的符號(hào)三角形個(gè)數(shù)的符號(hào)三角形個(gè)數(shù) 若若n(n+1)/2是奇數(shù)是奇數(shù) 則則sum=0. half = n(n+1)/4 p記錄符號(hào)三角形記錄符號(hào)三角形 p1t = xt 對(duì)對(duì)j=2:t, 依次計(jì)算依次計(jì)算 pjt-j+1 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 第第5章章 回溯法回溯法 1. 裝載問題裝載問題 2. 回溯回溯算法設(shè)計(jì)算法設(shè)計(jì)步驟步驟 3. 旅行旅行售貨員問題售貨員問題(TSP) 4. n皇后皇后問題問題 5. 最大團(tuán)問題最大團(tuán)問題 6. 符號(hào)三角形符號(hào)三角形 7. 回溯算法的效率回溯算法的效率回溯法的效率分析回溯法的效率分析影