下载文档原格式
盲目搜索搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程离散的问题通常没有统一的求解方法搜索策略的优劣涉及能否找到最好的解、计算时间、存储空间等搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。
效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造盲目搜索也叫无信息搜索，只适合用于求解比较简单的问题。
我们没有指定问题的任何推理信息，例如要搜索这一部分而不是另一部分，就像到目前为止的只要发现一条到目标的路径即可。
这种过程被称为是盲目的。
盲目搜索过程只把算子应用到节点，它没有使用问题领域的任何特殊知识（除了关于什么动作是合法的知识外）。
最简单的盲目搜索过程就是广度优先搜索。
该过程把所有的算子应用到开始节点以产生一个显式的状态空间图，再把所有可能的算子应用到开始节点的所有直接后继，再到后继的后继，等等。
搜索过程一律从开始节点向外扩展。
由于每一步将所有可能的算子应用到一个节点，因此可把它们组成一个叫后继函数的函数。
当把后继函数应用到一个节点时，产生一个节点集，该节点集就是把所有能应用到那个节点的算子应用到该节点而产生的。
一个节点的后继函数的每一次应用称为节点的扩展相同代价搜索是广度优先搜索的一种变体，在该方法中，节点从开始节点顺着代价等高点向外扩展，而不是顺着相同深度等高线。
如果图中所有弧的代价相同，那么相同代价搜索就和广度优先搜索一致。
反过来，相同代价搜索可以看作是下一章要讲的启发式搜索的一个特殊情况。
广度优先和相同代价搜索方法的简要描述只给出了它们的主要思想，但是要解决其他复杂的情况则需要技术改进深度优先搜索一次对节点应用一个算子以产生该节点的一个后继。
每一个节点都留下一个标记，用来指示如果需要时所必需的附加算子。
对每一个节点，必须有一个决策来决定哪个算子先用，哪个次之等等。
引言概述推箱子是一种常见的游戏，也是计算机算法和研究中的经典问题，它涉及的算法和方法有助于提高问题解决能力和逻辑思维能力。
本文将对推箱子实验进行详细分析和讨论，包括推箱子游戏的定义、规则和目标，以及解决推箱子难题的算法和策略。
正文内容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*算法则能够在较短的时间内找到最优解，但需要对问题进行合理的建模和启发式函数的选择。
因此，在实际应用中，我们需要根据问题的规模和特点来选择合适的算法。
一、实训背景随着互联网的普及和信息技术的发展，搜索引擎已成为人们获取信息的重要工具。
然而，在信息爆炸的时代，如何在海量信息中快速、准确地找到所需信息，成为了一个亟待解决的问题。
为了提高信息检索的效率，我们开展了盲目搜索实训，通过模拟实际搜索过程，探索有效的搜索策略。
二、实训目的1. 熟悉搜索引擎的基本操作和功能；2. 掌握信息检索的基本原则和技巧；3. 提高在海量信息中快速、准确地找到所需信息的能力；4. 培养批判性思维和信息素养。
三、实训内容1. 搜索引擎的选择与使用实训过程中，我们选择了百度、谷歌、搜狗等国内外主流搜索引擎进行实践。
通过对比分析，我们发现百度在中国市场占有率较高，且具有强大的中文搜索能力；谷歌则在全球范围内具有较高的搜索精度；搜狗则具有独特的语音搜索功能。
在实际操作中，我们根据需求选择合适的搜索引擎，并熟悉其操作界面和功能。
2. 信息检索的基本原则（1）相关性：搜索结果应与用户需求具有较高的相关性，避免无关信息的干扰；（2）准确性：搜索结果应准确反映用户需求，避免误导；（3）全面性：搜索结果应涵盖用户需求的相关领域，避免遗漏；（4）时效性：搜索结果应关注最新动态，避免过时信息的影响。
3. 信息检索的技巧（1）关键词优化：选择合适的关键词，提高搜索精度；（2）逻辑运算符：使用逻辑运算符（如AND、OR、NOT）进行组合搜索，提高搜索效果；（3）高级搜索：利用搜索引擎的高级搜索功能，如筛选时间、网站类型等，提高搜索效果；（4）搜索结果分析：对搜索结果进行筛选、排序和去重，提高信息质量。
四、实训过程1. 阶段一：搜索实践在实训过程中，我们针对不同的主题进行搜索，如科技、教育、娱乐等。
通过实践，我们发现：（1）关键词优化对于提高搜索精度至关重要；（2）逻辑运算符在组合搜索中具有重要作用；（3）高级搜索功能可以帮助我们更精确地找到所需信息。
2. 阶段二：案例分析我们选取了几个具有代表性的案例进行分析，如“人工智能”、“区块链”等。
启发式搜索A和A*搜索算法首先什么是启发式搜索？启发式搜索就是利用当前问题有关的信息作为启发式信息，这些信息是能够提升查找效率、减少搜索时间和减少查询次数的。
为了利用这些信息，我们定义了一个估价函数h(x)，h(x)是对当前状态x的一个估计，它表示x状态到目标点的距离。
那么由它表示的意义我们可以知道，当h(x)等于0时，说明到达了目标点。
一、A和A*搜搜算法介绍A搜索算法就是使用了估价函数的搜索算法，估价函数的一般形式是f(x)=g(x)+h(x)。
其任务就是估计待搜索有希望程度，赢一次给它们排定次序。
其中g(x)代表从初始结点到x结点的实际代价，h(x)是从当前结点到目标结点的代价，这个代价是估计出来的。
A*搜索算法是估价函数满足一定条件的算法，其限制条件是f(x)=g(x)+h(x)，代价函数g(x)大于0，h(x)的值不大于x到目标结点的实际代价h*(x)。
二、A和A*搜索算法运用搜索算法如下：①将初始节点S0放入Open表中。
②如Open表为空，则搜索失败，退出。
③把Open表的第一个节点取出，放入到Closed表中，并把该节点记为节点n。
④如果节点n是目标节点，则搜索成功，求得一个解，退出。
⑤扩展节点n，生成一组子节点，对既不在Open表中也不在Closed表中的子节点，计算出相应的估价函数值。
⑥把节点n的子节点放到Open表中。
⑦对Open表中的各节点按估价函数值从小到大排列；。
⑧转到②。
启发式通常用于资讯充份的搜寻算法，例如最好优先贪婪算法与A*。
最好优先贪婪算法会为启发式函数选择最低代价的节点；A*则会为g(n) + h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。
如果h(n)是可接受的（admissible）意即h(n)未曾付出超过达到目标的代价，则A*一定会找出最佳解。
最能感受到启发式算法好处的经典问题是n-puzzle。
此问题在计算错误的拼图图形，与计算任两块拼图的曼哈顿距离的总和以及它距离目的有多远时，使用了本算法。
//=================================//盲目搜索算法//=================================#include<iostream>#include<fstream>#include<sstream>using namespace std;//----------------------------------typedef int Mat[3][3];//定义3*3数组类型Mat wxf,aid;int n=0,nn=0;int p=0,num=0;typedef struct Node{Mat c;//存储每一步的结点矩阵int noway[4];//可以走的路线l,u,r,dint father;//指向父亲节点}Node;//结点结构typedef struct path{Mat d;//存储矩阵int tag;}path;//路径结构Node result[40000];//保留分解的结点path paths[10000];//保留解路径上的结点void change(Mat a,Mat b);//完成两个数组的赋值（将数组b的值赋给数组a）void input();//从文件读入初始状态void output();//将解路径输出到文件void print(Mat a);//显示输出int compare(Mat a);//判断是否为目标节点void judge(Mat a);//判断移动路线void movl(Mat a);//将0左移void movr(Mat a);//将0右移void movd(Mat a);//将0下移void movu(Mat a);//将0上移//----------------------------------void main(){input();change(result[n].c,wxf);result[n].father=-1;//设定初始允许移动方向judge(result[n].c);for(n=0;n<40000;n++){if(nn>=39999){for(int w=n;w<=nn;w++){if(compare(result[w].c)){n=w;goto ww;}}cout<<"已扩展了40000个结点"<<endl;cout<<"找不到目标结点"<<endl;return;}if(compare(result[n].c)){ww: while(n>=0){change(paths[p].d,result[n].c);paths[p].tag=n;n=result[n].father;num++;p++;}output();return;}else{/*========分解节点=============*/if(result[n].noway[0]){movl(result[n].c);}if(result[n].noway[1]){movu(result[n].c);}if(result[n].noway[2]){movr(result[n].c);}if(result[n].noway[3]){movd(result[n].c);}}}}//---------------------------------- void input(){ifstream startin("start.txt");int sj,si=0;for(string ss;getline(startin,ss);) {sj=0;istringstream sin(ss);for(int ia;sin>>ia;){wxf[si][sj]=ia;sj++;}si++;}ifstream endin("end.txt");int ei=0,ej;for(string es;getline(endin,es);){ej=0;istringstream sin(es);for(int ib;sin>>ib;){aid[ei][ej]=ib;ej++;}ei++;}}//--------------------------------- void print(Mat a){for(int ii=0;ii<3;++ii){for(int jj=0;jj<3;++jj)cout<<a[ii][jj]<<" ";cout<<endl;}cout<<" ↓"<<endl;}//----------------------------------int compare(Mat a){int m=0,mm=0,k=0;for(m=0;m<3;m++){for(mm=0;mm<3;mm++){if(a[m][mm]!=aid[m][mm])return 0;}}return 1;}//---------------------------------- void movl(Mat a){change(wxf,a);nn++;int i=0,j;for(;i<3;i++){for(j=0;j<3;j++){if(wxf[i][j]==0)goto movl;}}movl:wxf[i][j]=wxf[i][j-1];wxf[i][j-1]=0;change(result[nn].c,wxf);judge(result[nn].c);result[nn].father=n;result[nn].noway[2]=0;}//----------------------------------- void movr(Mat a){change(wxf,a);nn++;int i=0,j;for(;i<3;i++){for(j=0;j<3;j++){if(wxf[i][j]==0)goto movr;}}movr:wxf[i][j]=wxf[i][j+1];wxf[i][j+1]=0;change(result[nn].c,wxf);judge(result[nn].c);result[nn].father=n;result[nn].noway[0]=0;}//---------------------------------- void movd(Mat a){change(wxf,a);nn++;int i=0,j;for(;i<3;++i){for(j=0;j<3;++j){if(wxf[i][j]==0)goto movd;}}movd:wxf[i][j]=wxf[i+1][j];wxf[i+1][j]=0;change(result[nn].c,wxf);judge(result[nn].c);result[nn].father=n;result[nn].noway[1]=0;}//--------------------------------- void movu(Mat a){change(wxf,a);nn++;int i=0,j;for(;i<3;i++){for(j=0;j<3;j++){if(wxf[i][j]==0)goto movu;}}movu:wxf[i][j]=wxf[i-1][j];wxf[i-1][j]=0;change(result[nn].c,wxf);judge(result[nn].c);result[nn].father=n;result[nn].noway[3]=0;}//----------------------------------- void judge(Mat a){int q=0,qq;for(;q<3;q++){for(qq=0;qq<3;qq++){if(a[q][qq]==0)goto movtag;}}movtag:switch(q)//确定行号{case 0:{result[nn].noway[3]=1;result[nn].noway[1]=0;break;}case 2:{result[nn].noway[1]=1;result[nn].noway[3]=0;break;}default:{result[nn].noway[1]=1;result[nn].noway[3]=1;break;}}switch(qq)//确定列号{case 0:{result[nn].noway[2]=1;result[nn].noway[0]=0;break;}case 2:{result[nn].noway[0]=1;result[nn].noway[2]=0;break;}default:{result[nn].noway[2]=1;result[nn].noway[0]=1;break;}}}//--------------------------------------- void change(Mat a,Mat b){for(int e=0;e<3;e++)for(int ee=0;ee<3;ee++){a[e][ee]=b[e][ee];}}//--------------------------------------- void output(){ofstream out("path.txt");out<<"一共扩展出"<<nn<<"个结点"<<endl;for(p=num-1;p>=0;p--){out<<"结点"<<paths[p].tag<<endl;int j,i=0;for(;i<3;i++){for(j=0;j<3;j++){out<<paths[p].d[i][j]<<" ";}out<<endl;}out<<" ↓"<<endl;}out<<"正确的解路径"<<endl; }。
实验一：盲目搜索算法一、实验目的掌握盲目搜索算法之一的宽度优先搜索求解算法的基本思想。
对于宽度优先搜索算法基本过程，算法分析有一个清晰的思路，了解宽度优先搜索算法在实际生活中的应用。
二、实验环境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所示：图1、宽度优先搜索示意图图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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
启发式搜索实验报告2015-2016第1学期《人工智能基础》实验报告实验名称:启发式搜索算法专业班级学号姓名1、实验环境Visual C++ 6.02、实验目的和要求(复述问题)使用启发式算法求解8数码问题(1) 编制程序实现求解8数码问题A*算法，采用估价函数f(n)=d(n)+p(n)其中:d(n)是搜索树中结点n的深度;w(n)为节点n的数据库中错放的旗子个数;p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。
(2) 分析上述(1)中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。
实验目的:熟练掌握启发式搜索A*算法及其可采纳性。
3、解题思路、代码3.1解题思路八数码问题的求解算法(1) 盲目搜索宽度优先搜索算法、深度优先搜索算法(2) 启发式搜索启发式搜索算法的基本思想是:定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。
先定义下面几个函数的含义:f*(n)=g*(n)+h*(n) (1)式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。
评价函数的形式可定义如(2)式所示:f(n)=g(n)+h(n) (2)其中n是被评价的当前节点。
f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。
利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。
在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。
采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下:F(n)=d(n)+p(n) (4)1 / 112015-2016第1学期《人工智能基础》实验报告其中A*算法中的g(n)根据具体情况设计为d(n)，意为n节点的深度，而h(n)设计为p(n)，意为放错的数码与正确的位置距离之和。
人工智能概论大作业学院：电子工程学院专业：智能科学与技术题目一：搜索算法编程及实验报告一．算法题目八数码难题的求解。
二．实验目的从盲目搜索和启发式搜索方法中分别选择一种解决八数码难题，给出搜索树和从起始节点到目标节点的路径。
三．实验设备及软件环境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）算法描述有序搜索又称最好优先搜索，他总是选择最有希望的节点作为下一个要扩展的节点。
实验一：盲目搜索算法一、实验目的掌握盲目搜索算法之一的宽度优先搜索求解算法的基本思想。
对于宽度优先搜索算法基本过程，算法分析有一个清晰的思路，了解宽度优先搜索算法在实际生活中的应用。
二、实验环境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所示：图1、宽度优先搜索示意图图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;}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][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;}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]!='+')//向右下走{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;}elseif(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;}elseif(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;}elseif(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)六、实验总结通过本次实验，我掌握了宽度优先搜索算法的思想方法，对于其分析流程有了很清晰的思路，盲目搜索算法中的宽度优先搜索算法应用于实际生活中求解分析问题就有很重要的意义。
