算法設(shè)計與分析ch7 Tree searching strateg

第七章

TreeSearchingStrategies問題的定義輸入:n個布爾變量x1,x2,….,xn

關(guān)于x1,x2,….,xn的k個析取布爾式輸出:是否存在一個x1,x2,….,xn的一種賦值使得所有k個布爾析取式皆為真布爾表達(dá)式可滿足性問題把問題表示為樹通過不斷地為賦值集合分類來建立樹

(以三個變量(x1,x2,x3)為例)x1=Tx1=Fx2=Tx2=Fx2=Tx2=Fx3=Tx3=Tx3=Tx3=Tx3=Fx3=Fx3=Fx3=F求解問題設(shè)有布爾式:-x1,x1,x2x5,x3,-x2x1=Tx1=F問題的定義輸入:具有8個編號小方塊的魔方

8-Puzzle問題

23514786

輸出:移動系列,

經(jīng)過這些移動,

魔方達(dá)如下狀態(tài)12845673轉(zhuǎn)換為樹搜索問題235147862514786323517864Hamiltonian環(huán)問題問題定義輸入:具有n個節(jié)點的連通圖G=(V,E)輸出:G中是否具有Hamiltonian環(huán)沿著G的n條邊經(jīng)過每個節(jié)點一次,并回到起始節(jié)點的環(huán)稱為G的一個Hamiltonian環(huán).127453612435無Hamiltonian環(huán)圖:有Hamiltonian環(huán)圖:轉(zhuǎn)換為樹搜索問題134575673265247457473765326261112745361234544533512435

7.2BasicTreeSearchingStrategiesBreadth-FirstSearchDepth-FirstSearch算法1.構(gòu)造由根組成的隊列Q；2.

IfQ的第一個元素x是目標(biāo)節(jié)點Then停止;3.從Q中刪除x，把x的所有子節(jié)點加入Q的末尾;4.IfQ空Then失敗Elsegoto2.Breadth-FirstSearch例:

求解8-Puzzle問題21845673218456732184567321845673218456732184567321845673Depth-FirstSearch

算法1.

構(gòu)造一個由根構(gòu)成的單元素棧S;2.IfTop(S)是目標(biāo)節(jié)點Then停止;3.Pop(S),把Top(S)的所有子節(jié)點壓入棧頂;4.IfS空Then失敗Elsegoto2.例1.求解子集合和問題

輸入:S={7,5,1,2,10}

輸出:是否存在S’S,使得Sum(S’)=907812910187512210例2.求解Hamiltonian環(huán)問題125436145223565332244453635661

7.3OptimalTreeSearchingStrategies

HillClimbingBest-FirstSearchStrategyBranch-and-BoundStrategy基本思想在深度優(yōu)先搜索過程中,我們經(jīng)常遇到多個節(jié)點可以擴(kuò)展的情況,首先擴(kuò)展哪個?爬山策略使用貪心方法確定搜索的方向,是優(yōu)化的深度優(yōu)先搜索策略爬山策略使用啟發(fā)式測度來排序節(jié)點擴(kuò)展的順序HillClimbing用8-Puzzle問題來說明爬山策略的思想啟發(fā)式測度函數(shù):f(n)=W(n),W(n)是節(jié)點n中處于錯誤位置的方塊數(shù).例如,如果節(jié)點n如下,則f(n)=3,因為方塊1、2、8處于錯誤位置.8214567321845673218456732184567321845673218456732184567321845673218456732184567321845673334424102f(n)值HillClimbing算法

1.

構(gòu)造由根組成的單元素棧S;2.IfTop(S)是目標(biāo)節(jié)點Then停止;3.Pop(S);4.S的子節(jié)點按照其啟發(fā)測度由大到小的順序壓入S;5.IfS空Then失敗Elsegoto2.基本思想結(jié)合深度優(yōu)先和廣度優(yōu)先的優(yōu)點

根據(jù)一個評價函數(shù),在目前產(chǎn)生的所有節(jié)點中選擇具有最小評價函數(shù)值的節(jié)點進(jìn)行擴(kuò)展.

具有全局優(yōu)化觀念,而爬山策略僅具有局部優(yōu)化觀念.Best-FirstSearchSttrategyBesT-FirstSearch算法

