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

第七章

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

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

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

8-Puzzle問(wèn)題

23514786

輸出:移動(dòng)系列,

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

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

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

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

求解8-Puzzle問(wèn)題21845673218456732184567321845673218456732184567321845673Depth-FirstSearch

算法1.

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

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

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

7.3OptimalTreeSearchingStrategies

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

1.

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

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

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

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

PersonnelAssignmentProblem

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

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

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

輸出

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

給定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)換為樹(shù)搜索問(wèn)題s6s5s4s3s2s1s9s8s7拓樸排序:s1s3s7s4s9s5s2s8s6問(wèn)題的解空間命題1.P1Jk1、P2

Jk2、…、Pn

Jkn是一個(gè)可能解,當(dāng)且僅當(dāng)Jk1、Jk2、…、Jkn必是一個(gè)拓樸排序的序列.例.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)對(duì)應(yīng)于P1J1、P2J2、P3

J4、P4

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

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

生成樹(shù)根root;2.

選擇偏序集中沒(méi)有前序元素的所有元素,作為

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

例0122313423434434J1J2J3J4J2J3J4J1J3J4J3J4J2J4J3J4J4J3J4J3J4計(jì)算解的代價(jià)的下界命題2.

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

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

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

7.5TravelingSalesperson

OptimizationProblem

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

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

每個(gè)節(jié)點(diǎn)都沒(méi)有到自身的邊,

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

一條由任意一個(gè)節(jié)點(diǎn)開(kāi)始經(jīng)過(guò)每個(gè)節(jié)點(diǎn)一次最后返回開(kāi)始節(jié)點(diǎn)的路徑,

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

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

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

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

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

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

67i=1234567

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

變換后的代價(jià)矩陣為j=12345

67i=1234567

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

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

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

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

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

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

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

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

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

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

A*算法的核心是告訴我們?cè)谀承┣闆r下,我們得到的解一定是優(yōu)化解,于是算法可以停止

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

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

Whatisthevalueofh*(n)?不知道！于是,f*(n)也不知道

估計(jì)h*(n)使用任何方法去估計(jì)h*(n),用h(n)表示h*(n)的估計(jì)

h(n)h*(n)總為真

f(n)=g(n)+h(n)g(n)+h*(n)=f*(n)定義為n的代價(jià)輸出:發(fā)現(xiàn)一個(gè)從S到T的最短路徑例1.最短路徑問(wèn)題:輸入:

SV3V2V1V4V5T23432222351V3V2V1234S

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

h*(V1)=5,f*(V1)=g(V1)+h*(V1)=7估計(jì)h*(n)從V1出發(fā)有兩種可能:代價(jià)為2,代價(jià)為3,最小者為2h*(V1)2,選擇h(n)=2為h*(V1)的估計(jì)值f(V1)=g(v1)+h(V1)=4為V1的代價(jià)求解樹(shù)的第一階段SV3V2V1V4V5T23432222351A*算法本質(zhì)—已經(jīng)發(fā)現(xiàn)的解是優(yōu)化解定理1.

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

證明.

令n是任意擴(kuò)展到的節(jié)點(diǎn),t是選中目標(biāo)節(jié)點(diǎn).

往證f(t)=g(t)是優(yōu)化解代價(jià).(1).A*算法使用Best-first策略,f(t)f(n).(2).A*算法使用h(n)h*(n)估計(jì)規(guī)則,f(t)f(n)f*(n).

(3).{f*(n)}中必有一個(gè)為優(yōu)化解的代價(jià),令其為f*(s).

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

(4).t是目標(biāo)節(jié)點(diǎn)h(t)=0,所以f(t)=g(t)+h(t)=g(t)f*(s).

(5).f(t)=g(t)是一個(gè)可能解,g(t)f*(s),f(t)=g(t)=f*(s).A*算法的規(guī)則(1).使用Best-first策略搜索樹(shù);(2).節(jié)點(diǎn)n的代價(jià)函數(shù)為f(n)=g(n)+h(n),g(n)是

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

返回一個(gè)優(yōu)化解.應(yīng)用A*算法求解最短路徑問(wèn)題問(wèn)題的輸入:A*算法的執(zhí)行全過(guò)程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