[學習]算法設計與分析ch7treesearchingstrateg

1、第七章 Tree Searching Strategies,問題的定義輸入: n個布爾變量x1, x2, …., xn 關于x1, x2, …., xn的k個析取布爾式輸出: 是否存在一個x1, x2, …., xn的一種賦值 使得所有k個布爾析取式皆為真,布爾表達式可滿足性問題,把問題表示為樹通過不斷地為賦值集合分類來建立樹 (以三個變量(x1, x2, x3)為例)

2、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,x1=T,x1=F,x2=T,x2=F,x2=T,x2=F,x3=T,x3=T,x3=T,x3=T,x3=F,x3=F,x3=F,x3=F,求解問題設有布爾式: -x1, x1, x2? x5 , x3, -x2,,,,,,x1=T,x1=F,問題的定義輸入: 具有8個編號小方塊的魔方,8-Puzzle問題,輸出: 移動系列, 經(jīng)過這些移動, 魔方達如下狀態(tài),

3、轉(zhuǎn)換為樹搜索問題,,,Hamiltonian環(huán)問題,問題定義輸入: 具有n個節(jié)點的連通圖G=(V, E)輸出: G中是否具有Hamiltonian環(huán),沿著G的n條邊經(jīng)過每個節(jié)點一次, 并回到起始節(jié)點的環(huán)稱為G的一個Hamiltonian環(huán).,1,2,7,4,5,,,,,,,,,,3,,,,,,,,6,無Hamiltonian環(huán)圖:,有Hamiltonian環(huán)圖:,轉(zhuǎn)換為樹搜索問題,,,,,,,,,,,,1,3,4,5,7,5,6

4、,7,,,,,,,,,,,,,,,,,,,,3,2,6,5,2,4,7,4,5,7,4,7,3,7,6,5,3,2,6,2,6,1,1,,,,,,,,,,,1,2,3,4,5,4,4,5,3,3,5,7.2 Basic Tree Searching Strategies,Breadth-First SearchDepth-First Search,算法1. 構造由根組成的隊列Q；2. If Q的第一個元素x是目標節(jié)點 The

5、n 停止;3. 從Q中刪除x，把x的所有子節(jié)點加入Q的末尾;4. If Q空 Then 失敗 Else goto 2.,Breadth-First Search,例: 求解8-Puzzle問題,,,,,,,Depth-First Search,算法1. 構造一個由根構成的單元素棧S;2. If Top(S)是目標節(jié)點 Then 停止;3. Pop(S), 把Top(S)的所有子節(jié)點壓入棧頂;4.

6、 If S空 Then 失敗 Else goto 2.,,例1. 求解子集合和問題 輸入: S={7, 5, 1, 2, 10} 輸出: 是否存在S’?S, 使得Sum(S’)=9,,,,,,,0,7,8,12,9,10,18,7,5,1,2,2,10,例2. 求解Hamiltonian環(huán)問題,,,,,,,,,,,,,,,,,,,,,,,,1,4,5,2,2,3,5,6,5,3,3,

7、2,2,4,4,4,5,3,6,3,5,6,6,1,7.3 Optimal Tree Searching Strategies,Hill ClimbingBest-First Search StrategyBranch-and-Bound Strategy,基本思想在深度優(yōu)先搜索過程中, 我們經(jīng)常遇到多個節(jié)點可以擴展的情況, 首先擴展哪個?爬山策略使用貪心方法確定搜索的方向, 是優(yōu)化的深度優(yōu)先搜索策略爬山策略使用啟發(fā)式測度來排

8、序節(jié)點擴展的順序,Hill Climbing,用8-Puzzle問題來說明爬山策略的思想啟發(fā)式測度函數(shù): f(n)=W(n), W(n)是節(jié)點n中處于錯誤位置的方塊數(shù).例如, 如果節(jié)點n如下, 則f(n)=3, 因為方塊1、2、8處于錯誤位置.,,,,,,,,,,3,3,4,4,2,4,1,0,2,f(n) 值,Hill Climbing算法 1. 構造由根組成的單元素棧S; 2. If Top(S)是目標節(jié)點

