寬度優(yōu)先搜索.ppt

1、聲明： 本課件版權(quán)歸 清華大學(xué)計(jì)算機(jī)系語音技術(shù)中心 所有 未經(jīng)許可 不得擴(kuò)散,寬度優(yōu)先搜索,任務(wù)：處在（0，0）位置上的象棋馬跳到任何一個(gè)位置所需步數(shù) 0 1 2 3 4 y 0 0 3 2 3 2 1 3 4 1 2 3 2 2 1 4 3 2 3 3 2 3 2 3 4 2 3 2 3 4 x,根據(jù)馬的跳步規(guī)則研究8個(gè)方向的跳步增量dxk,dyk, k=0,1,7 6 -2 -1 0 1 2 -2 5 -1 7 0 4 1 2 k = 0 1 2 3,k 0 1 2 3 4 5 6 7 dx 1 2 2 1 -1 -2 -2 -1 dy -2 -1 1 2 2 1 -1 -2 dx-馬跳一

2、步在x方向上的增量 dy-馬跳一步在y方向上的增量 k- 方向號(hào) 從（x,y）馬跳一步到（x1,y1）,x1=x+dxk; 0 1 2 3 4 y1=y+dyk; 0 0 如馬的初始位置在(0,0)則 1 1 x1=0+dxk 2 1 y1=0+dyk , k=0,17 3 4 k 0 1 2 3 4 5 6 7 x1 1 2 2 1 -1 -2 -2 -1 y1 -2 -1 1 2 2 1 -1 -2,定義二維數(shù)組 int w55; 用來存儲(chǔ)每個(gè)格子中馬的跳步信息 對(duì)數(shù)組w進(jìn)行初始化，目的是讓每個(gè)格子只記錄一次，避免重復(fù)記錄。 for(int i=0;i=4;i+) for(int j=0;

3、j=4;j+) wij=-1;,經(jīng)初始化后的5x5格子中的數(shù)字均為-1 0 1 2 3 4 0 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 下面會(huì)看到，格子中的數(shù)為-1時(shí)才允許存入跳步信息。,馬從（0，0）跳一步，有兩個(gè)可行位置 （2，1）-k=2 （1，2）-k=3 稱（0，0）為結(jié)點(diǎn)，（2，1）和（1，2）為由（0，0）擴(kuò)展出的結(jié)點(diǎn) 0 0，0） 1 （2，1） 1（1，2）,馬由（0，0）跳一步到 （2，1）和（1，2） 再跳一步到 （4，0）（4，2）（3，3）（3

4、，1）（2，0）（0，2）（1，3）（4，2）（4，0） 見下圖，重點(diǎn)看： 標(biāo)有2的黃色的5個(gè)結(jié)點(diǎn)是由結(jié)點(diǎn)（2，1）擴(kuò)展出來的； 標(biāo)有2的黑色的4個(gè)結(jié)點(diǎn)是由結(jié)點(diǎn)（1，2）擴(kuò)展出來的。,0 1 2 3 4 y 0 0 -1 2 -1 2 1 -1 -1 1 2 -1 2 2 1 -1 -1 2 3 -1 2 -1 2 -1 4 2 -1 2 -1 -1 x,0 （0,0） 1（2,1） 1（1,2） 2 2 2 2 2 2 2 2 2 (4,0) (4,2) (3,3) (1,3) (0,2) (2,0) (3,1) (2,4) (0,4),怎樣來描述與實(shí)現(xiàn)這種擴(kuò)展過程呢？ 需要引入隊(duì)列數(shù)據(jù)結(jié)構(gòu)

5、 隊(duì)列的基本概念 隊(duì)列是限定在一端進(jìn)行插入，在另一端進(jìn)行刪除的特殊的線性表。 像食堂排隊(duì)買飯，后來的人排在隊(duì)尾（插入），隊(duì)頭上的人買完飯后離隊(duì)（刪除）。所有需要進(jìn)隊(duì)的數(shù)據(jù)項(xiàng)只能從隊(duì)尾進(jìn)入；所有需要出隊(duì)的數(shù)據(jù)項(xiàng)只能從隊(duì)頭離開。 先入隊(duì) 的元素先出隊(duì)，這種表又稱為先進(jìn)先出表（F I FO 表）。,隊(duì)列可用數(shù)組表示，在隊(duì)列運(yùn)算中要設(shè)兩個(gè)指針： 隊(duì)頭指針-head 隊(duì)尾指針-t a i l q 1 2 3 4 5 6 7 head tail temp=qtail; tail=tail+1;qtail=temp+1; q 1 2 3 4 5 6 7 8 head tail,將馬的跳步信息放入隊(duì)列中，用到

