pascal廣度優(yōu)先搜索

《pascal廣度優(yōu)先搜索》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、09年暑假集訓(xùn)（二）——廣度優(yōu)先搜索廣度優(yōu)先搜索概念廣度優(yōu)先是另一種控制結(jié)點(diǎn)擴(kuò)展的策略，這種策略優(yōu)先擴(kuò)展深度小的結(jié)點(diǎn)，把問題的狀態(tài)向橫向發(fā)展。廣度優(yōu)先搜索法也叫BFS法(BreadthFirstSearch)，進(jìn)行廣度優(yōu)先搜索時(shí)需要利用到隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)。廣度優(yōu)先搜索算法適應(yīng)范圍如果問題的解是由若干部選擇構(gòu)成的一個(gè)選擇序列，題目要求我們用最少的步驟解決最優(yōu)化的問題，這個(gè)時(shí)候我們一般考慮是否使用廣度優(yōu)先搜索。廣度優(yōu)先搜索具有很明確的解題結(jié)構(gòu)，很容易掌握。讓我們來看個(gè)例子！重排九宮問題游戲在一個(gè)3乘3的九宮

2、中有1-8的8個(gè)數(shù)及一個(gè)空格隨機(jī)擺放在其中的格子里。如下面左圖所示?，F(xiàn)在要求實(shí)現(xiàn)這樣的問題：將該九宮調(diào)整為如下圖右圖所示的形式。調(diào)整規(guī)則是：每次只能將與空格（上，下或左，右）相臨的一個(gè)數(shù)字平移到空格中。試編程實(shí)現(xiàn)。

3、2

4、8?

5、3

6、????????????????

7、1

8、2

9、3

10、-

11、1

12、????

13、4

14、????????????????

15、8

16、???

17、4

18、

19、7

20、?6?

21、5

22、????????????????

23、7

24、6

25、5

26、在深度優(yōu)先搜索算法中，是深度越大的結(jié)點(diǎn)越先得到擴(kuò)展。如果在搜索中把算法改為按結(jié)點(diǎn)的層次進(jìn)

27、行搜索，本層的結(jié)點(diǎn)沒有搜索處理完時(shí)，不能對(duì)下層結(jié)點(diǎn)進(jìn)行處理，即深度越小的結(jié)點(diǎn)越先得到擴(kuò)展，也就是說先產(chǎn)生的結(jié)點(diǎn)先得以擴(kuò)展處理，這種搜索算法稱為廣度優(yōu)先搜索法。在深度優(yōu)先搜索算法中，是深度越大的結(jié)點(diǎn)越先得到擴(kuò)展。如果在搜索中把算法改為按結(jié)點(diǎn)的層次進(jìn)行搜索，本層的結(jié)點(diǎn)沒有搜索處理完時(shí)，不能對(duì)下層結(jié)點(diǎn)進(jìn)行處理，即深度越小的結(jié)點(diǎn)越先得到擴(kuò)展，也就是說先產(chǎn)生的結(jié)點(diǎn)先得以擴(kuò)展處理，這種搜索算法稱為廣度優(yōu)先搜索法。特別提示在有些情況下，比如求最優(yōu)秀解的時(shí)候，有時(shí)廣度搜索比深度搜索好;一般來說廣度優(yōu)先搜索可以利用隊(duì)列實(shí)

28、現(xiàn)，主要用于求一種狀態(tài)通過幾種規(guī)定的操作以最小次的變換到另一種狀態(tài)廣度優(yōu)先搜索基本算法1）從某個(gè)頂點(diǎn)出發(fā)開始訪問，被訪問的頂點(diǎn)作相應(yīng)的標(biāo)記，并輸出訪問頂點(diǎn)號(hào)；2）從被訪問的頂點(diǎn)出發(fā)，依次搜索與該頂點(diǎn)有邊的關(guān)聯(lián)的所有未被訪問的鄰接點(diǎn)，并作相應(yīng)的標(biāo)記。3）再依次根據(jù)2）中所有被訪問的鄰接點(diǎn)，訪問與這些鄰接點(diǎn)相關(guān)的所有未被訪問的鄰接點(diǎn)，直到所有頂點(diǎn)被訪問為止?！舅惴ㄟ^程框架】procedureguangdu(i);beginwrite(i);v[i]:=true;insert(q,i);{q是隊(duì)列，i進(jìn)隊(duì)}r

29、epeatk:=delete(q)；{出隊(duì)}forj:=1tondoif(a[k,j]=1)and(notv[j])thenbeginwrite(j);v[j]:=true;insert(q,j);end;until隊(duì)列q為空;變化的就是每個(gè)節(jié)點(diǎn)的表示形式和擴(kuò)展的策略例一、分油問題假設(shè)有3個(gè)油瓶，容量分別為4，3，1(斤)。開始時(shí)4斤油瓶是滿的，另外兩個(gè)是空的，請(qǐng)用這三個(gè)油瓶將倒出2斤的油來分析：由于每一次倒油都是從一個(gè)油瓶向另外一個(gè)油瓶倒油，要么向外倒油的油瓶倒空，要不接受倒油的油瓶道滿。我們將三個(gè)油

30、瓶編號(hào)，用三個(gè)油瓶的油表示當(dāng)前狀態(tài)，共有六種不同的倒油方法1->2;1->3;2->3;2->1;3->2;3->1;（相當(dāng)于八種跳馬的方案,回溯的條件是該狀態(tài)在以前出現(xiàn)過，而我們現(xiàn)在不但要求出一種解，而且我們要的出最優(yōu)化（操作次數(shù)最少的解），也就是我們要求我們搜索樹的層最少)深度優(yōu)先搜索:狀態(tài)樹4001300130313014003102111301—>21—>32—>11—>23—>13—>21—>21—>3狀態(tài)樹(廣度優(yōu)先搜索）4，0，01，3，03，0，14,0,01,2,11->21->30,

31、3,11->32->32->1在上面的狀態(tài)樹中，我們要注意下面幾點(diǎn)1:對(duì)于每個(gè)當(dāng)前的狀態(tài)節(jié)點(diǎn)來說，可能有八種可能，但是有些可能我們可以預(yù)先處理處理?？s小該節(jié)點(diǎn)的度數(shù)（要求到出的酒杯非空），另外如果該節(jié)點(diǎn)已經(jīng)被產(chǎn)生那么我們就不必在搜索下去了，我們利用隊(duì)列來控制）；2：我們搜索的結(jié)束條件是搜索到有2著瓶油；3：因?yàn)槲覀円业阶顑?yōu)秀解，所以我們按照層來搜索廣度優(yōu)先搜索所用的數(shù)據(jù)結(jié)構(gòu)DATA（狀態(tài)）OP（由何種操作變換而來)PRE(由何種狀態(tài)變換來，即父節(jié)點(diǎn)）初始狀態(tài)初始狀態(tài)A操作結(jié)果初始狀態(tài)B操作結(jié)果初始狀態(tài)

32、經(jīng)過兩次A的結(jié)果012B1AAFRONTREAR一:交通圖問題表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過若干個(gè)城市?，F(xiàn)要找出一條經(jīng)過城市最少的一條路線。分析該題分析：看到這圖很容易想到用鄰接距陣來表示，0表示能走，1表示不能走。如圖5。利用隊(duì)列廣度搜索首先想到的是用隊(duì)的思想。我們可以a記錄搜索過程，a.city記錄經(jīng)過的城市,a.pre記錄前趨元素，這樣就可以倒推出最短線路。具體過程如下：　　（1）將城市A入