广度优先搜索算法实验报告（含算法实现思路，代码与运行结果，易错点提醒，以及实验中可能遇到的问题和解决办法）_广度优先搜索实验总结

实验项目名称

广度优先搜索

一、实验目的与要求：

目的：利用广度优先搜索算法，找到一条从起点到目标结点的最优路径。熟悉并掌握广度优先搜索算法的实现步骤以及算法流程，其核心思想是利用队列先进先出的特点，将已拓展的结点放在队列中，必要时记录其父节点，便于输出路径，不断拓展，若存在最优路径，则按要求输出路径或者到达目标结点所需的最短时间或者最短长度。

要求：编写几个使用广度优先搜索算法设计的程序，说明其大致的算法思路，调通程序并完成样例测试，完成实验报告。

二、实验设备及软件：

设备：荣耀笔记本电脑

软件：Visual Studio、浏览器、WPS、截图工具

三、实验方法（原理、流程图）

各算法大致思路如下：

1、Catch That Cow问题：

（1）定义结构体Step，其中整型变量x记录农夫所在的位置，steps记录农夫移动到x时所花费的时间，x与steps值均大于等于0，小于等于Max；

（2）用visited数组记录所有点的位置，若农夫已经经过该点，则值置为1，否则置为0；因为问题要求抓住牛的最少时间，为了提高搜索效率，所以规定：若该点已经经过，但没有得到最优路径，则不重复经过；

（3）初始时，将农夫的位置N入队，此时花费时间为0，即q.push(Step(N, 0))；

然后当队列不为空时，首先判断队首元素s的x值是否恰好等于目标位置K，若是，则输出s的steps值，就是最少时间；若不是，则将队首元素s进行拓展，将拓展后的元素结点入队，最后让s出队；

（4）队首元素s的拓展：

①基本条件为：拓展后的结点元素位置>=0或者<=Max，而且其对应的visited数组值不能为1，即之前不能被访问过；

②拓展方式有3种：关键在于理清农夫位置的移动方式，分别是从s.x到s.x-1；从s.x到s.x+1；从s.x到2*s.x；每移动一次，s.steps值加1，相应的位置对应的visited数组值需要置为1。

（5）若队列中元素为空，则说明无论结点怎么拓展，都无法抓住牛，则退出程序，输出内容为空。

【注意队首元素出队，可以放在元素拓展完之后的else语句中，也可以放在if……else语句外，确保其最后执行即可】

2、拯救行动问题：

（1）输入数据涉及到二维数组，所以定义结构体Position，其中整型变量r记录骑士所在位置行数，c记录骑士所在位置列数，time记录骑士行动的时间，而且r不能超过N，c不能超过M，三者均大于等于0；

（2）用字符型二维数组a[i][j]记录牢房的布局，输入数据时，当发现骑士的位置‘r’时，对应i和j分别表示结构体中的行数r与列数c，此时time值为0，将初始元素入队，即q.push(Position(i, j, 0))；

（3）在输入数据组数S不为0的while循环中，当队列不为空时，首先判断队首元素p，若再往上或者往下或者往左或者往右走一步，就能达到目标结点‘a’，则输出p的time值+1，就是行动的最短时间，然后退出循环；若预操作不能到达，则将队首元素p进行拓展，将拓展后的结点位置入队，最后让p出队；

（4）队首元素p的拓展：

①基本前提条件：记录骑士位置的下标r与c均不能越过数组下标的界限；牢房中‘#’表示墙壁，不能通行，骑士移动时需避开，‘x’表示守卫，若在拓展结点中，则需要战胜守卫；

②拓展方式有4种：分别是往下p.r+1；往上p.r-1；往右p.c+1；往左p.c-1；不能走有墙壁的地方，若遇到守卫，p.time+2，否则p.time+1；

（5）若经过拓展后，最终队列中元素为空，而且没有输出值后退出程序，则说明无论骑士怎么走，都无法拯救公主，则输出Impossible后，退出程序。

【程序中同样可以用visited数组记录牢房所有的位置以提高效率，若骑士已经经过则置为1，否则置为0，因为路径重复则意味着肯定不是最短时间】

3、鸣人与佐助问题：

【基本思路与拯救行动问题很像，但具体实现细节更复杂】

（1）定义结构体Information，与结构体Position相比，除了同样记录了鸣人行数r，列数c，所花费的时间time外，还记录了鸣人追上佐助过程中需要用到的查克拉数b，其中r与c不可越界，四者均大于等于0；

（2）用字符型二维数组a[i][j]记录地图的布局，输入数据时，当发现鸣人的位置‘@’时，对应i和j分别表示结构体中的行数r与列数c，此时b值与time值均为0，将初始元素入队，即q.push(Information(i, j, 0, 0));

（3）当队列不为空时，首先判断队首元素p，若再往上或者往下或者往左或者往右走一步，就能达到目标结点‘+’，此时还需判断走这条路径时用到的查克拉数p.b，若p.b<=T，说明这条路径是可行的，则输出p的time值+1，就是行动的最短时间，然后退出循环；若p.b>T，哪怕这条路径可以追上佐助，但是不可行，让队首元素p出队。若不能到达‘+’，则将队首元素p进行拓展，将拓展后的结点位置入队，最后让p出队；

（4）队首元素p的拓展：

①基本前提条件：记录骑士位置的下标r与c均不能越过数组下标的界限；地图中‘#’表示大蛇丸的手下，可以通行，但是每通过一个值为‘#’的地方，需要使用的查克拉数加1。

②拓展方式有4种：分别是往下p.r+1；往上p.r-1；往右p.c+1；往左p.c-1；若遇到大蛇丸的手下，则p.b+1，否则p.b不变；p.time一直都是加1

（5）若经过拓展后，最终队列中元素为空，而且没有输出值后退出程序，则说明无论鸣人怎么走，都无法追上佐助，则输出-1后，退出程序。

【本题中，不能用visited数组进行标记，因为通路太少，而且有查卡拉数限制，鸣人走的路线经过的结点需保证可以重复，才能找出最优解】

4、八数码问题：

（1）定义结构体Way，同样用整型变量r和c分别记录空格所在的行数与列数，

用string类型的变量direction记录空格移动的方向，r与c均不能越界，direction初始化为“”，上下左右移动时，direction分别加‘u’/‘d’/‘l’/‘r’；

（2）用goal数组记录目标状态，用字符型二维数组a记录输入的初始状态，用put数组记录元素是否归位，若已归位则置为1，否则置为0；用

（3）在输入数据时，当发现空格的位置‘x’时，对应i和j分别表示结构体中的行数r与列数c，并初始化字符串，将元素入队，即q.push(Way(i, j, ""))；同时若元素在输入时已归位，则将对应的put数组中的值置为1；

（4）当队列不为空时，首先判断put数组中值是否全部为1，若是，则说明元素全部归位达到目标状态，flag=true时输出p的direction值，就是空格的移动序列，然后退出循环；若put数组不全部为1，则置flag=false，将队首元素p进行拓展，将拓展后的结点位置入队，最后让p出队；</