1.使用評價函數(shù)構(gòu)造一個堆H,首先構(gòu)造由根組成的單元素堆;2.IfH的根r是目標(biāo)節(jié)點Then停止;3.從H中刪除r,把r的子節(jié)點插入H;4.IfH空Then失敗Elsegoto2.8-Puzzle問題實例21845673218456732184567321845673344218456733218456732184567321845673218456732184567324102218456733218456734基本思想上述方法很難用于求解優(yōu)化問題分支界限策略可以有效地求解組合優(yōu)化問題發(fā)現(xiàn)優(yōu)化解的一個界限縮小解空間,提高求解的效率舉例說明分支界限策略的原理Branch-and-BoundStrategy多階段圖搜索問題輸入:多階段圖輸出:從v0到v3的最短路徑v0v11v12v13v21v22v23v3132235347411v0v11v12v13v21v22v23v3132235347411132534327441111v0v12v11v13v22v21v23v21v23v22v3v3v3v3v3v3問題的樹表示v0v11v12v13v21v22v23v313223534741113253432711v0v12v11v22v21v23v21v23v22v3v3可能解上界=5=6>5=7>5=6>5=9>5v13解使用爬山策略進(jìn)行分支界限搜索分支界限策略的原理產(chǎn)生分支的機(jī)制(使用前面的任意一種策略)產(chǎn)生一個界限(可以通過發(fā)現(xiàn)可能解)進(jìn)行分支界限搜索,即剪除不可能產(chǎn)生優(yōu)化解的分支.7.4

PersonnelAssignmentProblem

問題的定義轉(zhuǎn)換為樹搜索問題求解問題的分支界限搜索算法輸入

人的集合P={P1,P2,…,Pn},P1<P2<…<Pn

工作的集合J={J1,J2,…,Jn},J是偏序集合矩陣[Cij],Cij是工作Jj分配到Pi的代價

輸出

矩陣[Xij],Xij=1表示Pi被分配Jj,i,jCijXij最小每個人被分配一種工作,不同人分配不同工作如果f(Pi)f(Pj),則PiPj問題的定義例.

給定P={P1,P2,P3},

J={J1,J2,J3},J1J3,J2J3.

P1J1、P2J2、P3J3是可能的解.

P1J1、P2J3、P3J2不可能是解.

拓樸排序輸入:偏序集合(S,)

輸出:S的拓樸序列是<s1,s2,…,sn>,

滿足:如果sisj,則si排在sj的前面.例轉(zhuǎn)換為樹搜索問題s6s5s4s3s2s1s9s8s7拓樸排序:s1s3s7s4s9s5s2s8s6問題的解空間命題1.P1Jk1、P2

Jk2、…、Pn

Jkn是一個可能解,當(dāng)且僅當(dāng)Jk1、Jk2、…、Jkn必是一個拓樸排序的序列.例.P={P1,P2,P3,P4},J={J1,J2,J3,J4},J的偏序如下J1J2J3J4

則(J1,J2,J3,J4)、(J1,J2,J4,J3)、(J1,J3,J2,J4)、

(J2,J1,J3,J4)、(J2,J1,J4,J3)是拓樸排序序列

(J1,J2,J4,J3)對應(yīng)于P1J1、P2J2、P3

J4、P4

J3問題的解空間是所有拓樸排序的序列集合，每個序列對于一個可能的解問題的樹表示(即用樹表示所有拓樸排序序列)0122313424334443拓樸序列樹的生成算法輸入:偏序集合S,樹根root.

輸出:由S的所有拓樸排序序列構(gòu)成的樹.1.

生成樹根root;2.

選擇偏序集中沒有前序元素的所有元素,作為

root的子節(jié)點;3.Forroot的每個字節(jié)點vDo4.S=S-{v};5.把v作為根,遞歸地處理S.

例0122313423434434J1J2J3J4J2J3J4J1J3J4J3J4J2J4J3J4J4J3J4J3J4計算解的代價的下界命題2.

把代價矩陣某行(列)的各元素減去同一個數(shù),不影響優(yōu)化解的求解.代價矩陣的每行(列)減去同一個數(shù)(該行或列的最小數(shù)),使得每行和每列至少有一個零,其余各元素非負(fù).每行(列)減去的數(shù)的和即為解的下界.

