計算機算法基礎(第七章)課件

1、計算機算法基礎(第七章)計算機算法基礎(第七章)0 預備知識問題狀態(tài)解狀態(tài)狀態(tài)空間答案狀態(tài)狀態(tài)空間樹活結點E-結點死結點等等本節(jié)主要目的通過對n-皇后問題的分析，學習以上概念，并且了解回溯法0 預備知識問題狀態(tài)狀態(tài)空間樹等等n-皇后問題描述將n個皇后放置在一個nn的棋盤上，要求沒有兩個皇后可以互相攻擊。攻擊的定義：兩個皇后出現在同一行、或同一列、或者同一條斜線上都視為出現了攻擊。n-皇后問題描述將n個皇后放置在一個nn的棋盤上，要求沒有8-皇后問題的一個解1234567812345678該解的8元組表示:(4,6,8,2,7,1,3,5) 8-皇后問題的一個解1234567812345678該

2、解的8n-皇后問題用n-元組(x1,x2,xn)表示棋盤上皇后的位置狀態(tài)下標表示皇后i (i=1,2,n)xi表示放置皇后i所在的列號顯式約束條件：每個xi只從集合Si=1,2,n取值滿足顯式約束的所有元組確定一個可能的解空間 解空間由nn個n-元組組成隱式約束條件沒有兩個xi可以相同，而且沒有兩個皇后可以在同一條斜線上 由前者得，所有解都是n-元組(1,2,n)的置換，因此，解空間縮小為 n！個元組n-皇后問題用n-元組(x1,x2,xn)表示棋盤上皇后4-皇后問題解空間的樹結構結點按深度優(yōu)先檢索編號葉子結點有4！ 24個 4-皇后問題解空間的樹結構結點按深度優(yōu)先檢索編號解空間樹結構的術語樹

