算法第七章周游

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

1、一般方法一、定義若需要確定滿足某一性質(zhì)的一個結(jié)點或結(jié)點子集，需要對所有結(jié)點檢索，這種檢索方法稱為周游。二、二叉樹周游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)分別表示上述算法對于樹T（設(shè)有n個結(jié)點）所需要的最大時間和空間。?則?定理(n1

)

t(n

n1

1)

c1}t(n)

c2n

c1,

(c2

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

1、一般方法證

n=0

則成立。設(shè)n

m

1，結(jié)論成立。則n=m時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、后根遍歷：按樹中根遍歷第一棵樹的第一棵樹的根按樹中根遍歷其余樹按樹后根遍歷第一棵樹的按樹后根遍歷其余樹二、樹的周游1、先根遍歷：

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

1、一般方法6/40NG

H

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

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

high(T)if

T=null

then

return(0)else return

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

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

1、一般方法四、圖的寬度優(yōu)先遍歷以隊列的結(jié)構(gòu)存放?過結(jié)點的遍歷方法。例12345678設(shè)置一個隊列為空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é)點v開始執(zhí)行時。所有已 結(jié)點都標上VISITED(i)=1。圖G和數(shù)組VISITED是全程量。VISITED開始時都已置成0//???VISITED(v)1;uv將Q初始化為空//Q是未檢測結(jié)點的隊列//loop4for

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

VISITED(w)=0

then

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

Q為空

then

return

endif //不再有還未檢測的結(jié)點//?10call

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

(n)。如使用鄰接表，則鄰接于u的所有結(jié)點可以在deg(u)時間內(nèi)判斷，所以檢測總時間為：(deg(u))(e)，visited數(shù)組初始化需要O(n),所以t(n,e)=(n+e)。如使用鄰接矩陣，則檢測時間為(n2),此時，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可以到達的所已置為零的數(shù)組VISITED(1:n)。這個算法有結(jié)點。G和VISITED是全程量//??12VISITED(v)1for

鄰接于v的每個結(jié)點w

do?3if

VISITED(w)=0 then

call

DFS(w)

endif?4repeat?5end

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

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

procedure

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

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

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

doif

VISITED(w)=0 thencallrepeatend

DFSprocedure

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

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

'',E'')

,使V

'

V

''?且E'

E''連通分圖。稱G

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

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

{a},

G2有兩個公共點a,b，則除去a,{a}仍連通，因G1,G2

還有一公共點G1

G2。{a}

仍連通，則

G1

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

G1

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

G2

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

。abG1G2第七章基本檢索與周游方法§3、雙連通分圖18/40因為如此加邊之后，原有的各點不再成為其割點，則要增加的邊數(shù)為Bk（刪除a后,

B1

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

，p

pi

1

i

1(ki

1)

(

ki

)

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

for

每一個割點ａ

doＥ２

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

Ｅ3

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

ａ，1

i

k

Ｅ4

將（vi

，vi

+1），1

i

k，加到GＥ5

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

310

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

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

.15

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

E(T

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

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

4578圖7.15

b9第七章基本檢索與周游方法§3、雙連通分圖24/40性質(zhì)3：設(shè)u是除根以外的任一結(jié)點，那么u為割點的充要條件是至少有一個兒子w，通過w子孫路徑和一條逆邊到達不了u的祖先。證明：若這樣的兒子w不存在，則u就不為割點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通過子孫路徑且至多加一條逆邊所達到的最小DFN數(shù),按樹的前根遍歷算法可以計算DFN數(shù)，按樹的后根遍歷算法可以計算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)下頁27/40三、割點自動識別算法結(jié)論1：對DFN計算采用先根遍歷（在遞歸調(diào)用前計算），對L值計算采用hou根遍歷（在遞歸調(diào)用后計算）結(jié)論2：割點判別算法

1）u為根，則DFS樹根至少有兩個兒子

。2）u不為根，u至少有一個兒子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

每個鄰接于u的結(jié)點w

do3 if

DFN(w)=0

then

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

end

ART三、割點自動識別算法2、DFN和L值計算算法(DFS算法的應(yīng)用）line procedure

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

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

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

每一個鄰接于u的結(jié)點w

doif v≠w and

DFN(W)<DFN(u) then

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

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

procedure

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

T

的每個兒子S

do6endififSOLVE(S)=0

then

return

(0)repeatreturn(1):else:for

T的每個兒子S

do//或結(jié)點//if

SOLVE(S)=1

then

return

(1)

endifrepeatreturn(0)1

case2

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

T可解

then

return

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

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

procedure

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

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

V沒有兒子then

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

ASOLVE(T)?7從樹T刪去所有標記為不可解的結(jié)點?8if

根結(jié)點T標記為可解then

return(T)endif???910從隊列Q中刪去以下的所有結(jié)點：它們在T中曾有一個祖先被標記為不可解或者在T中有一個標記為可解的祖先if

Q為空then

print(‘no

solution’);stop

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

BFGEN34/40第七章基本檢索與周游方法§5、對策樹例:

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

2

1

2

1B3A1

B

2

1

B

1

B

B

1

B

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

,c3

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

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

1,x對A是勝局1，x對A是負局V(x)

max{V(ci

)},

1id

min{V(ci

)}

1idE(x)，對弈者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負A勝A負A負p3,7圖7.20第七章基本檢索與周游方法§5、對策樹易見：則若A走子，e(x)=E(x)?若B走子，4、通過至多有L步棋來計算V

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

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

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

'

(x)

i1idmax{V

'

(c

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

'

(x)=V(x)V

'

(x)=-V(x)第七章基本檢索與周游方法§5、對策樹函數(shù)是e(X)。為方便起見，假定由任一不是終局的棋局X開始，此棋局的合法棋著只允許將棋局轉(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、對策樹從A看：由于VE(C,L-1)=-V(ci因此，結(jié)果為max{v(ci)}從B看：由于VE(C,L-1)=V(ci)因此，結(jié)果為min{v(ci)}第七章基本檢索與周游方法§5、對策樹二、對策樹的啟發(fā)性搜索1、

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

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

的

值就變成3，V

(p5,5

)

p3,3的

值，則不用去生成

p5,6

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

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