1、聲明： 本課件版權(quán)歸 清華大學(xué)計算機(jī)系語音技術(shù)中心 所有 未經(jīng)許可 不得擴(kuò)散,寬度優(yōu)先搜索,任務(wù)：處在（0，0）位置上的象棋馬跳到任何一個位置所需步數(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個方向的跳步增量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- 方向號 從（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; 用來存儲每個格子中馬的跳步信息 對數(shù)組w進(jìn)行初始化，目的是讓每個格子只記錄一次，避免重復(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 下面會看到，格子中的數(shù)為-1時才允許存入跳步信息。,馬從（0，0）跳一步，有兩個可行位置 （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個結(jié)點(diǎn)是由結(jié)點(diǎn)（2，1）擴(kuò)展出來的； 標(biāo)有2的黑色的4個結(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è)兩個指針： 隊(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個待擴(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個結(jié)點(diǎn) m=head=1 ,sq=tail=1 對 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 對 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個待擴(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個結(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 對 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ì)列中的序號,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ì)列 以序號來表示結(jié)點(diǎn) queue 1 2 3 4 5 12 13 14 22 2

11、3 24 25,從圖看出 隊(duì)列中有25個結(jié)點(diǎn)，每個結(jié)點(diǎn)對應(yīng)棋盤中的 25個格子； 隊(duì)列的序號，表示結(jié)點(diǎn)擴(kuò)展過程中的先后順序； 擴(kuò)展是分層的，處于同一層的結(jié)點(diǎn)從左至右依次擴(kuò)展，稱之為“寬度優(yōu)先”； 怎樣標(biāo)記一層的左右位置是編程的關(guān)鍵,用結(jié)構(gòu)數(shù)組來表示隊(duì)列 struct qtype /定義有兩個成員的結(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ù)組，用來存儲騎士們在棋盤上的起始位置,void init() /初始化函數(shù) /init memset(be

12、st,-1,sizeof(best); /初始化數(shù)組元素的值均為-1， int i=0; reci.x=0; /第0號騎士的 x 坐標(biāo)點(diǎn) reci.y=0; /第0號騎士的 y 坐標(biāo)點(diǎn) bestireci.xreci.y=0; /將第0號騎士在棋盤上的跳步信息置 為0，表示此處為出發(fā)點(diǎn) /init,/假定只有一個騎士 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會不斷增加 /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號騎士能否跳至(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號騎士跳至 /（x1,y1）的跳步信息 /if /for k /for am 從m 到 sq 作為一層已擴(kuò)展完畢,/之后，將下一段的開始sq+1賦給m,m是待擴(kuò)展的段頭

15、，段尾是新擴(kuò)展出的tail m=sq+1; /擴(kuò)展下一層時，是從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個騎士跳至座標(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ǔ)上，我們來研究騎士聚會問題。 任務(wù)：在88的棋盤上，輸入n個騎士的出發(fā)點(diǎn)，假定騎士每天只能跳一步，計算n個人的最早聚會地點(diǎn)和走多少天。要求盡早聚會，且n個人走的總步數(shù)最少。騎士的跳步按中國象棋的馬來跳。,解題思路： 從小到大，從簡到繁，先討論5*5的棋盤 從個別到一般 理思路 假定有4個騎士，初始位置

17、分別在 (0,0),(1,4),(1,2),(3,4) 5 對每一個騎士做擴(kuò)展，得到如下4張?zhí)叫畔D,0 3 2 3 2 0號騎士的 跳步圖 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號騎士的 跳步圖 2 3 2 3 0 數(shù) 字 3 2 1 2 3 放 在 2 3 4 1 2 右 上 3 2 3 2 3 角,2號騎士的 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號騎士的 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張落在一起，這時你可以看到每一個格子里有4個數(shù)據(jù)，分別屬于4個騎士的跳步信息 0號騎士的 1號騎士的 1 2 2 2 2號騎士的 3號騎士的 該方格坐標(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 每個格子 1 3 2 2 3 1 2 2 1 3 有 4 個數(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,依次對每個格子進(jìn)行觀察： 格子里4個數(shù)中最大的那個數(shù)，就是在該位置聚會所需天數(shù)，這是該位置的標(biāo)志性的數(shù)字。 按照題目要求尋找盡早聚會位置，即標(biāo)志性數(shù)字最小的格子。有可能這種格子不止一個，這時再比較4個騎士跳到這些位置上的總步數(shù)。最早聚會且4個人總步數(shù)也最少的位置即為所求。 下圖位置(2,1)是最佳聚會位置 用2天時間，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 會 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,搜索騎士們的最佳聚會位置 初始化棋盤，輸入n個騎士的初始位置 BFS（）寬度優(yōu)先對每一個騎士擴(kuò)展馬的跳步信息 計算在位置(x,y)上的 n個人中的最多跳步 goodxy.max n個人的跳步總和 goodxy.sum x,y=0,1,T-1 枚舉棋盤上的每個格子尋找 goodx

21、y.max 的最小值,min= min goodxy.max 1 x,y x,y = 0,1,T-1 在滿足 1 式的前提下，尋找個人跳步總和最小的格子位置 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個騎士的出發(fā)點(diǎn)，假定騎士每天只能跳一步，計算n個人的聚會地點(diǎn)和走多少天。 要求盡早聚會（走的天數(shù)最少）且 n個人走的總步數(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個跳步方向上的x增量 dy8=-2,-1,1,2,2,1,-1,-2;/8個跳步方向上的y增量 int n; /騎士數(shù)目n int x,y; /定義棋盤坐標(biāo)x和y，全局變量 struct qtype /定義有兩個成員的結(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ù)組，用來存儲騎士們在棋盤

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

24、維數(shù)組元素的值為1，表示棋盤中的每個格子都未曾填過信息 coutn; /提示并輸入騎士的數(shù)目n for( int i=0;ireci.x; /提示并輸入第i號騎士的 x 坐標(biāo)點(diǎn) coutreci.y; /提示并輸入第i號騎士的 y 坐標(biāo)點(diǎn) bestireci.xreci.y=0; /將第i號騎士在棋盤上的跳步信息置為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) /對0,1,.,n-1號的每一個騎士進(jìn)行跳步處理 /for i int head=1; /定義隊(duì)頭head，并初始化為1 int tail=1; /定義隊(duì)尾tail，并初始化為1 queuehead.x=reci.x; /讓第i個騎士的坐標(biāo)點(diǎn)x入隊(duì) queuehead.y=reci.y; /讓第i個騎士的坐標(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會

26、不斷增加 /while int sq=tail; /定義中間變量sq，記住原來的隊(duì)尾tail for( int am=m;am=sq;am=am+1) /從 m 到 sq 作 為一個階段進(jìn)行擴(kuò)展 /for am for( int k=0;k8;k=k+1 ) /枚舉 k 的 8 個方向。 /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號騎士能否跳至(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號騎士跳 至（x1,y1）， /此處的跳步比原來增加了一步 /if /for k /for am 從m 到 sq 作為一段已擴(kuò)展完畢,m=sq+1; / m是待擴(kuò)展的段頭， / 段尾是新擴(kuò)展出的tail step=step+1; /擴(kuò)展下一段時，步數(shù)需加1 /while /for i /BFS(),void display() /顯示棋局（調(diào)試過程用到過） /display for(int i=0;in;i=i+1) /枚舉0,1,.,n-1 每個騎士 /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個騎士跳至座標(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、) /搜索騎士們聚會的最佳位置 /seach BFS(); /寬度優(yōu)先擴(kuò)展馬的跳步 int minx,miny; /定義最佳聚會位置 /對每個棋盤格子計算n個人跳至此處的總步數(shù)和其中某人的最多步數(shù) for( x=0;xT;x=x+1) for( y=0;yT;y=y+1) /for y goodxy.sum=0; /求和前預(yù)置0 （計算n個人的跳步和） goodxy.max = -1;,/ 調(diào)試用來查看每個棋盤格子上所有n個人比較后的最大跳步值及所有n個人的跳步和 cout goodxy.max ) goodxy.max=bestjxy; /記錄在（x,y）格子處n個人比較后的最大跳步值 /for j /for y,cout y: 0 1 2 3 4 5 6 7 endl; coutx:; for( x=0;xT;x+)