算法第七章周游

第七章基本檢索與周游方法1、一般方法2、代碼優(yōu)化（略）3、雙連通分圖4、與或圖5、對(duì)策樹(shù)1/40第七章基本檢索與周游方法§

1、一般方法一、定義若需要確定滿足某一性質(zhì)的一個(gè)結(jié)點(diǎn)或結(jié)點(diǎn)子集，需要對(duì)所有結(jié)點(diǎn)檢索，這種檢索方法稱為周游。二、二叉樹(shù)周游1、中根遍歷：

左 、根、右procedure

inorder(T)if

T≠null

then inorder

(T.lchild)visit(T)inorder(T.rchild)endifendinorder2/40中根遍歷:FDHGIBEAC前根遍歷:ABDFGHIEC后根遍歷:FHIGDEBCAFGHIABCDE例2:第七章基本檢索與周游方法§

1、一般方法4/40????2、前根遍歷:

根、左

、右、右

、根3、后根遍歷:

左4、算法分析設(shè)t(n)、s(n)分別表示上述算法對(duì)于樹(shù)T（設(shè)有n個(gè)結(jié)點(diǎn)）所需要的最大時(shí)間和空間。?則?定理(n1

)

t(n

n1

1)

c1}t(n)

c2n

c1,

(c2

2c1)第七章基本檢索與周游方法§

1、一般方法證

n=0

則成立。設(shè)n

m

1，結(jié)論成立。則n=m時(shí)t(m

max{t(n1

)

t(m

n1

1)

c1}(0

n1

m

1)

max{c2n1

c1

c2

(m

n1

1)

c1}?成立t(n)

c2n

c1又t(0)

c2m

3c1

c2

c2m

c1t(n)

(n)t(n)

c2n

c1(c2

2c1)定理c2

2c1第七章基本檢索與周游方法§

1、一般方法5/402、中根遍歷:3、后根遍歷：按樹(shù)中根遍歷第一棵樹(shù)的第一棵樹(shù)的根按樹(shù)中根遍歷其余樹(shù)按樹(shù)后根遍歷第一棵樹(shù)的按樹(shù)后根遍歷其余樹(shù)二、樹(shù)的周游1、先根遍歷：

第一棵樹(shù)的根按樹(shù)先根遍歷第一棵樹(shù)的按樹(shù)先根遍歷其余樹(shù)??????第一棵樹(shù)的根第七章基本檢索與周游方法§

1、一般方法6/40NG

H

J樹(shù)的先根遍歷：ABEGHJFCDKLMNOP樹(shù)的中根遍歷：GEHJBFACDLKNMPO樹(shù)的后根遍歷：GHJFCDEBLNPOMKADABEFKLMOPc例2：第七章基本檢索與周游方法§

1、一般方法8/40例1三、應(yīng)用??????試計(jì)算一二叉樹(shù)的高度procedure

high(T)if

T=null

then

return(0)else return

max(high(T.lchild),high(T.rchild))+1endifend

high第七章基本檢索與周游方法§

1、一般方法四、圖的寬度優(yōu)先遍歷以隊(duì)列的結(jié)構(gòu)存放?過(guò)結(jié)點(diǎn)的遍歷方法。例12345678設(shè)置一個(gè)隊(duì)列為空Queue:1、2、3、4、5、6、7、8次序：1、2、3、4、5、6、7、8第七章基本檢索與周游方法§

1、一般方法9/401、算法7.6圖寬度優(yōu)先檢索算法??line

procedure

BFS(v)//寬度優(yōu)先搜索G，它在結(jié)點(diǎn)v開(kāi)始執(zhí)行時(shí)。所有已 結(jié)點(diǎn)都標(biāo)上VISITED(i)=1。圖G和數(shù)組VISITED是全程量。VISITED開(kāi)始時(shí)都已置成0//???VISITED(v)1;uv將Q初始化為空//Q是未檢測(cè)結(jié)點(diǎn)的隊(duì)列//loop4for

鄰接于u的所有結(jié)點(diǎn)wdo?5if

VISITED(w)=0

then

callADDQ(w,Q)//w未檢測(cè)//?6VISITED(w)1?7endif?8repeat?9if

Q為空

then

return

endif //不再有還未檢測(cè)的結(jié)點(diǎn)//?10call

DELETEQ(u,Q)?11repeat?12BFS10/402、算法分析定理：設(shè)t(n,e)和s(n,e)是BFS在任一具有n個(gè)結(jié)點(diǎn)和e條邊的圖G上所花的最大時(shí)間和最大附加空間，則t(n,e)=(n+e)，s(n,e)=(n)證明：因BFS完成隊(duì)列和邊的檢索工作，而它至多做n-1次加入隊(duì)列的動(dòng)作，所以s(n,e)=O(n),又因?yàn)関isited操作需要（n)空間，所以s(n,e)=