3、中每個結點確定求解問題的一個問題狀態(tài)(problem state)由根結點到其它結點的所有路徑確定了這個問題的狀態(tài)空間(state space)解狀態(tài)(solution states)是這樣一些問題狀態(tài)S，對于這些問題狀態(tài)，由根到S的那條路徑確定了這解空間中的一個元組（滿足顯式約束）答案狀態(tài)(solution states)是這樣一些解狀態(tài)S，由根到S的路徑確定了問題的一個解（滿足隱式約束）解空間的樹結構為狀態(tài)空間樹(state space tree)解空間樹結構的術語樹中每個結點確定求解問題的一個問題狀態(tài)(p利用狀態(tài)空間樹解題1 設想狀態(tài)空間樹2 生成問題狀態(tài)3 確定問題狀態(tài)中哪些是解狀態(tài)4

4、 哪些解狀態(tài)是答案狀態(tài)生成問題狀態(tài) 構造狀態(tài)空間樹利用狀態(tài)空間樹解題1 設想狀態(tài)空間樹狀態(tài)空間樹術語活結點：自己已經生成而其所有的兒子結點還沒有全部生成的結點。E-結點（正在擴展的結點）：當前正在生成其兒子結點的活結點。死結點：不再進一步擴展或者其兒子結點已全部生成的生成結點。靜態(tài)樹(static trees)：樹結構與所要解決的問題的實例無關。動態(tài)樹(dynamic trees)：根據不同的實例而使用不同的樹結構。狀態(tài)空間樹術語活結點：自己已經生成而其所有的兒子結點還沒有全構造狀態(tài)空間樹的兩個方法回溯法當前E-結點R，生成一個新的兒子C，則C就變成一個新的E-結點，對子樹C完全檢測后，R結點

5、再次成為E-結點分枝-限界方法一個E-結點一直保持到變成死結點為止限界函數以上兩種方法都使用限界函數殺死還沒有全部生成其兒子結點的那些活結點構造狀態(tài)空間樹的兩個方法回溯法4-皇后問題的限界函數如果(x1, x2, , xi)是到當前E-結點的路徑，那么具有父-子標記xi+1的所有兒子結點是一些這樣的結點，它們使得(x1, x2, , xi+1)表示沒有兩個皇后正在互相攻擊的一種棋盤格局。4-皇后問題的限界函數如果(x1, x2, , xi)是到4-皇后問題-回溯解 1 2 3 412344-皇后問題-回溯解 1 24-皇后問題回溯法vs狀態(tài)空間樹結點按深度優(yōu)先檢索編號葉子結點有4！ 24個 4

6、-皇后問題回溯法vs狀態(tài)空間樹結點按深度優(yōu)先檢索編號4-皇后問題回溯期間的生成樹4-皇后問題回溯期間的生成樹分枝限界法在生成當前E-結點全部兒子之后再生成其它活結點的兒子并且，用限界函數幫助避免生成不包含答案結點子樹的狀態(tài)空間FIFO檢索：活結點表采用隊LIFO檢索：活結點表采用棧分枝限界法在生成當前E-結點全部兒子之后再生成其它活結點的FIFO分枝限界法例7.1（4-皇后問題）FIFO分枝限界法例7.1（4-皇后問題）4-皇后問題回溯 vs FIFO分枝-限界回溯Win！4-皇后問題回溯 vs FIFO分枝-限界回溯LC-檢索（Least Cost）分枝-限界失敗的原因對下一個E-結點的選擇

7、規(guī)則過于死板如何解決？排序，讓答案結點排在前面！尋找一種“有智力”的排序函數C()，該函數能夠讓答案結點盡早生成排序的標準下一個E-結點應當是生成答案結點花費成本最小的結點，因此C()又稱作結點成本函數。LC：Least CostLC-檢索（Least Cost）分枝-限界失敗的原因LC-檢索（結點成本）一：在生成一個答案結點之前，子樹X需要生成的結點數。二：在子樹X中離X最近的那個答案結點到X的路徑長度。以圖7.1為例節(jié)點1、18、34、29、35、30、38可計算其他結點可得到一個范圍生成結點（12 18 34 5019 24 2930 3231）LC-檢索（結點成本）一：在生成一個答案結

8、點之前，子樹X需要LC-檢索（結點成本函數）C()定義如果X是答案結點，則C(X)是由狀態(tài)空間樹的根結點到X的成本（即花費的代價，可以是級數、計算復雜度等）如果X不是答案結點且子樹X不包含任何答案結點，則C(X)如果X不是答案結點但子樹X包含答案結點，則C(X)等于子樹X中具有最小成本的答案結點的成本LC-檢索（結點成本函數）C()定義LC-檢索（成本估計函數）從前面的兩個成本度量標準看， 計算C()的工作量與原問題的解具有相同復雜度。因此需要成本估計函數g(X)出現的新問題僅利用g(X) 會導致算法偏向縱深檢查，無法有效處理下面這種情況：即g(W)=g(Y)，LC分枝-限界檢索：伴之有限界函

9、數的LC-檢索LC分枝-限界檢索c(X) f (h(X) + g(15-謎問題（問題描述）134152512761114891013123456789101112131415通過一系列合法移動將初始排列轉換成目標排列。合法移動：將鄰接于空格的牌移動到空格。目標排列一種初始排列15-謎問題（問題描述）13415251276111489115-謎問題（是否有解）棋盤存在16！種不同排列任一初始狀態(tài)，可到達的狀態(tài)為這些排列中的一半在求解問題前，需要判定目標狀態(tài)是否在初始狀態(tài)的狀態(tài)空間中15-謎問題（是否有解）棋盤存在16！種不同排列15-謎問題（判定方法）按目標狀態(tài)給牌編號，空格為16用POSITI

10、ON(i)記錄編號為i的牌在初始狀態(tài)中的位置； POSITION(16)表示空格圖7.2(a)的POSITION(1 5 2 3 7 10 9 13 14 15 11 8 16 12 4 6)LESS(i)是使得牌j小于牌i且POSITION(j) POSITION(i)的數目LESS(1)=0; LESS(4)=1; LESS(12)=615-謎問題（判定方法）按目標狀態(tài)給牌編號，空格為1615-謎問題（判定方法）定理7.1 當且僅當sum(LESS(i) + X)是偶數時，目標狀態(tài)可由此初始狀態(tài)到達X1：空格恰好在上圖棋盤中的藍色格子上X0：空格在棋盤中的白色格子上15-謎問題（判定方法）

11、定理7.1 當且僅當sum(LESS15-謎問題(寬度優(yōu)先)15-謎問題(寬度優(yōu)先)15-謎問題(深度優(yōu)先)15-謎問題(深度優(yōu)先)15-謎問題（“智能”方法）針對不同實例用相同規(guī)則檢索，過于呆板和盲目是否能夠找到一種“智能”方法，給每個結點賦予成本值:如果結點在根結點到最近目標結點路徑上，則成本為這條路徑的長度：C(1)=C(4)=C(10)=C(23)=3否則，成本為檢索時殺死成本為的結點該方法的實際可操作性？15-謎問題（“智能”方法）針對不同實例用相同規(guī)則檢索，過于15-謎問題（成本估計值函數）C(X) = f(X) + g(X)f(X)：根到結點X的路徑長度1）g(X) ：是子樹X中

12、，由X到目標狀態(tài)的最短路徑長度的估計值2）狀態(tài)X轉換成目標狀態(tài)所需的最小移動數3）g(X) = 不在其目標位置的非空白牌數目；該值應該比2）要小 C(X) 是C(X)的下界15-謎問題（成本估計值函數）C(X) = f(X) +15-謎問題（使用C(X)的LC-檢索）555355315-謎問題（使用C(X)的LC-檢索）5553553LC-檢索的抽象化控制line procedure LC(T, c) /為找答案結點檢索T0 if T是答案結點 then 輸出T; return endif1 E T2 將活結點表初始化為空3 loop4 for E的每個兒子X do5 if X是答案結點 th

13、en 輸出從X到T的路徑6 return7 endif8 call ADD(X) /X是新的活結點9 PARENT(X) E /指示到根的路徑10 repeat (Continue)X加入到活結點表中LC-檢索的抽象化控制line procedure LC(TLC-檢索的抽象化控制 loop11 if 不再有活結點 then print(“no answer code”)12 stop13 endif14 call LEAST(E)15 repeat16 end LC從活結點表中刪除具有最小c值的活結點，并且將該結點賦給ELC-檢索的抽象化控制 loop從活結點表中刪除具有LC-檢索的抽象化控

14、制（正確性證明）過程略結論對于有限狀態(tài)空間樹，以及存在答案結點的無限狀態(tài)空間樹，算法能夠終止對于沒有答案結點的無限狀態(tài)空間樹，LC不會終止檢索局限在尋找估計成本不大于某個給定的限界C的答案結點是可取的LC-檢索的抽象化控制（正確性證明）過程略LC-檢索的抽象化控制（vs. BFS, D-Search）LC算法與BFS及D-Search基本相同活結點表采用隊列 vs BFS活節(jié)點表采用棧 vs D-Search不同：活結點表的構造，即下一個E-結點的選擇規(guī)則不同。LC-檢索的抽象化控制（vs. BFS, D-SearchLC-檢索的特性LC是否一定找得到具有最小成本的答案結點呢？否LC-檢索的特

15、性LC是否一定找得到具有最小成本的答案結點呢？LC-檢索的特性定理7.2定理7.2 在有限狀態(tài)空間樹T中，對于每一個結點X，令c(X)是c(X)的估計值且具有以下性質：對于每一對結點Y、Z，當且僅當c(Y)c(Z)時有c(Y)c(Z)。那么在使c( )作為c( )的估計值時，算法LC到達一個最小的成本答案結點終止。LC-檢索的特性定理7.2定理7.2 在有限狀態(tài)空間樹T中LC-檢索的特性 定理7.2的證明略LC-檢索的特性 定理7.2的證明略LC-檢索的特性 找最小成本答案結點line procedure LC1(T, c) /為找最小成本答案結點的LC-檢索0 if T是答案結點 then

16、輸出T; return endif1 E T2 將活結點表初始化為空3 loop3 if E是答案結點 then 輸出從E到T的路徑 return end if4 for E的每個兒子X do5 if X是答案結點 then 輸出從X到T的路徑6 return7 endif8 call ADD(X) /X是新的活結點9 PARENT(X) E /指示到根的路徑10 repeat (Continue)LC-檢索的特性 找最小成本答案結點line procLC-檢索的特性 找最小成本答案結點 loop11 if 不再有活結點 then print(“no answer code”)12 stop1

17、3 endif14 call LEAST(E)15 repeat16 end LC1LC-檢索的特性 找最小成本答案結點 loopLC-檢索的特性 定理7.3定理7.3 令c()是滿足如下條件的函數，在狀態(tài)空間樹T中，對于每一個結點X，有c(X)=c(X)，而對于T中的每一個答案結點X，有c(X)=c(X)。如果算法在第3行終止，則所找到的答案結點是具有最小成本的答案結點。證明略LC-檢索的特性 定理7.3定理7.3 令c()是滿分枝-限界算法限界的目的減少算法的盲目性，減小搜索空間，從而降低計算量下界使用使得c(X) U的所有活結點X可以被殺死分枝-限界算法限界的目的分枝-限界算法(解最優(yōu)化

18、問題)一般化的帶限期的作業(yè)排序問題假定n個作業(yè)和一臺處理機作業(yè)i對應一個三元組（pi,di,ti）ti表示作業(yè)i需要的單位處理時間di表示完成期限pi表示期限內未完成招致的罰款目標：從n個作業(yè)選取子集J，要求J中所有作業(yè)都能在各自期限內完成并且使得不在J中的作業(yè)招致的罰款總額最小分枝-限界算法(解最優(yōu)化問題)一般化的帶限期的作業(yè)排序問題分枝-限界算法(實例)n = 4; (p1,d1,t1) = (5,1,1); (p2,d2,t2) = (10,3,2); (p3,d3,t3) = (6,2,1); (p4,d4,t4) = (3,1,1);下界函數m=maxi|iSX上界U分枝-限界算法(

19、實例)n = 4;下界函數狀態(tài)空間樹動態(tài)元組狀態(tài)空間樹動態(tài)元組狀態(tài)空間樹靜態(tài)元組狀態(tài)空間樹靜態(tài)元組找最小成本答案結點的FIFO分枝-限界方法如何處理c(X) = U的情況為什么要處理？如何處理？引進，當u(X) u(Y)時， u(X) u(X) + u(Y)。在算法中，比較c(X) 與U的時候，可以對U作以下處理：當U是成本值，則不變當U由一單純上界得出，U= u(X) + 找最小成本答案結點的FIFO分枝-限界方法如何處理c(XFIFO分枝-限界算法FIFOBBline procedure FIFOBB(T, c, u, cost) / 為找出最小成本答案結點檢索T 假定T至少包含一個解結點

20、且 c(X) = c(X) = u(X)1 E T; PARENT(E) 0;2 if T是解結點 then U min(cost(T), u(T) + ); ans T3 else U u(T) + ; ans 04 Endif5 將隊列置初值為空 （Continue）FIFO分枝-限界算法FIFOBBline procedurFIFO分枝-限界算法(續(xù)1)6 loop7 for E的每個兒子X do8 if c(X) U then call ADDQ(X); PARENT(X) E 9 case10 :X是解結點 and cost(X)U:11 U min(cost(T), u(T) +

21、); 12 ans X13 : u(X)+ U: U u(X)+ 14 endcase15 endif16 repeat（Continue）FIFO分枝-限界算法(續(xù)1)6 loopFIFO分枝-限界算法(續(xù)2)17 loop /得到下一個E-結點18 if 隊列為空 then print(least cost=, U)19 while ans 0 do 20 print(ans)21 ans PARENT(ans)22 repeat23 return24 endif 25 call DELETEQ(X)26 if c(X) =U19 then print(least cost=, U)20

22、while ans0 do21 print(ans)22 ans PARENT(ans)23 repeat24 return 25 endif26 call LEAST(X)27 repeat28end LCBBLC分枝-限界的抽象化控制LCBB18 if 不再效率分析上下界函數的選擇是決定分枝-限界算法效率的主要因素對U選擇一個更好的初值是否能減少所生成的結點數？（否，根據定理7.4）擴展一些c()U的結點是否能減少所生成的結點數？（否，根據定理7.5）假定有兩個成本估計函數c1()和c2()，對于狀態(tài)空間樹的每一個結點X，若有c1()=c2()=c(X)，則稱c2()比c1()好。是否用較

23、好的成本估計函數生成的結點數要少呢？（否，根據定理7.6和定理7.7）效率分析上下界函數的選擇是決定分枝-限界算法效率的主要因素0/1背包問題描述極小化約束條件 xi=0 或xi=1，1=i=n 0/1背包問題描述極小化0/1背包問題的函數定義c(X)= （答案結點） c(X)= （不可行的結點）c(X)=minc(LCHILD(X), c(RCHILD(X)c(X)= - Bound( , , j-1, M)U(X) = - Bound( , , j-1, M)其中j是結點X所在的層級0/1背包問題的函數定義c(X)= 例7.2n=4, M=15(p1, p2, p3, p4) = (10,

24、 10, 12, 18)(w1, w2, w3, w4) = (2, 4, 6, 9)例7.2n=4, M=15例7.2的LC分枝 限界樹上面的數c下面的數u大小固定元組例7.2的LC分枝 限界樹上面的數c大小固定元組LCBB求解背包問題分析狀態(tài)空間樹中結點的結構如何生成一給定結點的兒子如何識別答案結點如何表示活結點表LCBB求解背包問題分析狀態(tài)空間樹中結點的結構狀態(tài)空間樹中結點的結構PARENT父結點鏈接指針LEVEL狀態(tài)空間樹中的級數TAGXi的取值CU背包的剩余空間PE已裝入物品的效益值的和UBc(X)狀態(tài)空間樹中結點的結構PARENT如何生成一給定結點的兒子左兒子生成PARENT(Y)

25、 = XLEVEL(Y) = LEVEL(X) + 1CU(Y) = CU(X) WLEVEL(X)PE(Y) = PE(X) + P LEVEL(X)TAG = 1UB(Y) = UB(X)如何生成一給定結點的兒子左兒子生成如何識別答案結點當且僅當LEVEL(X) = n 1X是答案結點如何識別答案結點當且僅當LEVEL(X) = n 1如何表示活結點表Min-堆測試活結點表是否為空常量時間加結點到活結點表 log(n)刪除最小UB值的結點 log(n)如何表示活結點表Min-堆計算上界和下界的算法line procedure LUBOUND(P, W, rw, cp, N, k, LBB,

26、 UBB)1 LBB cp; c rw;2 for i k to N do 3 if c=W(j) then c c-W(j) 6 LBB LBB+P(j)7 endif8 repeat9 return10 endif11 c c-W(i); LBB LBB+P(i)12 repeat13 UBB LBB14 end LUBOUND計算上界和下界的算法line procedure LUBOU生成一個新結點line procedure NEWNODE(par, lev, t, cap, prof, ub)1 call GETNODE(I)2 PARENT(I) par； LEVEL(i) lev

27、；TAG(I) t3 CU(I) cap；PE(I) prof；UB(I) ub4 call ADD(I)5 end NEWNODE生成一個新結點line procedure NEWNODE(背包問題的LC分枝-限界算法line procedure LCKNAP(P, W, M, N, )/ 大小固定元組表示狀態(tài)空間樹/ 假設P(1)/W(1)=P(2)/W(2)=P(N)/W(N) real P(N), W(N), M, L, LBB, UBB, cap, prof int ANS, X, N1 call INIT2 call GETNODE(E) 3 PARENT(E) 0; LEVEL(e) 1; CU(E) M; PE(E) 04 call LUBOUND(P, W, M, N, 0, 1, LBB, UBB)5 L LBB - ; UB(E) UBB 6 loop7 i LEVEL(E); cap CU(E); prof PE(E)背包問題的LC分枝-限界算法lin