求解問題的分支界限搜索算法-12-26-3-10-3解代價下界=12+26+3+10+3=54J1J2J3J4P1P2P3P4例.012231342343443454717271869176787881586468707073被分配到的人1234解空間的加權(quán)樹表示分支界限搜索(使用爬山法)算法1.

建立根節(jié)點,其權(quán)值為解代價下界;2.使用爬山法,類似于拓樸排序序列樹生成算法求解問題,每產(chǎn)生一個節(jié)點,其權(quán)值為加工后的代價矩陣對應(yīng)元素加其父節(jié)點權(quán)值;3.一旦發(fā)現(xiàn)一個可能解,將其代價作為界限,循環(huán)地進(jìn)行分支界限搜索:剪掉不能導(dǎo)致優(yōu)化解的子解,使用爬山法繼續(xù)擴(kuò)展新增節(jié)點,直至發(fā)現(xiàn)優(yōu)化解.例012134345471586468707073被分配到的人1234分支被剪掉J1J2J3J4{P1,P2,P3,P4}

7.5TravelingSalesperson

OptimizationProblem

問題的定義轉(zhuǎn)換為樹搜索問題分支界限搜索算法問題的定義輸入:

無向連通圖G=(V,E),

每個節(jié)點都沒有到自身的邊,

每對節(jié)點之間都有一條非負(fù)加權(quán)邊.輸出:

一條由任意一個節(jié)點開始經(jīng)過每個節(jié)點一次最后返回開始節(jié)點的路徑,

該路徑的代價(即權(quán)值只和)最小.所有解集合作為樹根,其權(quán)值由代價矩陣使用上節(jié)方法計算;用爬山法遞歸地劃分解空間,得到二叉樹劃分過程:如下選擇圖上滿足下列條件的邊(i,j)Cost(i,1)=max{Cost(k,1)|kV}Cost(i,j)=0

使右子樹代價下界增加最大所有包含(i,j)的解集合作為左子樹所有不包含(i,j)的解集合作為右子樹計算出左右子樹的代價下界轉(zhuǎn)換為樹搜索問題分支界限搜索算法

在上述二叉樹建立算法中增加如下策略:

發(fā)現(xiàn)優(yōu)化解的上界;

如果一個子節(jié)點的代價下界超過,則終止該節(jié)點的擴(kuò)展.

下邊我們用一個例子來說明算法構(gòu)造根節(jié)點,設(shè)代價矩陣如下j=12345

67i=1234567

根節(jié)點為所有解的集合計算根節(jié)點的代價下界-3-416725326-7-1-4所有解的集合L.B=96

變換后的代價矩陣為j=12345

67i=1234567

得到如下根節(jié)點及其代價下界構(gòu)造根節(jié)點的兩個子節(jié)點選擇使子節(jié)點代價下界增加最大的劃分邊(4,6)建立根節(jié)點的子節(jié)點:左子節(jié)點為包括邊(4,6)的所有解集合左子節(jié)點為不包括邊(4,6)的所有解集合所有解的集合L.B=96包括邊(4,6)的所有解集合不包括邊(4,6)的所有解集合計算左右子節(jié)點的代價下界(4,6)的代價為0,所以左節(jié)點代價下界仍為96.我們來計算右節(jié)點的代價下界:如果一個解不包含(4,6),它必包含一條從4出發(fā)的邊和進(jìn)入節(jié)點6的邊.由變換后的代價矩陣可知,具有最小代價由4出發(fā)的邊為(4,1),代價為32.由變換后的代價矩陣可知,具有最小代價進(jìn)入6的邊為(5,6),代價為0.于是,右節(jié)點代價下界為:96+32+0=128.目前的樹為所有解的集合L.B=96包括邊(4,6)的所有解集合不包括邊(4,6)的所有解集合L.B=96L.B=128左子樹右子樹遞歸地構(gòu)造左右子樹構(gòu)造左子樹根對應(yīng)的代價矩陣

左子節(jié)點為包括邊(4,6)的所有解集合,所以矩陣的第4行和第6列應(yīng)該被刪除由于邊(4,6)被使用,邊(6,4)不能再使用,所以代價矩陣的元素C[6,4]應(yīng)該設(shè)置為.結(jié)果矩陣如下

j=1234567i=1234567計算左子樹根的代價下界矩陣的第5行不包含0第5行元素減3,左子樹根代價下界為:96+3=99結(jié)果矩陣如下