(n)。如使用鄰接表，則鄰接于u的所有結(jié)點(diǎn)可以在deg(u)時(shí)間內(nèi)判斷，所以檢測(cè)總時(shí)間為：(deg(u))(e)，visited數(shù)組初始化需要O(n),所以t(n,e)=(n+e)。如使用鄰接矩陣，則檢測(cè)時(shí)間為(n2),此時(shí)，t(n,e)=

(n2)第七章基本檢索與周游方法§

1、一般方法3.非連通圖BFS周游算法Procedure

BFT(G,n)declare

VISITED(n)for

i=1

to

n

doVISITED(i)=0repeatfor

i=1

to

n

doif

VISITED(i)=0

then BFS(i)

endifrepeatend

BFT?第七章基本檢索與周游方法§

1、一般方法由v可以到達(dá)的所已置為零的數(shù)組VISITED(1:n)。這個(gè)算法有結(jié)點(diǎn)。G和VISITED是全程量//??12VISITED(v)1for

鄰接于v的每個(gè)結(jié)點(diǎn)w

do?3if

VISITED(w)=0 then

call

DFS(w)

endif?4repeat?5end

DFS第七章基本檢索與周游方法§

1、一般方法五、圖的深度優(yōu)先遍歷1、圖的深度優(yōu)先搜索算法line

procedure

DFS(v)//已知一個(gè)n結(jié)點(diǎn)的無(wú)向（或有向）圖G=（V,E）以及初值13/40??2、

DFS算法的執(zhí)行過(guò)程圖稱為DFS樹(shù)例 遍歷過(guò)程如下圖所示：7123456812345867第七章基本檢索與周游方法§

1、一般方法14/40DFS(w)endifVISITED(v)1for鄰接于v的每個(gè)結(jié)點(diǎn)w

doif

VISITED(w)=0 thencallrepeatend

DFSprocedure

DFS(v)第七章基本檢索與周游方法?§3、雙連通分圖一、雙連通分圖1、定義：若在無(wú)向連通圖G中，刪除結(jié)點(diǎn)a及關(guān)聯(lián)邊，G變成不連通，則a稱為割點(diǎn)，不含割點(diǎn)的圖稱為雙連通圖。例 為雙連通圖2、定義：若G'(V

',E')是雙連通子圖，且在G中再不存在這樣的雙連通子圖G''(V

'',E'')

,使V

'

V

''?且E'

E''連通分圖。稱G

'為G的極大雙連通子圖，簡(jiǎn)稱為雙15/40例圖7.1114226738310955第七章基本檢索與周游方法§3、雙連通分圖16/4033、雙連通分圖的性質(zhì)1）任何兩個(gè)雙連通分圖至多只有一個(gè)公共點(diǎn)并且該公共點(diǎn)就是割點(diǎn)。為雙連通分圖，有一個(gè)公共點(diǎn)a，若a證明：若G1,不是割點(diǎn)，則通分圖,與前提G1

G2。證明b，所以圖,與前提若分圖G1,G1

{a},

G2有兩個(gè)公共點(diǎn)a,b，則除去a,{a}仍連通，因G1,G2

還有一公共點(diǎn)G1

G2。{a}

仍連通，則

G1

為雙連G21GG2{a}仍連通，則

G1

為雙連通分G2第七章基本檢索與周游方法§3、雙連通分圖17/40∴G1

G2

為雙連通分圖這與前提2）任何一條邊不能同時(shí)在兩個(gè)不同的連通分圖中證明：否則的話會(huì)導(dǎo)致該邊關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)，成為兩個(gè)分圖的公共點(diǎn)，這與性質(zhì)1）

。abG1G2第七章基本檢索與周游方法§3、雙連通分圖18/40因?yàn)槿绱思舆呏?，原有的各點(diǎn)不再成為其割點(diǎn)，則要增加的邊數(shù)為Bk（刪除a后,

B1

仍連通），設(shè)圖G有a1,a2,…,ap個(gè)割點(diǎn)a，i與割點(diǎn) 關(guān)聯(lián)的ki分圖數(shù)為

，p

pi

1

i

1(ki

1)

(

ki

)

p第七章基本檢索與周游方法§3、雙連通分圖4、把非雙連通圖改造為雙連通圖算法分圖E1

for

每一個(gè)割點(diǎn)ａ

doＥ２

設(shè)Ｂ２，B２，...,Ｂk是包含結(jié)點(diǎn)a的雙