6、以下5條語句： tail=tail+1; queuetail.x=x1; queuetail.y=y1; queuetail.k=k; queuetail.step=step;,1個(gè)待擴(kuò)結(jié)點(diǎn) k / 2 3 0 (0,0) x 0 2 1 y 0 1 2 1 1 step 0 1 1 (2,1) (1,2) tail 1 2 3 擴(kuò)展出2個(gè)結(jié)點(diǎn) m=head=1 ,sq=tail=1 對(duì) m 到 sq 區(qū)間內(nèi)的結(jié)點(diǎn)進(jìn)行擴(kuò)展,k / 2 3 1 2 3 4 5 0 1 3 4 x 0 2 1 4 4 3 1 0 2 3 2 0 y 0 1 2 0 2 3 3 2 0 1 4 4 w 0 1 1

7、2 2 2 2 2 2 2 2 2 tail 1 2 3 4 5 6 7 8 9 10 11 12 m sq m=2, sq=3 對(duì) m 到 sq 區(qū)間內(nèi)的結(jié)點(diǎn)進(jìn)行擴(kuò)展,sq k / 2 3 1 2 3 4 5 0 1 3 4 x 0 2 1 4 4 3 1 0 2 3 2 0 y 0 1 2 0 2 3 3 2 0 1 4 4 step 0 1 1 2 2 2 2 2 2 2 2 2 tail 1 2 3 4 5 6 7 8 9 10 11 12 m m=2, sq=3,0 （0,0） 1（2,1） 1（1,2） 2個(gè)待擴(kuò)結(jié)點(diǎn) 2 2 2 2 2 2 2 2 2 (4,0) (4,2) (3

8、,3) (1,3) (0,2) (2,0) (3,1) (2,4) (0,4) 擴(kuò)展出9個(gè)結(jié)點(diǎn),k / 2 3 1 2 3 4 5 0 1 3 4 x 0 2 1 4 4 3 1 0 2 3 2 0 y 0 1 2 0 2 3 3 2 0 1 4 4 w 0 1 1 2 2 2 2 2 2 2 2 2 tail 1 2 3 4 5 6 7 8 9 10 11 12 m=4, sq=12 m sq 對(duì) m 到 sq 區(qū)間內(nèi)的結(jié)點(diǎn)進(jìn)行擴(kuò)展,0 1 2 3 4 0 0 3 2 3 2 1 3 -1 1 2 3 2 2 1 -1 3 2 3 3 2 3 2 3 4 2 3 2 3 -1,(0,0) 1

9、 2 3 (2,1) (1,2) 4 12 (4,0) (4,2) (3,3) (1,3) (0,2) (2,0) (3,1) (2,4) (0,4) (3,2) (3,4) (2,3) (3,0) (4,1) (1,4) (0,1) (1,0) (4,3) (0,3) 22 園圈中的數(shù)字為該結(jié)點(diǎn)在隊(duì)列中的序號(hào),0 1 2 3 4 y 0 0 3 2 3 2 1 3 4 1 2 3 2 2 1 4 3 2 3 3 2 3 2 3 4 2 3 2 3 4 x,(0,0) 1 2 3 (2,1) 跳1步 (1,2) 4 跳2步 12 (4,0) (4,2) (3,3) (1,3) (0,2) (2

10、,0) (3,1) (2,4) (0,4) 13 跳3步 22 (3,2) (3,4) (2,3) (3,0) (4,1) (1,4) (0,1) (1,0) (4,3) (0,3) 23 25 跳4步 (4,4) (1,1) (2,2),馬的初始位置（隊(duì)頭）結(jié)點(diǎn)1 由結(jié)點(diǎn)1 擴(kuò)展 第1步跳到結(jié)點(diǎn)2，結(jié)點(diǎn)3 由結(jié)點(diǎn)2，3 擴(kuò)展 第2步跳到結(jié)點(diǎn)4,結(jié)點(diǎn)5,結(jié)點(diǎn)12 由結(jié)點(diǎn)4,512 擴(kuò)展 第3步跳到結(jié)點(diǎn)13,結(jié)點(diǎn)14,結(jié)點(diǎn)22 由結(jié)點(diǎn)13,14,22 擴(kuò)展 第4步跳到結(jié)點(diǎn)23，結(jié)點(diǎn)24，結(jié)點(diǎn)25,根據(jù)上圖可構(gòu)造如下隊(duì)列 以序號(hào)來表示結(jié)點(diǎn) queue 1 2 3 4 5 12 13 14 22 2

