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法(Breadth First Search)，進(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的九宮中有1-8的8個(gè)數(shù)及一個(gè)空格隨機(jī)擺放在其中的格子里。如下面左圖所示?，F(xiàn)在要

2、求實(shí)現(xiàn)這樣的問題：將該九宮調(diào)整為如下圖右圖所示的形式。調(diào)整規(guī)則是：每次只能將與空格（上，下或左，右）相臨的一個(gè)數(shù)字平移到空格中。試編程實(shí)現(xiàn)。 | 2 | 8 | 3 | | 1 | 2 | 3 | - | 1 | | 4 | | 8 | | 4 | | 7 |6 | 5 | | 7 | 6 | 5 |,在深度優(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)先搜索算法中，是深度越大的結(jié) 點(diǎn)越先

3、得到擴(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í)現(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ù)

4、2）中所有被訪問的鄰接點(diǎn)，訪問與這些鄰接點(diǎn)相關(guān)的所有未被訪問的鄰接點(diǎn)，直到所有頂點(diǎn)被訪問為止。,【算法過程框架】,procedure guangdu(i); begin write(i); vi:=true; insert(q,i);q是隊(duì)列，i進(jìn)隊(duì) repeat k:=delete(q)；出隊(duì) for j:=1 to n do if (ak,j=1) and (not vj) then begin write(j); vj:=true; insert(q,j); end; until 隊(duì)列q為空; 變化的就是每個(gè)節(jié)點(diǎn)的表示形式和擴(kuò)展的策略,例一、分油問題,假設(shè)有3個(gè)油瓶，容量分別為4，3，1

5、(斤)。開始時(shí)4斤油瓶是滿的，另外兩個(gè)是空的，請(qǐng)用這三個(gè)油瓶將倒出2斤的油來 分析：由于每一次倒油都是從一個(gè)油瓶向另外一個(gè)油瓶倒油，要么向外倒油的油瓶倒空，要不接受倒油的油瓶道滿。我們將三個(gè)油瓶編號(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)樹,4 0 0,1 3 0,0 1 3,0 3 1,3 0 1,4 0 0,3 1 0,2 1 1,1 3 0,12,13

6、,21,12,31,32,12,13,狀態(tài)樹(廣度優(yōu)先搜索）,4，0，0,1，3，0,3，0，1,4,0,0,1,2,1,1-2,1-3,0,3,1,1-3,2-3,2-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 (由

7、何種狀態(tài) 變換來，即父節(jié)點(diǎn)）,初始 狀態(tài),初始狀態(tài)A 操作結(jié)果,初始狀態(tài)B 操作結(jié)果,初始狀態(tài)經(jīng)過兩次A的結(jié)果,0,1,2,B,1,A,A,FRONT,REAR,一:交通圖問題,表示的是從城市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入隊(duì)，隊(duì)首、隊(duì)尾都為1。（2） 將隊(duì)首

8、所指的城市所有可直通的城市入隊(duì)（如果這個(gè)城市在隊(duì)中出現(xiàn)過就不入隊(duì)，可用一個(gè)集合來判斷），將入隊(duì)城市的pre指向隊(duì)首的位置。然后將隊(duì)首加1，得到新的隊(duì)首城市。重復(fù)以上步驟，直到城市H入隊(duì)為止。當(dāng)搜到城市H時(shí)，搜索結(jié)束。利用pre可倒推出最少城市線路。,參考程序 const ju:array1.8,1.8 of 0.1=(1,0,0,0,1,0,1,1),(0,1,1,1,1,0,1,1),(0,1,1,0,0,1,1,1),(0,1,0,1,1,1,0,1),(1,1,0,1,1,1,0,0),(0,0,1,1,1,1,1,0),(1,1,1,0,0,1,1,0),(1,1,1,1,0,0,0,

9、1);type r=record 記錄定義city:array1.100 of char;pre:array1.100 of integer;end;var h,d,i:integer;a:r;s:set of A.H;procedure out; 輸出過程beginwrite(a.cityd);repeatd:=a.pred;write(-,a.cityd);until a.pred=0;writeln;halt;end;,用數(shù)組合表示 8個(gè)城市的相互 關(guān)系,procedure doit;beginh:=0; d:=1;a.city1:=A;a.pre1:=0;s:=A;repeat 步驟2

10、inc(h); 隊(duì)首加一，出隊(duì)for i:=1 to 8 do 搜索可直通的城市if （juord(a.cityh)-64,i=0）and （not（chr（i+64） in s）then 判斷城市是否走過begininc(d); 隊(duì)尾加一，入隊(duì)a.cityd:=chr(64+i);a.pred:=h;s:=s+a.cityd;if a.cityd=H then out;end;until h=d;end;begin 主程序doit;end.輸出：H-F-A,題二 字串變換 （NOIPG2.pas),問題描述:已知有兩個(gè)字串 A$, B$ 及一組字串變換的規(guī)則（至多6個(gè)規(guī)則）:A1$ - B1

11、$A2$ - B2$規(guī)則的含義為：在 A$中的子串 A1$ 可以變換為 B1$、A2$ 可以變換為 B2$ 。例如：A$abcdB$xyz變換規(guī)則為：abc-xuud-yy-yz則此時(shí)，A$ 可以經(jīng)過一系列的變換變?yōu)?B$，其變換的過程為：abcd-xud-xy-xyz共進(jìn)行了三次變換，使得 A$ 變換為B$。輸入:鍵盤輸人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ |- 變換規(guī)則. . / 所有字符串長度的上限為 20。輸出:輸出至屏幕。格式如下：若在 10 步（包含 10步）以內(nèi)能將 A$ 變換為 B$ ，則輸出最少的變換步數(shù)；否則輸出NO ANSWER!,三、騎士精神

12、（Knight）,在一個(gè)55的棋盤上有12個(gè)白色的騎士和12個(gè)黑色的騎士， 且有一個(gè)空位。在任何時(shí)候一個(gè)騎士都能按照騎士的走法（它可以走到和它橫坐標(biāo)相差為1，縱坐標(biāo)相差為2或者橫坐標(biāo)相差為2，縱坐標(biāo)相差為1的格子）移動(dòng)到空位上。 給定一個(gè)初始的棋盤，怎樣才能經(jīng)過移動(dòng)變成如下目標(biāo)棋盤： 為了體現(xiàn)出騎士精神，他們必須以最少的步數(shù)完成任務(wù)。,輸入文件： 第一行有一個(gè)正整數(shù)T(T=10)，表示一共有N組數(shù)據(jù)。接下來有T個(gè)55的矩陣，0表示白色騎士，1表示黑色騎士，*表示空位。兩組數(shù)據(jù)之間沒有空行。 輸出文件： 對(duì)于每組數(shù)據(jù)都輸出一行。如果能在15步以內(nèi)（包括15步）到達(dá)目標(biāo)狀態(tài)，則輸出步數(shù)，否則輸出1

13、。 Sample Input 2 10110 01*11 10111 01001 00000 01011 110*1 01110 01010 00100,題目四:移棋子,MFG投資公司發(fā)明了一種游戲棋盤，這個(gè)棋盤有15個(gè)孔，除了一個(gè)孔外，其它孔中都有一粒棋子。一粒棋子能沿著棋盤中的直線跳過一個(gè)或多個(gè)相鄰的棋子到最近的一個(gè)空孔中，被跳過的棋子就被移出棋盤。在下面的圖形中，位于12孔或者位于14號(hào)孔的棋子能跳入5號(hào)孔。如果位于12號(hào)孔的棋子跳過來，則位于8號(hào)孔的棋子就被移出棋盤，同樣如果是位于14號(hào)孔的棋子跳過來，則位于9號(hào)孔的棋子就被移走了。,請(qǐng)你編寫一個(gè)程序，找出用最 少跳動(dòng)序列移走其它棋子，除 了最后一粒棋子留在初始的空 孔中。如果這樣的序列不存在， 則程序要輸出一行信息 IMPOSSIBLE。,輸入輸入包含T個(gè)測試數(shù)據(jù)。輸入文件的第一行給出了T。每一個(gè)測試數(shù)據(jù)是單一的整數(shù)，表示一個(gè)空孔的編號(hào)