Ｅ3

設(shè)vi是Ｂi的一個(gè)結(jié)點(diǎn)，且vi

ａ，1

i

k

Ｅ4

將（vi

，vi

+1），1

i

k，加到GＥ5

repeat19/40?例如：14226755第七章基本檢索與周游方法§3、雙連通分圖383

310

9二、深度優(yōu)先生成樹(shù)1、定義定義1：按深度優(yōu)先檢索算法遍歷圖時(shí)的各個(gè)結(jié)點(diǎn)的次序，稱為該結(jié)點(diǎn)的數(shù)，用DFN表示，

的路徑，稱為該圖的深度優(yōu)先生成樹(shù)，簡(jiǎn)稱DFN樹(shù)。定義1：圖G中除DFN樹(shù)枝以外的邊稱為該樹(shù)的逆邊。第七章基本檢索與周游方法§3、雙連通分圖例：DFN(1)=1，DFN(10)=4336458圖

.15

b7910逆邊1222/40第七章基本檢索與周游方法§3、雙連通分圖2、性質(zhì)???性質(zhì)1：若(u,v)∈E(G)對(duì)于DFS樹(shù)T，則u是v的祖先或v是u的祖先證：若(u,v)∈E(G)（1）當(dāng)(u,v)∈E(T)，必有u是v的父親或v是u的父親（2）當(dāng)(u,v)

E(T

)不妨設(shè)DFN(u)<DFN(v)，根據(jù)DFS遍歷算法，是先

u，而對(duì)u的檢測(cè)至少要完v，才能完成，因此在樹(shù)T中u是v的祖先，故交叉邊不存在。交叉邊不存在233645789第七章基本檢索與周游方法§3、雙連通分圖23/40?性質(zhì)2：一棵DFS生成樹(shù)的根T是割點(diǎn)，當(dāng)且僅當(dāng)在T樹(shù)中至少有兩個(gè)兒子。證明：若有兩個(gè)兒子，刪除T，則這兩個(gè)兒子將位于兩個(gè)連通分支中，反之亦然。149256781233610

4578圖7.15

b9第七章基本檢索與周游方法§3、雙連通分圖24/40性質(zhì)3：設(shè)u是除根以外的任一結(jié)點(diǎn)，那么u為割點(diǎn)的充要條件是至少有一個(gè)兒子w，通過(guò)w子孫路徑和一條逆邊到達(dá)不了u的祖先。證明：若這樣的兒子w不存在，則u就不為割點(diǎn)u10

45u8圖7.15