9、 Then 停止; 3. Pop(S); 4. S的子節(jié)點按照其啟發(fā)測度由大到 小的順序壓入S; 5. If S空 Then 失敗 Else goto 2.,,基本思想 結合深度優(yōu)先和廣度優(yōu)先的優(yōu)點 根據(jù)一個評價函數(shù), 在目前產(chǎn)生的所有 節(jié)點中選擇具有最小評價函數(shù)值的節(jié) 點進行擴展. 具有全局優(yōu)化觀念, 而爬山策略僅具有局部 優(yōu)化觀念.,Best-First Se

10、arch Sttrategy,BesT-First Search算法 1. 使用評價函數(shù)構造一個堆H, 首先構造由根 組成的單元素堆; 2. If H的根r是目標節(jié)點 Then 停止; 3. 從H中刪除r, 把r的子節(jié)點插入H; 4. If H空 Then 失敗 Else goto 2. 8-Puzzle問題實例,,,,,3,4,4,,,3,,,,2,4,1,0,2,3,

11、4,,,基本思想上述方法很難用于求解優(yōu)化問題分支界限策略可以有效地求解組合優(yōu)化問題發(fā)現(xiàn)優(yōu)化解的一個界限縮小解空間, 提高求解的效率舉例說明分支界限策略的原理,Branch-and-Bound Strategy,多階段圖搜索問題輸入: 多階段圖,輸出: 從v0到v3的最短路徑,,,,,,,,,,,,,,,,,1,3,2,5,3,4,3,2,7,4,4,1,1,1,1,v0,v12,v11,v13,v22,v21,v23,

12、v21,v23,v22,v3,v3,v3,v3,v3,v3,問題的樹表示,,,,,,,,,,,,,1,3,2,5,3,4,3,2,7,1,1,v0,v12,v11,v22,v21,v23,v21,v23,v22,v3,v3,可能解上界=5,=6>5,=7>5,=6>5,=9>5,v13,解,,,使用爬山策略進行分支界限搜索,分支界限策略的原理產(chǎn)生分支的機制(使用前面的任意一種策略)產(chǎn)生一個界限(可以通過發(fā)現(xiàn)

13、可能解)進行分支界限搜索, 即剪除不可能產(chǎn)生優(yōu)化解的分支.,7.4 Personnel Assignment Problem,問題的定義轉(zhuǎn)換為樹搜索問題求解問題的分支界限搜索算法,輸入 人的集合P={P1, P2, …, Pn}, P1<P2< …<Pn 工作的集合J={J1, J2, …, Jn}, J是偏序集合 矩陣[Cij], Cij是工作Jj分配到Pi的代價 輸出 矩陣[Xij], Xi

14、j=1表示Pi被分配Jj , ?i,j CijXij最小 每個人被分配一種工作, 不同人分配不同工作 如果f(Pi)?f(Pj), 則Pi ? Pj,問題的定義,例. 給定P={P1, P2, P3} , J={J1, J2, J3}, J1?J3, J2?J3. P1?J1、P2?J2、P3?J3 是可能的解. P1?J1、P2?J3、P3?J2 不可能是解.,拓樸排序輸入: 偏序集合(S,

15、 ?) 輸出: S的拓樸序列是, 滿足: 如果si?sj, 則si排在sj的前面.例,轉(zhuǎn)換為樹搜索問題,拓樸排序:,s1,s3,s7,s4,s9,s5,s2,s8,s6,問題的解空間命題1. P1? Jk1、P2 ? Jk2、…、Pn ? Jkn是一個可能 解, 當且僅當Jk1、Jk2、…、Jkn必是一個拓樸 排序的序列.例. P={P1

16、, P2, P3, P4}, J={J1, J2, J3, J4}, J的偏序如下,則 (J1, J2, J3, J4)、(J1, J2, J4, J3 )、(J1, J3, J2, J4 )、 (J2, J1, J3, J4 )、(J2, J1, J4, J3 )是拓樸排序序列 (J1, J2, J4, J3)對應于P1?J1、P2?J2、P3 ? J4、P4