j=1234567i=1234567構(gòu)造右子樹根對應(yīng)的代價矩陣

右子節(jié)點為不包括邊(4,6)的所有解集合,只需要把

C[4,6]設(shè)置為

結(jié)果矩陣如下j=12345

67i=1234567計算右子樹根的代價下界矩陣的第4行不包含0第4行元素減32,右子樹根代價下界為:128+32=160結(jié)果矩陣如下j=12345

67i=1234567目前的樹為所有解的集合L.B=96包括邊(4,6)的所有解集合不包括邊(4,6)的所有解集合L.B=99L.B=160左子樹右子樹使用爬山策略擴(kuò)展左子樹根選擇邊使子節(jié)點代價下界增加最大的劃分邊(3,5)左子節(jié)點為包括邊(3,5)的所有解集合右子節(jié)點為不包括邊(3,5)的所有解集合計算左、右子節(jié)點的代價下界:99和117目前樹擴(kuò)展為:L.B=96所有解集合包括邊(4,6)不包括邊(4,6)L.B=99L.B=160包括邊(3,5)不包括邊(3,5)L.B=99L.B=117包括邊(2,1)不包括邊(2,1)L.B=112L.B=125包括邊(1,4)不包括邊(1,4)L.B=126L.B=153包括邊(6,7)不包括邊(6,7)L.B=126L.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>126停止擴(kuò)展優(yōu)化解代價的上界i1imj1jnX注意如果i1-i2-…-im和j1-j2-…-jm已被包含在一個正在構(gòu)造的路徑中,(im,j1)被加入,則必須避免jn到i1的路徑被加入.否則出現(xiàn)環(huán).7.6

TheA*AlgorithmA*算法的基本思想A*算法的規(guī)則應(yīng)用A*算法求解最短路徑問題A*算法的基本思想A*算法與分支界限策略的比較分支界限策略是為了剪掉不能達(dá)到優(yōu)化解的分支分支界限策略的關(guān)鍵是“界限”

A*算法的核心是告訴我們在某些情況下,我們得到的解一定是優(yōu)化解,于是算法可以停止

A*算法試圖盡早地發(fā)現(xiàn)優(yōu)化解

A*算法經(jīng)常使用Best-first策略求解優(yōu)化問題A*算法關(guān)鍵—代價函數(shù)對于任意節(jié)點ng(n)＝從樹根到n的代價h*(n)＝從n到目標(biāo)節(jié)點的優(yōu)化路徑的代價f*(n)＝g(n)+h*(n)是節(jié)點n的代價

Whatisthevalueofh*(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.最短路徑問題:輸入:

SV3V2V1V4V5T23432222351V3V2V1234S

g(V1)=2,g(V2)=3,g(V3)=4

h*(V1)=5,f*(V1)=g(V1)+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的代價求解樹的第一階段SV3V2V1V4V5T23432222351A*算法本質(zhì)—已經(jīng)發(fā)現(xiàn)的解是優(yōu)化解定理1.

使用Best-first策略搜索樹,如果A*選擇的節(jié)點是目標(biāo)節(jié)點,則該節(jié)點表示的解是優(yōu)化解.

證明.

令n是任意擴(kuò)展到的節(jié)點,t是選中目標(biāo)節(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).

我們有f(t)f*(s).

(4).t是目標(biāo)節(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)是

從根到n的路徑代價,h(n)是從n到某個目標(biāo)節(jié)點的優(yōu)化路徑代價;(3).對于所有n,h(n)h*(n);(4).當(dāng)選擇到的節(jié)點是目標(biāo)節(jié)點時,算法停止,

返回一個優(yōu)化解.應(yīng)用A*算法求解最短路徑問題問題的輸入:A*算法的執(zhí)行全過程SV3V2V1V4V5T23432222351SV3V2V1V4V5T2343222235Step1SV1V3V2243g(V1)=2g(V3)=4g(V2)=3h(V1)=min{2,3}=2h(V3)=min{2}=2h(V2)=min{2,2}=2f(V1)=2+2=4f(V3)=4+2=6f(V2)=2+2=54651SV3V2V1V4V5T2343222235Step2.擴(kuò)展V1g(V4)=2+2=4g(V2)=2+3=5h(V4)=min{3,1}=1h(V2