b9第七章基本檢索與周游方法§3、雙連通分圖1、定義L(u)=min{DFN(u),min{L(w)|w是u的兒子}，min{DFN(w)|(u,w)是一條逆邊}}，則L(u)是u通過(guò)子孫路徑且至多加一條逆邊所達(dá)到的最小DFN數(shù),按樹(shù)的前根遍歷算法可以計(jì)算DFN數(shù)，按樹(shù)的后根遍歷算法可以計(jì)算L(u）值。例：DFN(1)=1DFN(10)=4149256781233610

4578圖7.15

b9第七章基本檢索與周游方法§3、雙連通分圖L(4)=1DFN(4)=2DFN(9)=5DFN(6)=8L(10)=4DFN(3)=3DFN(2)=6DFN(7)=9L(9)=5L(5)=6L(1)=126/40DFN(5)=7DFN(8)=10L(6)=8

L(8)=6L(2)=1

L(3)=1L(7)=6轉(zhuǎn)下頁(yè)27/40三、割點(diǎn)自動(dòng)識(shí)別算法結(jié)論1：對(duì)DFN計(jì)算采用先根遍歷（在遞歸調(diào)用前計(jì)算），對(duì)L值計(jì)算采用hou根遍歷（在遞歸調(diào)用后計(jì)算）結(jié)論2：割點(diǎn)判別算法

1）u為根，則DFS樹(shù)根至少有兩個(gè)兒子

。2）u不為根，u至少有一個(gè)兒子w使得L(w)

≥DFN(u)第七章基本檢索與周游方法§3、雙連通分圖w,則遞歸調(diào)用else

if

w≠v

then

L(u)min(L(u),DFN(w))//w不是v的父親，endif

//（u，w)是一條逆邊endifrepeat?1 DFN(u)

num;L(u)num;numnum+12 for

每個(gè)鄰接于u的結(jié)點(diǎn)w

do3 if

DFN(w)=0

then

ART(w,u);L(u)min(L(u),L(w)) //還未5678?9

end

ART三、割點(diǎn)自動(dòng)識(shí)別算法2、DFN和L值計(jì)算算法(DFS算法的應(yīng)用）line procedure

ART(u,v)//u是深度優(yōu)先檢索的開(kāi)始結(jié)點(diǎn)。在深度優(yōu)先生成樹(shù)中，u若有父親，那么v就是它的父親。假設(shè)數(shù)組DFN是全程量，并將其初始化為0。num是全程變量，被初始化為1。N是G

的節(jié)點(diǎn)數(shù)//global

DFN(n),L(n),num,n第七章基本檢索與周游方法§3、雙連通分圖28/40??????????endif//注意：若v=w或DFN(W)>DFN(u)表明(u,w)是在棧中，現(xiàn)（u,v)是未在棧中的樹(shù)枝或逆邊//if

DFN(w)=0

then

ART(w,u)

if

L(w)

≥DFN(u)then

print(“為雙連通分圖”)；loop

(x,y)pop(s)；print(‘(‘,x,’,’,y,’)’)until

((x,y)=(u,w)

or

(x,y)=(w,u))endifL(u)min(L(u),L(w))else

if

w

≠v

then

L(u)min(L(u),DFN(w))

endifendifrepeatend

ART3、雙連通分圖輸出算法Procedure

ART(u,v)//u若有父親則為v//DFN(u)num

L(u)num

numnum+1for

每一個(gè)鄰接于u的結(jié)點(diǎn)w

doif v≠w and

DFN(W)<DFN(u) then

push(u,v)1、樹(shù)枝：如w未被 ，則DFN(w)=0,此時(shí)，DFN(w)<DFN(u)成立2、逆邊：DFN(w)<DFN(u)成立表示u為割點(diǎn)，因?yàn)閡的兒子w子孫路徑加一條逆邊到不了u的祖先，則一個(gè)雙

分圖形成了三、割點(diǎn)自動(dòng)識(shí)別算法第七章基本檢索與周游方法§3、雙連通分圖29/40第七章基本檢索與周游方法§4、與或圖一、問(wèn)題的提出1、復(fù)雜問(wèn)題分解為一系列子問(wèn)題，又可由子問(wèn)題的解導(dǎo)出原問(wèn)題的解，稱為問(wèn)題化簡(jiǎn)，問(wèn)題化簡(jiǎn)已經(jīng)在工業(yè)調(diào)度、定理證明、機(jī)器學(xué)習(xí)、 系統(tǒng)等方面得到廣泛應(yīng)用，化簡(jiǎn)過(guò)程用圖表示，則圖稱為與或圖。2、解圖是由與或圖中一些可解結(jié)點(diǎn)組成的子圖30/40例如：ABCDEABCDEEFGHI實(shí)例樹(shù)與或樹(shù)AEBCDF與或圖第七章基本檢索與周游方法§4、與或圖二、與或樹(shù)是否可解判定算法（算法7.12）Line

procedure

SOLVE(T)//T是一棵樹(shù)其根為T(mén)的與/或樹(shù)，T≠0。如果問(wèn)題可解則返回1，否則返回0//：T是與結(jié)點(diǎn)：for

T

的每個(gè)兒子S

do6endififSOLVE(S)=0

then

return

(0)repeatreturn(1):else:for

T的每個(gè)兒子S

do//或結(jié)點(diǎn)//if

SOLVE(S)=1

then

return

(1)

endifrepeatreturn(0)1

case2

: T是終結(jié)點(diǎn)：if

T可解

then

return

(1）else return(0)endif??????????910111213endcaseend

SOLVE32/40第七章基本檢索與周游方法§4、與或圖33/40三、解樹(shù)生成算法設(shè)問(wèn)題的解可用函數(shù)F來(lái)表示，則一個(gè)已生成的結(jié)點(diǎn)，可用F去生成它的所有兒子，解樹(shù)生成分為深度優(yōu)先或?qū)挾葍?yōu)先，當(dāng)生成的結(jié)點(diǎn)，深度可能是無(wú)限時(shí)，則必須通過(guò)限制深度來(lái)解決。1、寬度優(yōu)先生成解樹(shù)算法7.13Line

procedure

BFGEN(T,F)//F生成T中的兒子結(jié)點(diǎn)；T是根結(jié)點(diǎn)。終止時(shí)，如果存在解樹(shù)，則T是這解樹(shù)的根//第七章基本檢索與周游方法§4、與或圖第七章基本檢索與周游方法§4、與或圖?1將隊(duì)列Q初始化為空；

VT?2loop?3用F生成V的那些兒子//檢測(cè)V//???4if

V沒(méi)有兒子then