17、 ? J3,問題的解空間是所有拓樸排序的序列集合，每個序列對于一個可能的解,問題的樹表示(即用樹表示所有拓樸排序序列),拓樸序列樹的生成算法 輸入: 偏序集合S, 樹根root. 輸出: 由S的所有拓樸排序序列構成的樹. 1. 生成樹根root; 2. 選擇偏序集中沒有前序元素的所有元素, 作為 root的子節(jié)點; 3. For root的每個字節(jié)點v Do 4. S=

18、S-{v}; 5. 把v作為根, 遞歸地處理S.,,例,,,,,,,,,,,,,,,,0,1,2,2,3,1,3,4,2,3,4,3,4,4,3,4,,,,,,,,,,,計算解的代價的下界命題2. 把代價矩陣某行(列)的各元素減去同一個 數(shù), 不影響優(yōu)化解的求解.代價矩陣的每行(列)減去同一個數(shù)(該行或列的最小數(shù)), 使得每行和每列至少有一個零, 其余各元素非負.每行(列)減去的數(shù)的和即為

19、解的下界.,求解問題的分支界限搜索算法,-12,-26,-3,-10,-3,,解代價下界=12+26+3+10+3=54,例.,解空間的加權樹表示,分支界限搜索(使用爬山法)算法1. 建立根節(jié)點, 其權值為解代價下界;2. 使用爬山法, 類似于拓樸排序序列樹生成算法 求解問題, 每產(chǎn)生一個節(jié)點, 其權值為加工后的 代價矩陣對應元素加其父節(jié)點權值;3. 一旦發(fā)現(xiàn)一個可能解, 將其代價作為界限, 循環(huán) 地進行

20、分支界限搜索: 剪掉不能導致優(yōu)化解的 子解, 使用爬山法繼續(xù)擴展新增節(jié)點, 直至發(fā)現(xiàn) 優(yōu)化解.,,例,,,,,,,,0,1,2,1,3,4,3,4,54,71,58,64,68,70,70,73,分支被剪掉,{P1, P2, P3, P4},7.5 Traveling Salesperson Optimization Problem,問題的定義 轉(zhuǎn)換為樹搜索問題 分支界限搜索算法,問題的定義

21、,輸入: 無向連通圖G=(V, E), 每個節(jié)點都沒有到自身的邊, 每對節(jié)點之間都有一條非負加權邊.輸出: 一條由任意一個節(jié)點開始 經(jīng)過每個節(jié)點一次 最后返回開始節(jié)點的路徑, 該路徑的代價(即權值只和)最小.,,所有解集合作為樹根, 其權值由代價矩陣 使用上節(jié)方法計算;用爬山法遞歸地劃分解空間, 得到二叉樹

22、劃分過程: 如下選擇圖上滿足下列條件的邊(i, j)Cost(i, 1)=max{Cost(k,1) |?k?V}Cost(i, j)=0 使右子樹代價下界增加最大所有包含(i, j)的解集合作為左子樹所有不包含(i, j)的解集合作為右子樹計算出左右子樹的代價下界,轉(zhuǎn)換為樹搜索問題,分支界限搜索算法,在上述二叉樹建立算法中增加如下策略: 發(fā)現(xiàn)優(yōu)化解的上界?; 如果一個子節(jié)點的代價下界超過?, 則終止該 節(jié)點的

23、擴展. 下邊我們用一個例子來說明算法,,,構造根節(jié)點, 設代價矩陣如下,,根節(jié)點為所有解的集合 計算根節(jié)點的代價下界,- 3- 416 7 25 3 26,-7,-1,-4,變換后的代價矩陣為,,得到如下根節(jié)點及其代價下界,,構造根節(jié)點的兩個子節(jié)點選擇使子節(jié)點代價下界 增加最大的劃分邊(4, 6)建立根節(jié)點的子節(jié)點: 左子節(jié)點為包括邊(4, 6)的所有解集合左子節(jié)點為不包括邊(4, 6)的所有解集合

