资源描述：
《宽度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、声明：本课件版权归清华大学计算机系语音技术中心所有未经许可不得扩散宽度优先搜索任务：处在（0，0）位置上的象棋马跳到任何一个位置所需步数01234y003232134123221432332323423234x根据马的跳步规则研究8个方向的跳步增量dx[k],dy[k],k=0,1,…76-2-1012-25-170412k=0123k01234567dx1221-1-2-2-1dy-2-11221-1-2dx----马跳一步在x方向上的增量dy----马跳一步在y方向上的增量k-----方向号从（x,y）马跳一步到（x1,y1）x1=x+dx[k];01234y1=
2、y+dy[k];00如马的初始位置在(0,0)则11x1=0+dx[k]21y1=0+dy[k],k=0,1…734k01234567x11221-1-2-2-1y1-2-11221-1-2定义二维数组intw[5][5];用来存储每个格子中马的跳步信息对数组w进行初始化，目的是让每个格子只记录一次，避免重复记录。for(inti=0;i<=4;i++)for(intj=0;j<=4;j++)w[i][j]=-1;经初始化后的5x5格子中的数字均为-1012340-1-1-1-1-11-1-1-1-1-12-1-1-1-1-13-1-1-1-1-14-1-1-1-1-
3、1下面会看到，格子中的数为-1时才允许存入跳步信息。马从（0，0）跳一步，有两个可行位置（2，1）--------k=2（1，2）--------k=3称（0，0）为结点，（2，1）和（1，2）为由（0，0）扩展出的结点00，0）1（2，1）1（1，2）马由（0，0）跳一步到（2，1）和（1，2）再跳一步到（4，0）（4，2）（3，3）（3，1）（2，0）（0，2）（1，3）（4，2）（4，0）见下图，重点看：标有2的黄色的5个结点是由结点（2，1）扩展出来的；标有2的黑色的4个结点是由结点（1，2）扩展出来的。01234y00-12-121-1-112-1221-1
4、-123-12-12-142-12-1-1x0（0,0）1（2,1）1（1,2）222222222(4,0)(4,2)(3,3)(1,3)(0,2)(2,0)(3,1)(2,4)(0,4)怎样来描述与实现这种扩展过程呢？需要引入队列数据结构队列的基本概念队列是限定在一端进行插入，在另一端进行删除的特殊的线性表。像食堂排队买饭，后来的人排在队尾（插入），队头上的人买完饭后离队（删除）。所有需要进队的数据项只能从队尾进入；所有需要出队的数据项只能从队头离开。先入队的元素先出队，这种表又称为先进先出表（FIFO表）。队列可用数组表示，在队列运算中要设两个指针：队头指针---
5、-----head队尾指针--------tailq1234567headtailtemp=q[tail];tail=tail+1;q[tail]=temp+1;q12345678headtail将马的跳步信息放入队列中，用到以下5条语句：tail=tail+1;queue[tail].x=x1;queue[tail].y=y1;queue[tail].k=k;queue[tail].step=step;1个待扩结点k/230(0,0)x021y01211step011(2,1)(1,2)tail123扩展出2个结点m=head=1,sq=tail=1对m到sq区间内
6、的结点进行扩展k/23123450134x021443102320y012023320144w011222222222tail123456789101112msqm=2,sq=3对m到sq区间内的结点进行扩展sqk/23123450134x021443102320y012023320144step011222222222tail123456789101112mm=2,sq=30（0,0）1（2,1）1（1,2）2个待扩结点222222222(4,0)(4,2)(3,3)(1,3)(0,2)(2,0)(3,1)(2,4)(0,4)扩展出9个结点k/23123450134
7、x021443102320y012023320144w011222222222tail123456789101112m=4,sq=12msq对m到sq区间内的结点进行扩展0123400323213-1123221-13233232342323-1(0,0)123(2,1)(1,2)412(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园圈中的数字为该结点在队列中的序号01234y00323213412322