標(biāo)記V為不可解else①將V的所有不是葉子結(jié)點(diǎn)的兒子放入隊(duì)列Q，將那些葉子結(jié)點(diǎn)分別標(biāo)上可解或不可解;②把V的所有兒子加入樹(shù)T;5endif?6call

ASOLVE(T)?7從樹(shù)T刪去所有標(biāo)記為不可解的結(jié)點(diǎn)?8if

根結(jié)點(diǎn)T標(biāo)記為可解then

return(T)endif???910從隊(duì)列Q中刪去以下的所有結(jié)點(diǎn)：它們?cè)赥中曾有一個(gè)祖先被標(biāo)記為不可解或者在T中有一個(gè)標(biāo)記為可解的祖先if

Q為空then

print(‘no

solution’);stop

endif?11刪去隊(duì)列Q的第一個(gè)元素；設(shè)此結(jié)點(diǎn)是V?12repeat?13end

BFGEN34/40第七章基本檢索與周游方法§5、對(duì)策樹(shù)例:

拾火柴每次至多取3根，最少取一根，拿到最后一根為敗者。654314323221A3

2

1

2

1B3A1

B

2

1

B

1

B

B

1

B

BAAAAAB下棋A下棋35/4036/40小。c1,c2

,c3

,...cd例:對(duì)于終局，則第七章基本檢索與周游方法§5、對(duì)策樹(shù)一、估價(jià)函數(shù)1、E(x)以數(shù)值形式表示弈者在棋局X下獲勝機(jī)會(huì)的大是x棋局的兒子們所表示的棋局。2、V(x)是棋局x的代價(jià)函數(shù)???x是葉子x是方形結(jié)點(diǎn)，即A下棋

x是園形結(jié)點(diǎn)，即B下棋E(x)

1,x對(duì)A是勝局1，x對(duì)A是負(fù)局V(x)

max{V(ci

)},

1id

min{V(ci

)}

1idE(x)，對(duì)弈者B走子37/403-∞-∞+∞-∞3+∞-12-∞0-32150-322310315927弈者A走子p1,12,1pp2,3

-1p2,4p3,1p3,2p3,3p3,4p3,5p3,6maxminmaxp4,5minmaxp5,15,2pp5,3p5,45,5pp5,6p5,7p5,8p5,9p5,10p5,11p4,1p4,2p4,3p4,4A的最優(yōu)棋著3

p2,2A勝A負(fù)A勝A負(fù)A負(fù)p3,7圖7.20第七章基本檢索與周游方法§5、對(duì)策樹(shù)易見(jiàn)：則若A走子，e(x)=E(x)?若B走子，4、通過(guò)至多有L步棋來(lái)計(jì)算V

'(x)的算法VE(x,L)算法7.14Procedure

VE(X,L)//通過(guò)至多向前看L著棋計(jì)算V

'(x)，弈者A使用的估價(jià)38/40V

'

(x)

i1idmax{V

'

(c

)}3、最大最小遞歸過(guò)程e(x)，x是葉子結(jié)點(diǎn)e(x)=-E(x)V

'

(x)=V(x)V

'

(x)=-V(x)第七章基本檢索與周游方法§5、對(duì)策樹(shù)函數(shù)是e(X)。為方便起見(jiàn)，假定由任一不是終局的棋局X開(kāi)始，此棋局的合法棋著只允許將棋局轉(zhuǎn)換成棋////周游第一棵//周游其余的局

C1,C2

,

,Cd39/40if

X是終局or

L=0

then return(e(X))

endifans

VE(C1,l

1)for

i2

to

d

do?ans

max(ans,

VE(C1,l

1))repeatreturn(ans)end

VE第七章基本檢索與周游方法§5、對(duì)策樹(shù)從A看：由于VE(C,L-1)=-V(ci因此，結(jié)果為max{v(ci)}從B看：由于VE(C,L-1)=V(ci)因此，結(jié)果為min{v(ci)}第七章基本檢索與周游方法§5、對(duì)策樹(shù)二、對(duì)策樹(shù)的啟發(fā)性搜索1、

-截?cái)嘁?guī)則如果一個(gè)求最小值位置的值，判斷為小于或等于它的），那么可以停止生成這父親的當(dāng)前估價(jià)值（設(shè)為?例如圖7.20所示，V(p4,1

)個(gè)求最小值位置其余兒子的值。一旦確定，p3,3

的

值就變成3，V

(p5,5

)

p3,3的

值，則不用去生成

p5,6

的值。40/40如果一個(gè)求最小值位置的值，判斷為小于或等于它的父親的當(dāng)前子的值。估價(jià)值（設(shè)為

），那么可以停止生成這個(gè)求最小值位置其余兒3,34,15,6p例如，V