下载文档原格式
盲目搜索搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程离散的问题通常没有统一的求解方法搜索策略的优劣涉及能否找到最好的解、计算时间、存储空间等搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。
效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造盲目搜索也叫无信息搜索，只适合用于求解比较简单的问题。
我们没有指定问题的任何推理信息，例如要搜索这一部分而不是另一部分，就像到目前为止的只要发现一条到目标的路径即可。
这种过程被称为是盲目的。
盲目搜索过程只把算子应用到节点，它没有使用问题领域的任何特殊知识（除了关于什么动作是合法的知识外）。
最简单的盲目搜索过程就是广度优先搜索。
该过程把所有的算子应用到开始节点以产生一个显式的状态空间图，再把所有可能的算子应用到开始节点的所有直接后继，再到后继的后继，等等。
搜索过程一律从开始节点向外扩展。
由于每一步将所有可能的算子应用到一个节点，因此可把它们组成一个叫后继函数的函数。
当把后继函数应用到一个节点时，产生一个节点集，该节点集就是把所有能应用到那个节点的算子应用到该节点而产生的。
一个节点的后继函数的每一次应用称为节点的扩展相同代价搜索是广度优先搜索的一种变体，在该方法中，节点从开始节点顺着代价等高点向外扩展，而不是顺着相同深度等高线。
如果图中所有弧的代价相同，那么相同代价搜索就和广度优先搜索一致。
反过来，相同代价搜索可以看作是下一章要讲的启发式搜索的一个特殊情况。
广度优先和相同代价搜索方法的简要描述只给出了它们的主要思想，但是要解决其他复杂的情况则需要技术改进深度优先搜索一次对节点应用一个算子以产生该节点的一个后继。
每一个节点都留下一个标记，用来指示如果需要时所必需的附加算子。
对每一个节点，必须有一个决策来决定哪个算子先用，哪个次之等等。
启发算法与盲目算法一、盲目搜索对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。
在所有搜索方式中，广度优先算法和深度优先搜索算法都十分重要，因为它们提供了一套系统地访问图数据结构的方法。
我们着重讲解广度优先搜索算法。
1.深度优先搜索深度优先搜索算法（简称DFS）是一种用于遍历或搜索树或图的算法。
沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
当节点的所在边都己被探寻过，搜索将回溯到发现节点的那条边的起始节点。
这一过程一直进行到已发现从源节点可达的所有节点为止。
由于深度优先搜索不是接下来最短路径算法的基础，因此这里不做拓展。
2.广度优先搜索广度优先搜索算法（简称BFS）又称为宽度优先搜索从起点开始，首先遍历起点周围邻近的点，然后再遍历已经遍历过的点邻近的点，逐步的向外扩散，直到找到终点。
在执行算法的过程中，每个点需要记录达到该点的前一个点的位置—父节点。
这样做之后，一旦到达终点，便可以从终点开始，反过来顺着父节点的顺序找到起点，由此就构成了一条路径。
以上两种算法的不同搜索策略可以通过下面网页查看动图，这是两种相邻节点之间的移动代价相等时用到的算法，图中的边不设权值。
3.Dijkstra算法Dijkstra算法是由计算机科学家Edsger W.Dijkstra在1956年提出的。
考虑这样一种场景，在一些情况下，图形中相邻节点之间的移动代价并不相等。
例如，游戏中的一幅图，既有平地也有山脉，那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。
在Dijkstra算法中，需要计算每一个节点距离起点的总移动代价。
同时，还需要一个优先队列结构。
对于所有待遍历的节点，放入优先队列中会按照代价进行排序。
在算法运行的过程中，每次都从优先队列中选出代价最小的作为下一个遍历的节点。
直到到达终点为止。
对比了不考虑节点移动代价差异的广度优先搜索与考虑移动代价的Dijkstra算法。
可以看出当图形为网格图，并且每个节点之间的移动代价是相等的，那么Dijkstra算法将和广度优先算法变得一样。
一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
例如：图1 八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或A* 算法）编程求解八数码问题（初始状态任选）。
选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。
二、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验算法A*算法是一种常用的启发式搜索算法。
在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。
A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n)这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。
由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n) = g(n) + h(n)其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。
在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。
用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。
这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。
（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。
实验一基本的搜索技术【实验目的】通过运行演示程序，理解深度优先、广度优先、A*算法的原理和运行过程。
【实验内容】1.分别以深度优先、广度优先、A*算法为例演示搜索过程2.观察运行过程记录搜索顺序3.设置不同属性，观察和记录搜索过程的变化4.分析不同算法的特点【实验原理】在知识不完全时，一般不存在成熟的求解算法可以利用，只有利用已有的知识摸索前进，从许多可能的解中寻找真正的解这就是搜索。
即使对于结构性能较好，理论上有算法可依的问题，由于问题本身的复杂性以及计算机在时间、空间上的局限性，往往也需要通过搜索来进行求解。
总的来说搜索策略分为两大类：盲目搜索和启发式搜索一、无信息的搜索策略——盲目搜索在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随即调用操作算子）进行的搜索，它能快速地运用一个操作算子。
盲目搜索中，由于没有可参考的信息，因此只要能匹配的操作算子都须运用，这会搜索更多的状态。
最重要的宽度优先和深度优先是最重要的盲目搜索方法。
1. 宽度优先搜索：从根结点出发，按从低到高的层次顺序搜索，同一层的结点按固定的顺序（例如从左到右、从右到左）搜索。
宽度优先总是先搜索到距离最近的目标结点。
宽度优先搜索不适合用于分支较多的情况。
2. 深度优先搜索：用回溯的思想搜索图。
深度优先搜索适用于分支较多而层次较浅的情况。
二、利用知识引导搜索——启发式搜索盲目搜索复杂度很大，为了提高算法效率，应该具体问题具体分析，利用与问题有关的信息，从中得到启发而来引导搜索，以达到减少搜索量的目的，这就是启发式搜索。
启发信息：(1) 陈述性启发信息：一般被用于更准确、更精炼地描述状态，使问题的状态空间缩小,如待求问题的特定状况等属于此类信息(2) 过程性启发信息：一般被用于构造操作算子，使操作算子少而精如一些规律性知识等属于此类信息(3) 控制性启发信息：如何选择操作算子控制性启发信息往往被反映在估价函数之中。
估价函数的任务就是估计待搜索结点的“有希望”程度(或者说估计操作算子的“性能”)，并依此给它们排定次序。
人工智能概论大作业学院：电子工程学院专业：智能科学与技术题目一：搜索算法编程及实验报告一．算法题目八数码难题的求解。
二．实验目的从盲目搜索和启发式搜索方法中分别选择一种解决八数码难题，给出搜索树和从起始节点到目标节点的路径。
三．实验设备及软件环境Win7的笔记本电脑，VS2013（使用c语言编程）。
四．实验方法1.盲目搜索——宽度优先搜索。
（1）.算法描述如果搜索是以接近其实节点的程度来依次扩展节点，那么这中搜索就叫宽度优先搜索。
这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。
(1）把起始节点放到OPEN表中（如果该起始节点为一目标节点，则求得一个解答）。
（2）如果OPEN是个空表，则没有解，失败退出；否则继续。
（3）把第一个节点（节点 n）从OPEN表移出，并把它放入CLOSED扩展节点表中。
（4）扩展节点n。
如果没有后继节点，则转向上述第（2）步。
（5）把n 的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。
（6）如果n 的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第（2）步。
（2）.算法流程图（3）.程序代码#include "stdio.h"#include "conio.h"#include "string.h" struct pic{char data[10];char imoperate;int father;char extend; };char end[10] = "1238 4765";int result[100];int n;int m;pic base[100];char *w;int find(int x){for (int i = 0; i < 10; i++)if (base[x].data[i] != end[i])return 0;return 1;}void showline(int x){int i = 0;while (base[x].father != -1){result[i] = x;x = base[x].father;i++;}result[i] = 0;result[i + 1] = '\0';m = i;printf("\n搜索路径");for (i = m; i >= 0; i--){printf("\n\n\n");printf("%c\t%c\t%c\n", base[result[i]].data[0], base[result[i]].data[1], base[result[i]].data[2]);printf("%c\t%c\t%c\n", base[result[i]].data[3], base[result[i]].data[4], base[result[i]].data[5]);printf("%c\t%c\t%c", base[result[i]].data[6], base[result[i]].data[7], base[result[i]].data[8]);}}int left(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 0 || i == 3 || i == 6)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i] = base[x].data[i - 1];base[n].father = x;base[n].imoperate = 'R';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int right(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 2 || i == 5 || i == 8)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i + 1] = base[x].data[i];base[n].father = x;base[n].imoperate = 'L';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int up(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] == ' ')break;if (i == 0 || i == 1 || i == 2)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i - 3] = base[x].data[i];base[n].data[i] = base[x].data[i - 3];base[n].father = x;base[n].imoperate = 'D';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}int down(int x){int i;for (i = 0; i < 10; i++)if (base[x].data[i] ==' ')break;if (i == 6 || i == 7 || i == 8)return 0;for (int j = 0; j < 10; j++)base[n].data[j] = base[x].data[j];base[n].data[i + 3] = base[x].data[i];base[n].data[i] = base[x].data[i + 3];base[n].father = x;base[n].imoperate = 'U';base[n].extend = 'Y';base[x].extend = 'N';w = base[n].data;n++;if (find(n - 1) == 1)return 1;}void main(){void showtree(int x);n = 1;int i;strcpy_s(base[0].data, "2831 4765");base[0].imoperate = 'N';base[0].father = -1;base[0].extend = 'Y';for ( i = 0; i < 100; i++){if (base[i].extend == 'Y'){if (base[i].imoperate == 'L'){if (right(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'R') {if (left(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'U') {if (left(i) == 1)break;if (right(i) == 1)break;if (down(i) == 1)break;continue;}if (base[i].imoperate == 'D') {if (right(i) == 1)break;if (up(i) == 1)break;if (left(i) == 1)break;continue;}if (base[i].imoperate == 'N') {if (left(i) == 1)break;if (right(i) == 1)break;if (up(i) == 1)break;if (down(i) == 1)break;continue;}}}printf("搜索结束\n");showline(n - 1);showtree(n - 1);getchar();}void showtree(int x){printf("\n\n\n搜索树\n\n\n");int i;for (i = 0; i <= x; i++){if (i == 0){printf("\t\t\t %c%c%c\n", base[i].data[0], base[i].data[1], base[i].data[2]);printf("\t\t\t %c%c%c\n", base[i].data[3], base[i].data[4], base[i].data[5]);base[i].data[7], base[i].data[8]);printf("\t\t\t |\n");printf(" ");for (int j = 0; j < 49; j++)printf("-");printf("\n");printf(" |");printf(" |");printf(" |");printf(" |\n");continue;}if (i>0 && i <= 4){printf(" %c%c%c", base[i].data[0],base[i].data[1], base[i].data[2]);printf("\t %c%c%c", base[i+1].data[0], base[i+1].data[1], base[i+1].data[2]);printf("\t %c%c%c", base[i+2].data[0], base[i+2].data[1], base[i+2].data[2]);printf("\t %c%c%c\n", base[i+3].data[0], base[i+3].data[1], base[i+3].data[2]);printf(" %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);base[i+1].data[4], base[i+1].data[5]);printf("\t %c%c%c", base[i+2].data[3], base[i+2].data[4], base[i+2].data[5]);printf("\t %c%c%c\n", base[i+3].data[3], base[i+3].data[4], base[i+3].data[5]);printf(" %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);printf("\t %c%c%c", base[i+1].data[6], base[i+1].data[7], base[i+1].data[8]);printf("\t %c%c%c", base[i+2].data[6], base[i+2].data[7], base[i+2].data[8]);printf("\t %c%c%c\n", base[i+3].data[6], base[i+3].data[7], base[i+3].data[8]);printf(" |");printf(" |");printf(" |");printf(" |\n");printf(" ---------");printf(" ---------");printf(" ---------");printf(" ---------\n");printf(" | |");printf(" | |");printf(" | |");printf(" | |\n");i = 4;continue;}if (i > 4 && i <= 12){printf(" %c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i+j].data[0],base[i+j].data[1], base[i+j].data[2]);printf("\n %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);printf("\n | |");printf(" | |");printf(" | |");printf(" | |\n");i = 12;continue;}if (i > 12 && i <= 20){printf(" %c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[0], base[i + j].data[1], base[i + j].data[2]);printf("\n %c%c%c", base[i].data[3],base[i].data[4], base[i].data[5]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n %c%c%c", base[i].data[6],base[i].data[7], base[i].data[8]);for (int j = 1; j < 8; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);printf("\n | |");printf(" | |");printf(" | |");printf(" | |\n");printf(" -----");for (int j = 0; j < 7;j++)printf(" -----");printf("\n | |");for (int j = 0; j < 7; j++)printf(" | |");i = 20;continue;}if (i>20 && i <= 36){printf("\n%c%c%c", base[i].data[0], base[i].data[1], base[i].data[2]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[0], base[i + j].data[1], base[i + j].data[2]);printf("\n%c%c%c", base[i].data[3], base[i].data[4], base[i].data[5]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[3], base[i + j].data[4], base[i + j].data[5]);printf("\n%c%c%c", base[i].data[6], base[i].data[7], base[i].data[8]);for (int j = 1; j < 11; j++)printf(" %c%c%c", base[i + j].data[6], base[i + j].data[7], base[i + j].data[8]);i = 36;continue;}}}2.启发式搜索——有序搜索（1）算法描述有序搜索又称最好优先搜索，他总是选择最有希望的节点作为下一个要扩展的节点。
引言概述推箱子是一种常见的游戏，也是计算机算法和研究中的经典问题，它涉及的算法和方法有助于提高问题解决能力和逻辑思维能力。
本文将对推箱子实验进行详细分析和讨论，包括推箱子游戏的定义、规则和目标，以及解决推箱子难题的算法和策略。
正文内容1.推箱子游戏的定义、规则和目标1.1定义：推箱子是一种益智类游戏，玩家需要将箱子推到指定位置，才能过关。
1.2规则：玩家通过控制一个游戏角色，推动箱子向指定位置移动，但箱子无法直接移动至目标位置。
1.3目标：玩家需要以最少的移动步数将所有箱子推至目标位置，即完成关卡。
2.解决推箱子难题的算法和策略2.1盲目搜索算法2.1.1深度优先搜索算法：从初始状态开始，一直沿着一个方向推动箱子，直到遇到障碍物为止。
2.1.2广度优先搜索算法：在每一步中，尝试所有可能的移动方向，并记录每个状态的移动路径，直到找到解决方案。
2.1.3双向搜索算法：从初始位置和目标位置同时开始搜索，直到两个搜索路径相交为止。
2.2启发式搜索算法2.2.1A算法：根据启发函数估计当前状态到目标状态的距离，选择距离最小的下一步移动方向。
2.2.2剪枝算法：通过预判某些状态的不可行性，提前排除无需尝试的移动方向。
2.2.3贪心算法：每次选择距离目标位置最近的箱子进行推动，以减少总体移动步数。
2.3知识表示与推理2.3.1逻辑推理：使用逻辑规则和推理算法进行箱子和角色的位置推理。
2.3.2状态空间搜索：将推箱子问题转化为状态空间搜索问题，通过搜索解空间来获得解法。
2.3.3约束满足问题：将箱子移动约束转化为约束满足问题，使用约束满足算法找到解决方案。
2.4强化学习方法2.4.1Q学习：使用状态动作奖励状态的马尔可夫决策过程进行学习和决策的强化学习方法。
2.4.2深度强化学习：基于深度神经网络的强化学习方法，通过大量样本数据进行模型训练和优化。
2.4.3遗传算法：通过基因编码和演化算子的操作，寻找最优的解决方案。
八数码问题实验报告八数码问题实验报告引言：八数码问题，也被称为九宫格问题，是一种经典的数学谜题。
在一个3x3的方格中，摆放有1至8的数字，其中一个位置为空。
目标是通过交换数字的位置，将数字按照从小到大的顺序排列，最终使得空格位于最后一个位置。
本实验旨在通过编程实现八数码问题的求解，并探讨不同算法在解决该问题上的效果和优劣。
实验步骤：1. 算法选择在本次实验中，我们选择了广度优先搜索算法和A*算法作为求解八数码问题的两种不同方法。
广度优先搜索算法是一种盲目搜索算法，它通过逐层扩展搜索树，直到找到目标状态。
而A*算法则是一种启发式搜索算法，它结合了广度优先搜索和启发式函数，通过评估每个状态的代价来指导搜索过程，以找到最优解。
2. 算法实现我们使用Python语言实现了以上两种算法。
首先，我们定义了一个表示状态的类，并实现了状态的初始化、移动、判断是否达到目标状态等基本操作。
然后，我们分别编写了广度优先搜索算法和A*算法的求解函数。
在广度优先搜索算法中，我们使用队列数据结构来保存待扩展的状态，以实现逐层扩展的效果；在A*算法中，我们使用优先队列来保存待扩展的状态，并根据启发式函数的值进行优先级排序。
3. 实验结果我们使用了多个测试样例来验证两种算法的求解效果。
实验结果表明，广度优先搜索算法能够找到解，但是在面对状态空间较大的情况下，搜索时间会呈指数级增长。
而A*算法则能够更快地找到最优解，其效率相对较高。
然而，A*算法需要选择合适的启发式函数，并且对于某些特殊情况，可能会陷入局部最优解而无法找到最优解。
4. 结果分析通过对比两种算法的求解结果，我们可以发现广度优先搜索算法和A*算法在时间效率和解的质量上存在一定的差异。
广度优先搜索算法适用于状态空间较小的情况，但是在状态空间较大时效率较低；而A*算法则能够在较短的时间内找到最优解，但需要对问题进行合理的建模和启发式函数的选择。
因此，在实际应用中，我们需要根据问题的规模和特点来选择合适的算法。
实验一：盲目搜索算法一、实验目的掌握盲目搜索算法之一的宽度优先搜索求解算法的基本思想。
对于宽度优先搜索算法基本过程，算法分析有一个清晰的思路，了解宽度优先搜索算法在实际生活中的应用。
二、实验环境PC机一台，VC++6.0三、实验原理宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。
同时，宽度优先搜索算法是连通图的一种遍历策略。
因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。
其基本思想是：(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。
(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。
(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。
(4) 扩展节点n。
如果没有后继节点，则转向上述第(2)步。
(5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。
(6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。
宽度优先搜索示意图和宽度优先算法流程图如下图1和图2所示：图2、宽度优先算法流程图四、实验数据及步骤这部分内容是通过一个实例来对宽度优先算法进行一个演示，分析其思想。
问题描述了《迷宫问题》的出路求解办法。
定义一个二维数组：int maze[5][5]={0，1，0，0，0，0，1，0，1，0，0，0，0，0，0，0，1，1，1，0，0，0，0，1，0，};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
题目保证了输入是一定有解的。
下面我们队问题进行求解：对应于题目的输入数组：0，1，0，0，0，0，1，0，1，0，0，0，0，0，0，0，1，1，1，0，0，0，0，1，0，我们把节点定义为(y，x)，(y，x)表示数组maze的项maze[x][y]。
于是起点就是(0，0)，终点是(4，4)。
我们大概梳理一遍：初始条件：起点Vs为(0，0)，终点Vd为(4，4)，灰色节点集合Q={}，初始化所有节点为白色节点，说明：初始全部都是白色（未访问），即将搜索起点（灰色），已经被搜索过了（黑色）。
开始我们的宽度搜索。
执行步骤：1.起始节点Vs变成灰色，加入队列Q，Q={(0，0)}2.取出队列Q的头一个节点Vn，Vn={0，0}，Q={}3.把Vn={0，0}染成黑色，取出Vn所有相邻的白色节点{(1，0)}4.不包含终点(4，4)，染成灰色，加入队列Q，Q={(1，0)}5.取出队列Q的头一个节点Vn，Vn={1，0}，Q={}6.把Vn={1，0}染成黑色，取出Vn所有相邻的白色节点{(2，0)}7.不包含终点(4，4)，染成灰色，加入队列Q，Q={(2，0)}8.取出队列Q的头一个节点Vn，Vn={2，0}，Q={}9.把Vn={2，0}染成黑色，取出Vn所有相邻的白色节点{(2，1)，(3，0)}10.不包含终点(4，4)，染成灰色，加入队列Q，Q={(2，1)，(3，0)}11.取出队列Q的头一个节点Vn，Vn={2，1}，Q={(3，0)}12. 把Vn={2，1}染成黑色，取出Vn所有相邻的白色节点{(2，2)}13.不包含终点(4，4)，染成灰色，加入队列Q，Q={(3，0)，(2，2)}14.持续下去，知道Vn的所有相邻的白色节点中包含了(4，4)……15.此时获得最终答案我们来看看广度搜索的过程中节点的顺序情况：图3迷宫问题的搜索树图中标号即为我们搜索过程中的顺序，我们观察到，这个搜索顺序是按照上图的层次关系来的，例如节点(0，0)在第1层，节点(1，0)在第2层，节点(2，0)在第3层，节点(2，1)和节点(3，0)在第3层。
我们的搜索顺序就是第一层->第二层->第三层->第N层这样子。
我们假设终点在第N层，因此我们搜索到的路径长度肯定是N，而且这个N 一定是所求最短的。
我们用简单的反证法来证明：假设终点在第N层上边出现过，例如第M层，M<N，那么我们在搜索的过程中，肯定是先搜索到第M层的，此时搜索到第M 层的时候发现终点出现过了，那么最短路径应该是M，而不是N了。
所以根据广度优先搜索的话，搜索到终点时，该路径一定是最短的。
五、实验核心代码/*** 广度优先搜索*/void course(char **maze,int hang,int lie){int i=1,j=1,n=-1;step *Step; //定义一个存储行走路线的栈Step=new step [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<<"步: "<<"向右走到: "<<"("<<i<<","<<j<<")"<<endl;}else if(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;}else 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<<"步: "<<"向左走到: "<<"("<<i<<","<<j<<")"<<endl;}else if(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;}else if(maze[i+1][j+1]!='1'&&maze[i+1][j+1]!='.'&&maze[i+1][j+1]!='+')//向右下走{maze[i+1][j+1]='.';j=j+1;i=i+1;n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步: "<<"向右下走到: "<<"("<<i<<","<<j<<")"<<endl;}else if(maze[i+1][j-1]!='1'&&maze[i+1][j-1]!='.'&&maze[i+1][j-1]!='+')//向右上走{maze[i+1][j-1]='.';j=j+1;i=i-1;n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步: "<<"向右上走到: "<<"("<<i<<","<<j<<")"<<endl;}else if(maze[i-1][j+1]!='1'&&maze[i-1][j+1]!='.'&&maze[i-1][j+1]!='+')//向左下走{maze[i-1][j+1]='.';j=j-1;i=i+1;n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步: "<<"向左下走到: "<<"("<<i<<","<<j<<")"<<endl;}else if(maze[i-1][j-1]!='1'&&maze[i-1][j-1]!='.'&&maze[i-1][j-1]!='+')//向左上走{maze[i-1][j-1]='.';j=j-1;i=i-1;n++;Step[n].x=i;Step[n].y=j;cout<<"第"<<n<<"步: "<<"向左上走到: "<<"("<<i<<","<<j<<")"<<endl;}else //返回上一步{if(i==1&&j==1) //当回到入口时，说明无通路，结束循环break;else{maze[i][j]='+'; //将走不通的点置为+n--;i=Step[n].x;j=Step[n].y;cout<<"此路不通!返回至上一步: "<<"("<<i<<","<<j<<")"<<endl;//输出返回信息}}if(i==hang&&j==lie)cout<<"成功走到出口!!!"<<" "<<"共"<<n<<"步";}}outway(maze,hang,lie,i,j);//输出结果}实验结果如下：实验图中点的坐标转化为问题描述中的点：(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)六、实验总结通过本次实验，我掌握了宽度优先搜索算法的思想方法，对于其分析流程有了很清晰的思路，盲目搜索算法中的宽度优先搜索算法应用于实际生活中求解分析问题就有很重要的意义。