24、,計算左右子節(jié)點的代價下界(4, 6)的代價為0, 所以左節(jié)點代價下界仍為96.我們來計算右節(jié)點的代價下界:如果一個解不包含(4, 6), 它必包含一條從4出發(fā)的邊和 進入節(jié)點6的邊.由變換后的代價矩陣可知, 具有最小代價由4出發(fā)的邊為(4, 1), 代價為32.由變換后的代價矩陣可知, 具有最小代價進入6的邊為(5, 6), 代價為0.于是, 右節(jié)點代價下界為: 96+32+0=128.,目前的樹為,遞歸地構造左右子樹構

25、造左子樹根對應的代價矩陣 左子節(jié)點為包括邊(4, 6)的所有解集合, 所以矩陣的第4行和第6列應該被刪除由于邊(4, 6)被使用, 邊(6, 4)不能再使用, 所以代價矩陣的元素C[6, 4]應該設置為?.結果矩陣如下,計算左子樹根的代價下界矩陣的第5行不包含0第5行元素減3, 左子樹根代價下界為: 96+3=99結果矩陣如下,構造右子樹根對應的代價矩陣 右子節(jié)點為不包括邊(4, 6)的所有解集合, 只需要把

26、 C[4, 6]設置為? 結果矩陣如下,計算右子樹根的代價下界矩陣的第4行不包含0第4行元素減32, 右子樹根代價下界為: 128+32=160結果矩陣如下,目前的樹為,使用爬山策略擴展左子樹根選擇邊使子節(jié)點代價下界增加最大的劃分邊(3, 5)左子節(jié)點為包括邊(3, 5)的所有解集合右子節(jié)點為不包括邊(3, 5)的所有解集合計算左、右子節(jié)點的代價下界: 99和117目前樹擴展為:,L.B=96,包括邊(2, 1)

27、,不包括邊(2, 1),,,L.B=112,L.B=125,包括邊(1, 4),不包括邊(1, 4),,,L.B=126,L.B=153,包括邊(6, 7),不包括邊(6, 7),,,L.B=126,L.B=134,包括邊(5, 2),不包括邊(5, 2),,,L.B=126,空集合,包括邊(7, 3),不包括邊(7, 3),,,L.B=126,空集合,解:1-4-6-7-3-5-2-1代價: 126,由于右子樹代價下界=160

28、>126停止擴展,優(yōu)化解代價的上界,,i1,im,,j1,jn,,,X,,注 意如果i1-i2-…-im和j1-j2-…-jm已被包含在一個正在構造的路徑中, (im, j1)被加入, 則必須避免jn到 i1的路徑被加入. 否則出現(xiàn)環(huán).,7.6 The A* Algorithm,A*算法的基本思想A*算法的規(guī)則應用A*算法求解最短路徑問題,A*算法的基本思想,A*算法與分支界限策略的比較 分支界限策略是為了剪掉不能達到

29、優(yōu)化解的分支 分支界限策略的關鍵是“界限” A*算法的核心是告訴我們在某些情況下, 我們得 到的解一定是優(yōu)化解, 于是算法可以停止 A*算法試圖盡早地發(fā)現(xiàn)優(yōu)化解 A*算法經(jīng)常使用Best-first策略求解優(yōu)化問題,,A*算法關鍵—代價函數(shù) 對于任意節(jié)點ng(n)＝從樹根到n的代價h*(n)＝從n到目標節(jié)點的優(yōu)化路徑的代價f*(n)＝g(n) + h*(n)是節(jié)點n的代價 What is the v

