实验一、盲目搜索算法.docx

: .
实验一：盲目搜索算法一、实验目的
掌握盲目搜索算法之一的宽度优先搜索求解算法的根本思想。对丁宽度。
我们假设终点在第N层，因此我们搜索到的路径长度肯定是N，而且这个N一定是所求最短的。
我们用简单的反证法来证明：假设终点在第N层上边出现过，例如第M层,M＜N,那么我们在搜索的过程中，肯定是先搜索到第M层的，此时搜索到第M层的时候发现终点出现过了，那么最短路径应该是M,而不是N了。
所以根据广度优先搜索的话，搜索到终点时，该路径一定是最短的。
五、实验核心代码
/**
*广度优先搜索
*/
voidcourse（char**maze,inthang,intlie）
（inti=1,j=1,n=-1;step*Step;〃定义一个存储行走路线的栈Step=newstep[hang*lie];if（maze[1][1]=='1'）cout<<"此路无法行走!!!”<<endl<<endl;getchar();exit(0);}else(n++;maze[i][j]='.';//.表示入口Step[n].x=i;〃记录入口的坐标Step[n].y=j;while(maze[hang][lie]!='.')(
//'1'表小走不通，’+'表小已经走过但不通乂回来的路径，’.'表小已经走过并通了的路径
if(maze[i][j+1]!='1'&&maze[i][j+1]!='.'&&maze[i][j+1]!='+')//向右走(maze[i][j+1]='.';j=j+1;n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步："<<"向右走到：
"<<T<<i<<”,”<<j<<”)"<<endl;}elseif(maze[i+1][j]!='1'&&maze[i+1][j]!='.'&&maze[i+1][j]!='+')
〃向下走{maze[i+1][j]='.';i=i+1;n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步："<<"向下走到：
"<<T<<i<<”,”<<j<<”)”<<endl;}elseif(maze[i][j-1]!='T&&maze[i][j-1]!='.'&&maze[i][j-1]!='+')〃向左走maze[i][j-1]='.';j=j-1；n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步："<<"向左走到：
"<<"("<<i<<","<<j<<")"<<endl;}elseif(maze[i-1][j]!='1'&&maze[i-1][j]!='.'&&maze[i-1][j]!='+')〃向上走{maze[i-1][j]='.';i=i-1;n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步："<<"向上走到：
"<<"("<<i<<","<<j<<")"<<endl;}elseif(maze[i+1][j+1]!='1'&&maze[i+1][j+1]!='.'&&maze[i+1][j+1