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

1、計算機算法基礎(chǔ)(第七章)計算機算法基礎(chǔ)(第七章)0 預(yù)備知識問題狀態(tài)解狀態(tài)狀態(tài)空間答案狀態(tài)狀態(tài)空間樹活結(jié)點E-結(jié)點死結(jié)點等等本節(jié)主要目的通過對n-皇后問題的分析，學習以上概念，并且了解回溯法0 預(yù)備知識問題狀態(tài)狀態(tài)空間樹等等n-皇后問題描述將n個皇后放置在一個nn的棋盤上，要求沒有兩個皇后可以互相攻擊。攻擊的定義：兩個皇后出現(xiàn)在同一行、或同一列、或者同一條斜線上都視為出現(xiàn)了攻擊。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-皇后問題解空間的樹結(jié)構(gòu)結(jié)點按深度優(yōu)先檢索編號葉子結(jié)點有4！ 24個 4-皇后問題解空間的樹結(jié)構(gòu)結(jié)點按深度優(yōu)先檢索編號解空間樹結(jié)構(gòu)的術(shù)語樹

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

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

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

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

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

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

9、數(shù)的LC-檢索LC分枝-限界檢索c(X) f (h(X) + g(15-謎問題（問題描述）134152512761114891013123456789101112131415通過一系列合法移動將初始排列轉(zhuǎn)換成目標排列。合法移動：將鄰接于空格的牌移動到空格。目標排列一種初始排列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)的數(shù)目LESS(1)=0; LESS(4)=1; LESS(12)=615-謎問題（判定方法）按目標狀態(tài)給牌編號，空格為1615-謎問題（判定方法）定理7.1 當且僅當sum(LESS(i) + X)是偶數(shù)時，目標狀態(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ī)則檢索，過于呆板和盲目是否能夠找到一種“智能”方法，給每個結(jié)點賦予成本值:如果結(jié)點在根結(jié)點到最近目標結(jié)點路徑上，則成本為這條路徑的長度：C(1)=C(4)=C(10)=C(23)=3否則，成本為檢索時殺死成本為的結(jié)點該方法的實際可操作性？15-謎問題（“智能”方法）針對不同實例用相同規(guī)則檢索，過于15-謎問題（成本估計值函數(shù)）C(X) = f(X) + g(X)f(X)：根到結(jié)點X的路徑長度1）g(X) ：是子樹X中

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

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

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

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

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

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

18、問題)一般化的帶限期的作業(yè)排序問題假定n個作業(yè)和一臺處理機作業(yè)i對應(yīng)一個三元組（pi,di,ti）ti表示作業(yè)i需要的單位處理時間di表示完成期限pi表示期限內(nèi)未完成招致的罰款目標：從n個作業(yè)選取子集J，要求J中所有作業(yè)都能在各自期限內(nèi)完成并且使得不在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);下界函數(shù)m=maxi|iSX上界U分枝-限界算法(

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

20、且 c(X) = c(X) = u(X)1 E T; PARENT(E) 0;2 if T是解結(jié)點 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是解結(jié)點 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-結(jié)點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 不再效率分析上下界函數(shù)的選擇是決定分枝-限界算法效率的主要因素對U選擇一個更好的初值是否能減少所生成的結(jié)點數(shù)？（否，根據(jù)定理7.4）擴展一些c()U的結(jié)點是否能減少所生成的結(jié)點數(shù)？（否，根據(jù)定理7.5）假定有兩個成本估計函數(shù)c1()和c2()，對于狀態(tài)空間樹的每一個結(jié)點X，若有c1()=c2()=c(X)，則稱c2()比c1()好。是否用較

23、好的成本估計函數(shù)生成的結(jié)點數(shù)要少呢？（否，根據(jù)定理7.6和定理7.7）效率分析上下界函數(shù)的選擇是決定分枝-限界算法效率的主要因素0/1背包問題描述極小化約束條件 xi=0 或xi=1，1=i=n 0/1背包問題描述極小化0/1背包問題的函數(shù)定義c(X)= （答案結(jié)點） c(X)= （不可行的結(jié)點）c(X)=minc(LCHILD(X), c(RCHILD(X)c(X)= - Bound( , , j-1, M)U(X) = - Bound( , , j-1, M)其中j是結(jié)點X所在的層級0/1背包問題的函數(shù)定義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分枝 限界樹上面的數(shù)c下面的數(shù)u大小固定元組例7.2的LC分枝 限界樹上面的數(shù)c大小固定元組LCBB求解背包問題分析狀態(tài)空間樹中結(jié)點的結(jié)構(gòu)如何生成一給定結(jié)點的兒子如何識別答案結(jié)點如何表示活結(jié)點表LCBB求解背包問題分析狀態(tài)空間樹中結(jié)點的結(jié)構(gòu)狀態(tài)空間樹中結(jié)點的結(jié)構(gòu)PARENT父結(jié)點鏈接指針LEVEL狀態(tài)空間樹中的級數(shù)TAGXi的取值CU背包的剩余空間PE已裝入物品的效益值的和UBc(X)狀態(tài)空間樹中結(jié)點的結(jié)構(gòu)PARENT如何生成一給定結(jié)點的兒子左兒子生成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)如何生成一給定結(jié)點的兒子左兒子生成如何識別答案結(jié)點當且僅當LEVEL(X) = n 1X是答案結(jié)點如何識別答案結(jié)點當且僅當LEVEL(X) = n 1如何表示活結(jié)點表Min-堆測試活結(jié)點表是否為空常量時間加結(jié)點到活結(jié)點表 log(n)刪除最小UB值的結(jié)點 log(n)如何表示活結(jié)點表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生成一個新結(jié)點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生成一個新結(jié)點line procedure NEWNODE(背包問題的LC分枝-限界算法line procedure LCKNAP(P, W, M, N, )/ 大小固定元組表示狀態(tài)空間樹/ 假設(shè)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