30、alue of h*(n)?不知道！于是, f*(n)也不知道 估計h*(n)使用任何方法去估計h*(n), 用h(n)表示h*(n)的估計 h(n)?h*(n)總為真 f(n)=g(n)+h(n)?g(n)+h*(n)=f*(n)定義為n的代價,輸出: 發(fā)現(xiàn)一個從S到T的最短路徑,,例1. 最短路徑問題:輸入:,g(V1)=2, g(V2)=3, g(V3)=4 h*(V1)=5, f*(V1)=g(V1

31、)+h*(V1) =7,,估計h*(n) 從V1出發(fā)有兩種可能: 代價為2, 代價為3, 最小者為2h*(V1)?2, 選擇h(n)=2為h*(V1)的估計值f(V1)=g(v1)+h(V1)=4為V1的代價,,求解樹的第一階段,,A*算法本質(zhì)—已經(jīng)發(fā)現(xiàn)的解是優(yōu)化解 定理1. 使用Best-first策略搜索樹, 如果A*選擇的節(jié)點是 目標節(jié)點, 則該節(jié)點表示的解是優(yōu)化解. 證明.

32、 令n是任意擴展到的節(jié)點, t是選中目標節(jié)點. 往證f(t)=g(t)是優(yōu)化解代價. (1). A*算法使用Best-first策略, f(t)?f(n). (2). A*算法使用h(n)?h*(n)估計規(guī)則, f(t)?f(n)?f*(n). (3). {f*(n)}中必有一個為優(yōu)化解的代價, 令其為f*(s).

33、 我們有f(t) ?f*(s). (4). t是目標節(jié)點h(t)=0, 所以f(t)=g(t)+h(t)=g(t)?f*(s). (5). f(t)=g(t)是一個可能解, g(t)?f*(s), f(t)=g(t)=f*(s).,A*算法的規(guī)則,(1). 使用Best-first策略搜索樹;(2). 節(jié)點n的代價函數(shù)為f(n)=g(n)+h(n), g(n)

34、是 從根到n的路徑代價, h(n)是從n到某個目 標節(jié)點的優(yōu)化路徑代價;(3). 對于所有n, h(n)?h*(n);(4). 當選擇到的節(jié)點是目標節(jié)點時, 算法停止, 返回一個優(yōu)化解.,應用A*算法求解最短路徑問題,問題的輸入:,A*算法的執(zhí)行全過程,,Step 1,g(V1)=2g(V3)=4g(V2)=3,h(V1)=min{2,3}=2h(V3)=min{2}=2h(V2

35、)=min{2,2}=2,f(V1)=2+2=4f(V3)=4+2=6f(V2)=2+2=5,4,6,5,1,,Step 2. 擴展V1,g(V4)=2+2=4g(V2)=2+3=5,h(V4)=min{3,1}=1h(V2)=min{2, 2}=2,f(V4)=4+1=5f(V2)=5+2=7,S,V3,V2,,,,2,4,3,4,6,5,V4,V2,,,V1,2,3,1,5,7,,Step 3. 擴展V2,g(V4)=3+

36、2=5g(V5)=3+2=5,h(V4)=min{3,1}=1h(V5)=min{5}=5,f(V4)=5+1=6f(V2)=5+5=10,S,V3,,,,2,4,3,4,6,5,V4,V2,,,V1,2,3,1,5,7,V4,V5,2,2,,,V2,6,10,,Step 4. 擴展V4,g(V5)=2+2+1=5g(T) =2+2+3=7,h(V5)=min{5}=5h(T)=0,f(V5)=5+5=10f(V2)=7+0

37、=7,S,V3,,,,2,4,3,4,6,5,V2,,,V1,2,3,1,5,7,V4,V5,2,2,,,V2,6,10,V5,T,1,3,,,V4,7,10,,Step 5. 擴展V3,g(V5)=4+2=6,h(V5)=min{5}=5,f(V5)=6+5=11,S,V3,,,,2,4,3,6,5,1,V5,,2,11,,Step 6. 擴展V4,g(V5)=3+2+1=6g(T) =3+2+3=8,h(V5)=min{5}=5