11、3 24 25,從圖看出 隊(duì)列中有25個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)棋盤中的 25個(gè)格子； 隊(duì)列的序號(hào)，表示結(jié)點(diǎn)擴(kuò)展過程中的先后順序； 擴(kuò)展是分層的，處于同一層的結(jié)點(diǎn)從左至右依次擴(kuò)展，稱之為“寬度優(yōu)先”； 怎樣標(biāo)記一層的左右位置是編程的關(guān)鍵,用結(jié)構(gòu)數(shù)組來表示隊(duì)列 struct qtype /定義有兩個(gè)成員的結(jié)構(gòu) int x,y; /成員x 和成員y queueT*T+20,recT*T+20; /定義數(shù)組queue和數(shù)組rec是結(jié)構(gòu)類型的 /queue是結(jié)構(gòu)數(shù)組,作隊(duì)列用 ，T=5 /rec是結(jié)構(gòu)數(shù)組，用來存儲(chǔ)騎士們?cè)谄灞P上的起始位置,void init() /初始化函數(shù) /init memset(be

12、st,-1,sizeof(best); /初始化數(shù)組元素的值均為-1， int i=0; reci.x=0; /第0號(hào)騎士的 x 坐標(biāo)點(diǎn) reci.y=0; /第0號(hào)騎士的 y 坐標(biāo)點(diǎn) bestireci.xreci.y=0; /將第0號(hào)騎士在棋盤上的跳步信息置 為0，表示此處為出發(fā)點(diǎn) /init,/假定只有一個(gè)騎士 i (i=0) void BFS() /寬度優(yōu)先搜索 /BFS() /騎士的坐標(biāo)點(diǎn)在reci.x和reci.y int head=1; /定義隊(duì)頭head，并初始化為1 int tail=1; /定義隊(duì)尾tail，并初始化為1 queuehead.x=reci.x; /讓騎士的坐

13、標(biāo)點(diǎn)x入隊(duì) queuehead.y=reci.y; /讓騎士的坐標(biāo)點(diǎn)y入隊(duì) int step=0; /定義馬的跳步數(shù)step，初始化為0 int m=head; /定義中間變量m，記住隊(duì)頭head,while( m=tail ) /從隊(duì)頭m 到隊(duì)尾tail 進(jìn)行擴(kuò)展,直到 /隊(duì)空為止. 擴(kuò)展過程tail會(huì)不斷增加 /while int sq=tail; /讓sq記住原來的隊(duì)尾tail for( int am=m;am=sq;am+) /從 m 到 sq 作為一層擴(kuò)展 /for am for( int k=0;k8;k=k+1 ) /枚舉 k ，k為跳步方向 /for k /從(x,y)點(diǎn)沿k方

14、向跳至(x1,y1) int x1=queueam.x+dxk; int y1=queueam.y+dyk;,if( okjump(i,x1,y1) /判第i號(hào)騎士能否跳至(x1,y1)， /如能,讓該點(diǎn)入隊(duì)并記跳步信息 /if tail=tail+1; /隊(duì)尾加1(這是新擴(kuò)展出的) queuetail.x=x1; /讓 x1 入隊(duì) queuetail.y=y1; /讓 y1 入隊(duì) bestix1y1=step+1; /記錄第i號(hào)騎士跳至 /（x1,y1）的跳步信息 /if /for k /for am 從m 到 sq 作為一層已擴(kuò)展完畢,/之后，將下一段的開始sq+1賦給m,m是待擴(kuò)展的段頭

15、，段尾是新擴(kuò)展出的tail m=sq+1; /擴(kuò)展下一層時(shí)，是從step加1 的步數(shù)開始的 step=step+1; /while /BFS(),/可跳步的判別函數(shù) bool okjump(int i,int x,int y) return ( x=1 /如果馬跳至棋盤界內(nèi)且該處尚未有馬跳到過，則返回true，否則返回false,void display() /顯示棋局（調(diào)試過程用到） /display for( x=0;x5;x+) /從0,1,.,4枚舉x /for x coutendl; /換行 for( y=0;y5;y+) /從0,1,.,4枚舉y coutbestixy ; /輸出

16、第i個(gè)騎士跳至座標(biāo)點(diǎn)(x,y)上的步數(shù) /for x coutendl; /換行 /display,int main() /主函數(shù) init(); /初始化 BFS(); /寬度優(yōu)先擴(kuò)展結(jié)點(diǎn) display();/顯示棋盤中的跳步信息 return 0; ,在5*5的棋盤上討論馬的跳步信息的 基礎(chǔ)上，我們來研究騎士聚會(huì)問題。 任務(wù)：在88的棋盤上，輸入n個(gè)騎士的出發(fā)點(diǎn)，假定騎士每天只能跳一步，計(jì)算n個(gè)人的最早聚會(huì)地點(diǎn)和走多少天。要求盡早聚會(huì)，且n個(gè)人走的總步數(shù)最少。騎士的跳步按中國象棋的馬來跳。,解題思路： 從小到大，從簡(jiǎn)到繁，先討論5*5的棋盤 從個(gè)別到一般 理思路 假定有4個(gè)騎士，初始位置

17、分別在 (0,0),(1,4),(1,2),(3,4) 5 對(duì)每一個(gè)騎士做擴(kuò)展，得到如下4張?zhí)叫畔D,0 3 2 3 2 0號(hào)騎士的 跳步圖 3 4 1 2 3 數(shù) 字 2 1 4 3 2 放 在 3 2 3 2 3 左 上 2 3 2 3 4 角,3 2 1 2 3 1號(hào)騎士的 跳步圖 2 3 2 3 0 數(shù) 字 3 2 1 2 3 放 在 2 3 4 1 2 右 上 3 2 3 2 3 角,2號(hào)騎士的 1 2 3 2 1 跳步圖 數(shù) 2 3 0 3 2 字 放 1 2 3 2 1 在 左 4 1 2 1 4 下 角 3 2 3 2 3,3號(hào)騎士的 3 2 3 2 3 跳步圖 數(shù) 2 3

18、4 1 2 字 放 3 2 1 2 3 在 右 2 3 2 3 0 下 角 3 2 1 2 3,發(fā)揮你的想象力，把4張圖畫在透明膠片上，然后把4張落在一起，這時(shí)你可以看到每一個(gè)格子里有4個(gè)數(shù)據(jù)，分別屬于4個(gè)騎士的跳步信息 0號(hào)騎士的 1號(hào)騎士的 1 2 2 2 2號(hào)騎士的 3號(hào)騎士的 該方格坐標(biāo)x=2,y=1,0 3 3 2 2 1 3 2 2 3 1 3 2 2 3 3 2 2 1 3 3 2 4 3 1 2 2 3 3 0 4 張 2 2 3 3 0 4 3 1 2 2 膠片疊放 2 3 1 2 4 1 3 2 2 3 每個(gè)格子 1 3 2 2 3 1 2 2 1 3 有 4 個(gè)數(shù) 3 2

19、 2 3 3 4 2 1 3 2 4 2 1 3 2 2 1 3 4 0 2 3 3 2 2 3 3 2 4 3 3 3 2 2 3 1 2 2 3 3,依次對(duì)每個(gè)格子進(jìn)行觀察： 格子里4個(gè)數(shù)中最大的那個(gè)數(shù)，就是在該位置聚會(huì)所需天數(shù)，這是該位置的標(biāo)志性的數(shù)字。 按照題目要求尋找盡早聚會(huì)位置，即標(biāo)志性數(shù)字最小的格子。有可能這種格子不止一個(gè)，這時(shí)再比較4個(gè)騎士跳到這些位置上的總步數(shù)。最早聚會(huì)且4個(gè)人總步數(shù)也最少的位置即為所求。 下圖位置(2,1)是最佳聚會(huì)位置 用2天時(shí)間，4人共跳7步。,0 3 3 2 2 1 3 2 2 3 1 3 2 2 3 3 2 2 1 3 最 3 2 4 3 1 2 2

20、 3 3 0 佳 2 2 3 3 0 4 3 1 2 2 聚 2 3 1 2 4 1 3 2 2 3 會(huì) 1 3 2 2 3 1 2 2 1 3 點(diǎn) 3 2 2 3 3 4 2 1 3 2 （2，1） 4 2 1 3 2 2 1 3 4 0 2 3 3 2 2 3 3 2 4 3 3 3 2 2 3 1 2 2 3 3,搜索騎士們的最佳聚會(huì)位置 初始化棋盤，輸入n個(gè)騎士的初始位置 BFS（）寬度優(yōu)先對(duì)每一個(gè)騎士擴(kuò)展馬的跳步信息 計(jì)算在位置(x,y)上的 n個(gè)人中的最多跳步 goodxy.max n個(gè)人的跳步總和 goodxy.sum x,y=0,1,T-1 枚舉棋盤上的每個(gè)格子尋找 goodx

21、y.max 的最小值,min= min goodxy.max 1 x,y x,y = 0,1,T-1 在滿足 1 式的前提下，尋找個(gè)人跳步總和最小的格子位置 if( goodxy.max = min ) sum = min goodxy.sum 2 x,y x,y = 0,1,T-1,找到滿足公式 1 和 2 的格子位置 x, y 記錄并顯示min, sum ,(x,y) 任務(wù)即告完成 參考程序如下,/*任務(wù)：在88的棋盤上，輸入n個(gè)騎士的出發(fā)點(diǎn)，假定騎士每天只能跳一步，計(jì)算n個(gè)人的聚會(huì)地點(diǎn)和走多少天。 要求盡早聚會(huì)（走的天數(shù)最少）且 n個(gè)人走的總步數(shù)最少。騎士的跳步按中國象棋的馬來跳。200

22、7年2月20日*/ #include #include #include using namespace std;,const T=8; /棋盤尺寸 const dx8=1,2,2,1,-1,-2,-2,-1,/8個(gè)跳步方向上的x增量 dy8=-2,-1,1,2,2,1,-1,-2;/8個(gè)跳步方向上的y增量 int n; /騎士數(shù)目n int x,y; /定義棋盤坐標(biāo)x和y，全局變量 struct qtype /定義有兩個(gè)成員的結(jié)構(gòu) int x,y; /成員x 和成員y，棋盤上的坐標(biāo)點(diǎn) queueT*T,recT*T; /queue是結(jié)構(gòu)數(shù)組，作隊(duì)列用 /rec是結(jié)構(gòu)數(shù)組，用來存儲(chǔ)騎士們?cè)谄灞P

23、 /上的起 始位置,/定義3維整數(shù)類型數(shù)組best，存儲(chǔ)馬的跳步信息， /第1維是騎士號(hào)，第2和第3維是棋盤坐標(biāo)點(diǎn)x和y int bestT*TTT; struct jtype /定義有兩個(gè)成員的結(jié)構(gòu) int sum; /成員sum，記錄n個(gè)騎士跳入一個(gè)棋盤 /格子中的總步數(shù) int max; /成員max，記錄n個(gè)騎士跳入一個(gè)棋盤 / 格子中，n個(gè)中的某人的最多步數(shù) goodTT; /定義2維 jtype 類型數(shù)組，存儲(chǔ)棋盤中 /每個(gè)格子中的馬的跳步信息：總步數(shù)及最多步數(shù),void init() /初始化函數(shù) /init memset (best,-1,sizeof(best); /初始化3

24、維數(shù)組元素的值為1，表示棋盤中的每個(gè)格子都未曾填過信息 coutn; /提示并輸入騎士的數(shù)目n for( int i=0;ireci.x; /提示并輸入第i號(hào)騎士的 x 坐標(biāo)點(diǎn) coutreci.y; /提示并輸入第i號(hào)騎士的 y 坐標(biāo)點(diǎn) bestireci.xreci.y=0; /將第i號(hào)騎士在棋盤上的跳步信息置為0，表示此處為出發(fā)點(diǎn) /for i /init,bool okjump(int i,int x,int y) /可跳步的判別函數(shù) return ( x=0 /如果馬跳至棋盤界內(nèi)且該處尚未有馬跳/到過，則返回true，否則返回false ,void BFS() /寬度優(yōu)先搜索 /BF

25、S() for(int i=0;in;i=i+1) /對(duì)0,1,.,n-1號(hào)的每一個(gè)騎士進(jìn)行跳步處理 /for i int head=1; /定義隊(duì)頭head，并初始化為1 int tail=1; /定義隊(duì)尾tail，并初始化為1 queuehead.x=reci.x; /讓第i個(gè)騎士的坐標(biāo)點(diǎn)x入隊(duì) queuehead.y=reci.y; /讓第i個(gè)騎士的坐標(biāo)點(diǎn)y入隊(duì) int step=0; /定義馬的跳步數(shù)step，初始化為0 int m=head; /定義中間變量m，記住隊(duì)頭head,while( m=tail ) /從隊(duì)頭m 到隊(duì)尾tail 進(jìn)行擴(kuò)展, /直到隊(duì)空為止.擴(kuò)展過程tail會(huì)

26、不斷增加 /while int sq=tail; /定義中間變量sq，記住原來的隊(duì)尾tail for( int am=m;am=sq;am=am+1) /從 m 到 sq 作 為一個(gè)階段進(jìn)行擴(kuò)展 /for am for( int k=0;k8;k=k+1 ) /枚舉 k 的 8 個(gè)方向。 /for k int x1=queueam.x+dxk; int y1=queueam.y+dyk; /從(x,y)點(diǎn)沿k方向跳至(x1,y1),if ( okjump(i,x1,y1) ) /判第i號(hào)騎士能否跳至(x1,y1) /if tail=tail+1; /隊(duì)尾加1(這是新擴(kuò)展出的) queuetai

27、l.x=x1; /讓 x1 入隊(duì) queuetail.y=y1; /讓 y1 入隊(duì) bestix1y1=step+1; /記錄第i號(hào)騎士跳 至（x1,y1）， /此處的跳步比原來增加了一步 /if /for k /for am 從m 到 sq 作為一段已擴(kuò)展完畢,m=sq+1; / m是待擴(kuò)展的段頭， / 段尾是新擴(kuò)展出的tail step=step+1; /擴(kuò)展下一段時(shí)，步數(shù)需加1 /while /for i /BFS(),void display() /顯示棋局（調(diào)試過程用到過） /display for(int i=0;in;i=i+1) /枚舉0,1,.,n-1 每個(gè)騎士 /for i

28、 for( x=0;xT;x+) /從0,1,.,T-1，枚舉x /for x coutendl; /換行 for( y=0;yT;y+ ) /從0,1,.,T-1，枚舉y coutbestixy ; /輸出第i個(gè)騎士跳至座標(biāo)點(diǎn)(x,y)上的步數(shù) /for x coutendl; /換行 /for i /display,void output_good() / 調(diào)試用函數(shù) cout = endl; for (int i=0; iT; i+) for (int j=0; jT; j+) cout goodij.max ; cout endl; cout = endl; ,void search(

29、) /搜索騎士們聚會(huì)的最佳位置 /seach BFS(); /寬度優(yōu)先擴(kuò)展馬的跳步 int minx,miny; /定義最佳聚會(huì)位置 /對(duì)每個(gè)棋盤格子計(jì)算n個(gè)人跳至此處的總步數(shù)和其中某人的最多步數(shù) for( x=0;xT;x=x+1) for( y=0;yT;y=y+1) /for y goodxy.sum=0; /求和前預(yù)置0 （計(jì)算n個(gè)人的跳步和） goodxy.max = -1;,/ 調(diào)試用來查看每個(gè)棋盤格子上所有n個(gè)人比較后的最大跳步值及所有n個(gè)人的跳步和 cout goodxy.max ) goodxy.max=bestjxy; /記錄在（x,y）格子處n個(gè)人比較后的最大跳步值 /for j /for y,cout y: 0 1 2 3 4 5 6 7 endl; coutx:; for( x=0;xT;x+)