《数据结构课程设计》报告
题目：深度与广度优先搜索
--迷宫问题
专业 计算机科学与技术
学生姓名 李柏 班级 B 计算机115 学
号
1110704512 指导教师 巩 永 旺 完成日期
2013年1月11日
目录
1简介 (1)
2算法说明 (1)
3测试结果 (3)
4分析与探讨 (7)
5小结 (8)
附录 (10)
附录1 源程序清单 (10)
迷宫问题
1 简介
1、图的存储结构
图的存储结构又称图的表示，其最常用的方法是邻接矩阵和邻接表。无论采用什么存储方式，其目标总是相同的，既不仅要存储图中各个顶点的信息，同时还要存储顶点之间的所有关系。
2、图的遍历
图的遍历就是从指定的某个顶点（称其为初始点）出发，按照一定的搜索方法对图中的所有顶点各做一次访问过程。根据搜索方法不同，遍历一般分为深度优先搜索遍历和广度优先搜索遍历。
本实验中用到的是广度优先搜索遍历。即首先访问初始点v i，并将其标记为已访问过，接着访问v i的所有未被访问过的邻接点，顺序任意，并均标记为已访问过，以此类推，直到图中所有和初始点v i有路径相通的顶点都被访问过为止。鉴于广度优先搜索是将所有路径同时按照顺序遍历，直到遍历出迷宫出口，生成的路径为最短路径。因此我们采用了广度优先搜索。
无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点。广度优先搜索采用队列作为数据结构。
本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。具体实验内容如下：
选择手动或者自动生成一个n×m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“☆”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫，则只输出迷宫原型图。
2算法说明
迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述。设置迷宫的长为n、宽为m，范围为49×49，用int maze[N+2][M+2]来表示，这样相当于在迷宫外层包了一层1，即防止搜索路径时跳出迷宫。
（1）手动生成迷宫
void hand_maze(int m,int n) //手动生成迷宫
{
int i,j;
for(i=0;i for(j=0;j { cin>>maze[i][j]; } } （2）自动生成迷宫 void automatic_maze(int m,int n) //自动生成迷宫 { int i,j; for(i=0;i for(j=0;j maze[i][j]=rand()%2; //随机生成0、1 maze[0][0]=0; //将开始和结束位置强制为0，保证有可能出来迷宫 maze[m-1][n-1]=0; } 2、迷宫路径的搜索 在生成的0、1矩阵迷宫中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其北（-1，0），东北（-1，1），东（0,1），东南（1,1），南（1,0），西南（1，-1），西（0，-1），西北（-1，-1）8个方向位，是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。逆序输出路径，将已输出的路径标记为3。 实验数据如下： 表3.1 方向move的偏移量 Name dir Move[dir].vert Move[dir].horiz N 0 -1 0 NE 1 -1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1 -1 W 6 0 -1 NW 6 0 -1 3测试结果 图1 图2 图3 图4 图5 图6 图7 4分析与探讨 首先明确题目中的已知条件： （1）迷宫是一个8*8大小的矩阵。 （2）从迷宫的左上角进入，右下角为迷宫的终点。 （3）maze[i][j]=0代表第i+1行第j+1列的点是通路；maze[i][j]=1代表该点是墙，无法通行。 （4）迷宫有两种生成方式：手工设定和自动生成。 （5）当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、下、左、右、左上、左下、右上、右下”8个方向。 （6）要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数组maze[N+2][N+2]来表示这个迷宫，其中N为迷宫的行、列数。当值为“0” 时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫的位置在任何时候都可以由行号row和列号cool表示。 （7）为什么指定: maze[N+2][N+2]来表示迷宫，而不是使用maze[N][N]来表示迷宫？原因是当老鼠跑到了迷宫的边界点时就有可能跳出迷宫，而使用maze[N+2][N+2]就可以把迷宫的外边再包一层“1”，这样就能阻止老鼠走出格。 （8）老鼠在每一点都有8种方向可以走，分别是：North，NorthEast，East，SouthEast, South,SouthWest,West，NorthWest。可以用数组move[8]来表示每一个方向上的横纵坐标的偏移量，见表 3.1。根据这个数组，就很容易计算出沿某个方向行走后的下一个点的坐标。 方向move的偏移量 迷宫问题可以用深度优先搜索方法实现。当老鼠在迷宫中移动的时候，可能会有许多种移动选择方向。程序需要记录并用栈来保存当前点的坐标，然后任意选择一个方向进行移动。由于应用栈保存了当前通道上各点的坐标，所以当在当前各 方向上都走不通时可以返回上一个点，然后选择另一个方向前进。 可定义element结构用于存储每一步的横纵坐标和方向。 typedef struct{ short int row; short int col; short int dir; }element; Element stack[MAX _STACK_SIZE]; 根据表3.1可推算出每次移动后的坐标。设当前的坐标是（row,col）,移动的方向是dir，移动后的点是next,则有 next_row=row+move[dir].vert; next_col=col+move[dir].horiz; 可用另一个二维数组mark[N+2]来记录哪些点已经被访问过。当经过点maze[row][col]时，相应地将mark[row][col]的值从0置为1。 本程序支持自动生成迷宫。利用random（2）函数可随机产生0或1，来支持迷宫的自动生成。注意maze[N][N]和maze[1][1]一定要等于0，因为他们分别是起点和终点。 如果找到了一条走出迷宫的路径，则需要在屏幕中打印出如图3.5所示格式的信息。这里要用到graphics.h即TC中的图形库（注意：本程序是TC上的实现，而VC++有自己的图形库，所以使用VC++编译提示错误）。针对图3.5，可使用circle （）函数画圆，outtexttxy（）函数标记文字，并用line（）函数来划线。 程序的主要函数如下： ●函数void add（int*top,element item），将当前步的信息item压入到作为全局变 量的栈stack（栈顶为top）中。 ●函数element delete（int * top），返回stack中栈顶的元素。 ●函数void path（void），采用深度优先搜索算法，首先取出栈顶元素作为当前 点选择一个方向前进到下一个点（如果能走得话）；然后，将下一个点压入栈，并将二维数组mark中对应的值改为1，表示该点已经走到了。反复执行上面两步，当走到一个点不能再走下去了（已经尝试了各个方向并失败），并且这个点不是终点，则这个点的上一个点会从栈中被跑抛出，从而“回朔”到上一点； 当遇到终点时，程序结束，找到一条路径；当在程序循环过程中遇到栈为空，则说明该迷宫根本无法走到终点。 5小结 为期一个星期的数据结构课程设计快结束了，这使我对深度和广度优先搜索有了更加深刻的理解和认识。我们团队负责的迷宫问题的课程设计就是充分的利用深度和广度优先搜索的有关知识，主要运用的是广度优先搜索遍历。 （1）深度优先搜索遍历：深度优先搜索是一个递归过程。首先访问一个顶点Vi并将其标记为已访问过，然后从Vi的任意一个未被访问的邻接点出发进行深度优先搜索遍历。如此执行，当Vi的所有邻接点均被访问过时，则退回到上一个顶点Vk，从Vk的另一未被访问过的邻接点出发进行深度优先搜索遍历。如此执行，直到退回到初始点并且没有未被访问过的邻接点为止。 （2）广度优先搜索遍历：广度优先搜索过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过的邻接点，其访问顺序可以任意，假定依次为Vi1、Vi2，…Vin，并标记为已访问过，然后按照Vi1、Vi2，…Vin的次序访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。在设计迷宫问题时要考虑使用二维数组，在数组中我们选择maze[N+2][N+2]来表示迷宫，而不是用maze[N][N]来表示，这样就可以避免老鼠走迷宫会出格。 通过这一个星期的学习实践，我更加深层次的了解了关于数据结构的相关知识，也越来越发现自己对数据结构方面知识的欠缺，使我对自己所学得的知识有了一个深刻的理解，对于这方面的知识，我还缺少很多，纸上得来终觉浅，再强大的理论也要通过实践来证明。在今后的学习中我要多练习，做一个专业的计算机学生。 参考文献 [1] 刘振安,刘燕君.C程序设计课程设计[M].[北京]机械工业出版社,2004年9月 [2] 谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月 [3] 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月 [4] 李志球《实用C语言程序设计教程》北京：电子工业出版社，1999 [5] 王立柱：C/C++与数据结构北京：清华大学出版社，2002 [6] 吴文虎《程序设计基础》北京：清华大学出版社，2003 [7] 郭福顺，王晓芬，李莲治《数据结构》（修订本），大连理工大学出版社，1997 [8] 潘道才，陈一华《数据结构》，电子科技大学出版社，1994 附录 附录1 源程序清单 #include #include using namespace std; #define N 49 //定义为全局变量,这是迷宫数组的上线，可以自行修改 #define M 49 int X; int maze[N+2][M+2]; int head=0,tail=0; //队列的头尾指针，初始值设为0 struct point //存放迷宫访问到点的队列结构体，包含列，行，序号 { int row,col,predecessor; }queue[1200]; void hand_maze(int m,int n) //手动生成迷宫 { int i,j; cout< cout<<"请按行输入迷宫，0表示通路，1表示障碍:"< for(i=0;i for(j=0;j { cin>>maze[i][j]; } } void automatic_maze(int m,int n) //自动生成迷宫 { int i,j; cout<<"\n迷宫生成中……\n\n"; system("pause"); for(i=0;i for(j=0;j maze[i][j]=rand()%2; //随机生成0、1 maze[0][0]=0; //将开始和结束位置强制为0，保证有可能出来迷宫 maze[m-1][n-1]=0; } void data(int m,int n) { //当用户输入的不是规整的m行n列的迷宫，用来生成规则的数字迷宫 int i,j; cout< cout<<"根据您先前设定的迷宫范围"< cout< cout<<" 我们将取所输入的前"< cout<<"\n数字迷宫生成结果如下:\n\n"; cout<<"迷宫入口\n"; cout<<"↓"; for(i=0;i { cout<<"\n"; for(j=0;j { if(maze[i][j]==0) cout<<" 0"; if(maze[i][j]==1) cout<<" 1"; } } cout<<"→迷宫出口\n"; } void print_maze(int m,int n) { //打印迷宫外壳int i,j,k; cout<<"\n字符迷宫生成结果如下:\n\n"; cout<<"迷宫入口\n"; cout<<" ↓"; cout< cout<<"▲"; //生成上外壳 for(k=0;k { cout<<"▲"; //这两个黑三角用来生成顶部外壳} for(i=0;i { cout<<"\n"; //生成左外壳 cout<<"▲"; for(j=0;j { if(maze[i][j]==0) printf("□"); if(maze[i][j]==1) printf("■"); } cout<<"▲"; //生成右外壳 } cout< for(k=0;k { cout<<"▲"; } cout<<" ▲\n"; //生成底部外壳 for(i=0;i { cout<<" ";} cout<<"↓\n"; for(i=0;i { cout<<" ";} cout<<"迷宫出口\n"; } void result_maze(int m,int n) //这个是打印输出迷宫的星号路径 { int i,j; cout<<"迷宫通路(用☆表示)如下所示：\n\t"; for(i=0;i { cout<<"\n"; for(j=0;j { if(maze[i][j]==0||maze[i][j]==2) //2是队列中访问过的点 cout<<"□"; if(maze[i][j]==1) cout<<"■"; if(maze[i][j]==3) //3是标记的可以走通的路径 cout<<"☆"; } } } void enqueue(struct point p) //迷宫中队列入队操作 { queue[tail]=p; tail++; //先用再加，队列尾部加1 } struct point dequeue() //迷宫中队列出队操作，不需要形参，因此用结构体定义 { head++; return queue[head-1]; } int is_empty() //判断队列是否为空 { return head==tail; } void visit(int row,int col,int maze[51][51]) //访问迷宫矩阵中的节点{ struct point visit_point={row,col,head-1}; //head-1的作用是正在访问的这个点的序号为之前的点序号 maze[row][col]=2; //将访问过的点位标记为2 enqueue(visit_point);//入队 } int path(int maze[51][51],int m,int n) //路径求解 { X=1; //初始值定为1 struct point p={0,0,-1}; //定义入口节点 if(maze[p.row][p.col]==1) //入口为1时，迷宫不可解 { cout<<"\n===============================================\n"; cout<<"此迷宫无解\n\n"; X=0; return 0; } maze[p.row][p.col]=2; //标记为已访问 enqueue(p); //将p入队列while(!is_empty()) { p=dequeue(); if((p.row==m-1)&&(p.col==n-1)) //当行和列为出口时跳出 break; //定义8个走位方向 if((((p.row-1)>=0)&&((p.row-1) visit(p.row-1,p.col+0,maze); //北 if((((p.row-1)>=0)&&((p.row-1) visit(p.row-1,p.col+1,maze); //东北 if((((p.row+0) visit(p.row+0,p.col+1,maze); //东 if((((p.row+1) visit(p.row+1,p.col+1,maze); //东南 if((((p.row+1) visit(p.row+1,p.col+0,maze); //南 if((((p.row+1) visit(p.row+1,p.col-1,maze); //西南 if((((p.row+0) visit(p.row+0,p.col-1,maze); //西 if((((p.row-1)>=0)&&((p.row-1) visit(p.row-1,p.col-1,maze); //西北 } if(p.row==m-1&&p.col==n-1) //如果当前矩阵点是出口点，输出路径 { cout<<"\n============================================================== ====\n"; cout<<"迷宫路径为：\n"; cout<<"出口"< cout<<" "<<"↑"< printf("(%d,%d)\n",p.row+1,p.col+1); cout<<" "<<"↑"< maze[p.row][p.col]=3; //逆序将路径标记为3 while(p.predecessor!=-1) { p=queue[p.predecessor]; printf("(%d,%d)\n",p.row+1,p.col+1); cout<<" "<<"↑"< maze[p.row][p.col]=3; } cout<<"入口"< } else { cout<<"\n=============================================================\n"; cout<<"此迷宫无解！\n\n"; X=0; } return 0; } void main() { int i,m,n,cycle=0; while(cycle!=(-1)) { cout<<"*************************************************************************** *****\n"; cout<<" 欢迎进入迷宫求解系统\n"; cout< cout<<" 设计者:李柏（B计算机115班）\n"; cout<<"*************************************************************************** *****\n"; cout<<" ☆手动生成迷宫请按：1\n"; cout<<" ☆自动生成迷宫请按：2\n"; cout<<" ☆退出请按：3\n\n"; cout<<"*************************************************************************** *****\n"; cout<<"\n"; cout<<"请选择你的操作：\n"; cin>>i; switch(i) { case 1: cout<<"\n请输入行数："; cin>>m; cout<<"\n"; cout<<"请输入列数："; cin>>n; while((m<0||m>49)||(n<0||n>49)) { cout<<"\n抱歉，你输入的行列数超出预设范围(0-49,0-49),请重新输入：\n\n"; cout<<"\n请输入行数："; cin>>m; cout<<"\n"; cout<<"请输入列数："; cin>>n; } hand_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0) result_maze(m,n); //当X不为0时，有解，调用输出路径函数 cout<<"\n\nPress Enter Contiue!\n"; getchar(); while(getchar()!='\n'); //接受一个输入，当为回车时执行break跳出，否则一直执行接受数据 break; case 2: cout<<"\n请输入行数："; cin>>m; cout<<"\n"; cout<<"请输入列数："; cin>>n; while((m<0||m>49)||(n<0||n>49)) { cout<<"\n抱歉，你输入的行列数超出预设范围(0-49,0-49),请重新输入：\n\n"; cout<<"\n请输入行数："; cin>>m; cout<<"\n"; cout<<"请输入列数："; cin>>n; } automatic_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0) result_maze(m,n); cout<<"\n\nPress Enter Contiue!\n"; getchar(); while(getchar()!='\n'); break; case 3: cycle=(-1);break; default: cout<<"\n";cout<<"你的输入有误!\n"; cout<<"\nPress Enter Contiue!\n"; getchar(); while(getchar()!='\n'); break; } } } 深度优先与广度优先 （一）深度优先搜索的特点是：（1）从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2- 7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法 （二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。（2）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当搜索深度较大时，如例题2- 5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。（3）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点 的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。（4）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。（5）从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 二、广度优先搜索法的显著特点是：（1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。（2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。（3）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一 合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。 深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。 所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s 一、实验目的 1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构； 2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用； 3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。 二、实验内容 实验内容1**图的遍历 [问题描述] 许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。 [基本要求] 建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。 [实现提示] 设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。 [程序代码] 头文件： #include < 人工智能 > 实验报告 3 一、实验目的： 掌握汉诺塔的深度有界搜索求解算法的基本思想。 二、实验要求： 用C语言实现汉诺塔的深度有界搜索求解 三、实验语言环境： C语言 四、设计思路： 含有深度界限的深度优先搜索算法如下： (1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。 (2) 如果OPEN为一空表，则失败退出。 (3) 把第一个节点(节点n)从OPEN表移到CLOSED表。 (4) 如果节点n的深度等于最大深度，则转向(2)。 (5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。 (6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。 五、实验代码： #include long floor; //记录第几层 } node; node queue[362880 / 2 + 1]; //奇偶各一半 long tail, head; long hash[362880 / 32 + 1]; int main() { void Solve(); while (scanf("%ld", &queue[0].map) && queue[0].map) { memset(hash, 0, sizeof(hash)); queue[0].floor = 1; //(根节点)第一层 tail = head = 0; Solve(); printf("max_floor == %d\n", queue[head].floor); printf("total node == %d\n", head + 1); printf("total node in theory [%d]\n", 362880 / 2); } return 0; } void Solve() { node e; long i, map[9], space; long Compress(long *); int V isited(long *); void swap(long &, long &); while (tail <= head) { e = queue[tail++]; for (i=8; i>=0; i--) { map[i] = e.map % 10; if (map[i] == 0) { space = i; } e.map /= 10; } V isited(map); //根节点要置为访问过 if (space >= 3) { //can up swap(map[space - 3], map[space]); if (!Visited(map)) { queue[++head].map = Compress(map); queue[head].floor = queue[tail - 1].floor + 1; 深度优先搜索和广度优先搜索的比较 （一）深度优先搜索的特点是： （1）从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2-7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。 但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法（二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。 （2）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当搜索深度较大时，如例题2-5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。 （3）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。 （4）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。 （5）从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。 如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 二、广度优先搜索法的显著特点是： （1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。 （2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。 （3）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度（或广度）优先搜索算法：找到一个目标后，不是立即退出，而是记录下目标结点的路径和费用，如果有多个目标结点，就加以比较，留下较优的结点。把所有可能的路径都搜索完后，才输出记录的最优路径。 （4）广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。 上机实验报告 学院：计算机与信息技术学院 专业：计算机科学与技术(师范）课程名称：数据结构 实验题目：深度优先遍历（邻接矩阵）班级序号：师范1班 学号：201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：2015年12月25号 一、实验目的： 1﹒掌握图的基本概念和邻接矩阵存储结构。 2﹒掌握图的邻接矩阵存储结构的算法实现。 3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。 二、实验环境： Windows 8.1 Microsoft Visual c++ 6.0 二、实验内容及要求： 编写图的深度优先遍历邻接矩阵算法。建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 四、概要设计： 深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。 以图中无向图G4为例，深度优先遍历图的过程如图所示。假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。依次类推，接着从V4,V8,V5出发进行搜索。在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。由此得到顶点的访问序列为： V1 V2 V4 V8 V5 V3 V6 V7 五、代码 #include 一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验容 编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20 有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有 连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。 深度优先搜索： 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。 下面图中的数字显示了深度优先搜索顶点被访问的顺序。 "* ■ J 严-* 4 t C '4 --------------------------------- --- _ 为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则： (1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。 (2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。 (3) 如果不能执行规则1和规则2，就完成了整个搜索过程。 广度优先搜索： 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。 在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中， 算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区 域。它是用队列来实现的。 下面图中的数字显示了广度优先搜索顶点被访问的顺序。 实现广度优先搜索，也要遵守三个规则: ⑴ 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。（2）如果因为已经没有未访问顶点而不能执行规则1 #include 第五章状态空间搜索策略 搜索是人工智能的一个基本问题，是推理不可分割的一部分。搜索是求解问 题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。搜索可分为盲目搜索和启发式搜索两种。 1．1 盲目搜索策略 1．状态空间图的搜索策略 为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。一般情况下，不同的知识表示对应着不同的求解方法。状态空间表示法是一 种用“状态”和“算符”表示问题的方法。状态空间可由一个三元组表示(S ，F， S g )。 利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。 算法5．1 状态空间图的一般搜索算法 ①建立一个只含有初始节点S 0的搜索图G，把S 放入OPEN表中。 ②建立CLOSED表，且置为空表。 ③判断OPEN表是否为空表，若为空，则问题无解，退出。 ④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。 ⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解 的这条路径得到。 即可从图G中沿着指针从n到S ⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。 ⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN 表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n 节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。 ⑧按某一任意方式或按某种策略重排OPEN表中节点的顺序。 ⑨转第③步。 2．宽度优先搜索策略 宽度优先搜索是一种盲目搜索策略。其基本思想是，从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面(即将扩展得到的后继节点放于OPEN表的末端)。 宽度优先搜索的盲目性较大，搜索效率低，这是它的缺点。但宽度优先搜索策略是完备的，即只要问题有解，用宽度优先搜索总可以找到它的解。 3．深度优先搜索 深度优先搜索也是一种盲目搜索策略，其基本思想是：首先扩展最新产生的 一、深度优先搜索和广度优先搜索的深入讨论 （一）深度优先搜索的特点是： （1）从上面几个实例看出，可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的，如例题2-4，2-5，2-6；有的是未知的，如例题2-7、例题2-8；有的搜索深度是有限制的，但达到目标的深度是不定的。 但也看到，无论问题的内容和性质以及求解要求如何不同，它们的程序结构都是相同的，即都是深度优先算法（一）和深度优先算法（二）中描述的算法结构，不相同的仅仅是存储结点数据结构和产生规则以及输出要求。 （2）深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当搜索深度较大时，如例题2-5、2-6。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。 （3）深度优先搜索方法有广义和狭义两种理解。广义的理解是，只要最新产生的结点（即深度最大的结点）先进行扩展的方法，就称为深度优先搜索方法。在这种理解情况下，深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是，仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法，实际上是在数据库中产生一个结点之间的搜索树，因此也属于图搜索算法的范畴。 （4）不保留全部结点的深度优先搜索法，由于把扩展望的结点从数据库中弹出删除，这样，一般在数据库中存储的结点数就是深度值，因此它占用的空间较少，所以，当搜索树的结点较多，用其他方法易产生内存溢出时，深度优先搜索不失为一种有效的算法。 （5）从输出结果可看出，深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13，但第一个解却是17。 如果要求出最优解的话，一种方法将是后面要介绍的动态规划法，另一种方法是修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。 二、广度优先搜索法的显著特点是： （1）在产生新的子结点时，深度越小的结点越先得到扩展，即先产生它的子结点。为使算法便于实现，存放结点的数据库一般用队列的结构。 （2）无论问题性质如何不同，利用广度优先搜索法解题的基本算法是相同的，但数据库中每一结点内容，产生式规则，根据不同的问题，有不同的内容和结构，就是同一问题也可以有不同的表示方法。 （3）当结点到跟结点的费用（有的书称为耗散值）和结点的深度成正比时，特别是当每一结点到根结点的费用等于深度时，用广度优先法得到的解是最优解，但如果不成正比，则得到的解不一定是最优解。这一类问题要求出最优解，一种方法是使用后面要介绍的其他方法求解，另外一种方法是改进前面深度（或广度）优先搜索算法：找到一个目标后，不是立即退出，而是记录下目标结点的路径和费用，如果有多个目标结点，就加以比较，留下较优的结点。把所有可能的路径都搜索完后，才输出记录的最优路径。 （4）广度优先搜索算法，一般需要存储产生的所有结点，占的存储空间要比深度优先大得多，因此程序设计中，必须考虑溢出和节省内存空间得问题。 （5）比较深度优先和广度优先两种搜索法，广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索算法法要快些。 华北水利水电学院数据结构实验报告 20 10 ～20 11 学年第一学期2008级计算机专业 班级：107学号：200810702姓名：王文波 实验四图的应用 一、实验目的： 1．掌握图的存储结构及其构造方法 2．掌握图的两种遍历算法及其执行过程 二、实验内容： 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。 三、实验要求： 1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。 2．C/ C++完成算法设计和程序设计并上机调试通过。 3．撰写实验报告，提供实验结果和数据。 4．写出算法设计小结和心得。 四、程序源代码： #include { int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2; #define M 20 #include "stdio.h" #include "stdlib.h" #include "malloc.h" typedef struct{/*定义图*/ int V[M]; int R[M][M]; int vexnum; }Graph; void creatgraph(Graph *g,int n){/*创建图*/ int i,j,r1,r2; g->vexnum=n; for(i=1;i<=n;i++)/*顶点用i表示*/{g->V[i]=i;}for(i=1;i<=n;i++)/*初始化R*/ for(j=1;j<=n;j++){g->R[i][j]=0;}printf("Please input R(0,0 END): \n");/*输入R*/ scanf("%d,%d",&r1,&r2); while(r1!=0&&r2!=0){g->R[r1][r2]=1; g->R[r2][r1]=1; scanf("%d,%d",&r1,&r2);}} void printgraph(Graph *g){/*打印图的邻接矩阵*/ int i,j; for(i=1;i<=g->vexnum;i++) { for(j=1;j<=g->vexnum;j++){printf("%2d ",g->R[i][j]);}printf("\n");}} int visited[M];/*全局变量： 访问标志数组*/ void visitvex(Graph *g,int vex){/*访问顶点*/ printf("%d ",g->V[vex]);}int firstadjvex(Graph *g,int vex){/*获取第一个未被访问的邻接节点*/int w,i; for(i=1;i<=g->vexnum;i++){if(g->R[vex][i]==1&&visited[i]==0){w=i; break;}else{w=0;}} return w;}int nextadjvex(Graph *g,int vex,int w){/*获取下一个未被访问的邻接节点*/ int t; t=firstadjvex(g,w); return t;}void DFS(Graph *g,int vex){/*深度递归遍历*/ int w; visited[vex]=1; visitvex(g,vex); for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w)) if(!visited[w]){DFS(g,w);}} void DFSTraverse(Graph *g){/*深度遍历*/ int i; for(i=1;i<=g->vexnum;i++) 猴子摘香蕉问题的宽度优先搜索和最大深度为5的有界深度优先搜索（注意：括号中的斜体字是我做的说明，不是答案的内容） 解：设一个状态由四元组（W, X, Y , Z ）来表示，其中： 1. W 代表猴子的位置，其取值可为a ，b 和c ； 2. X 代表猴子和箱子的位置关系，取值为0和1，其中0表示猴子在箱子下，而1表示猴子在箱子上面； 3. Y 代表箱子的位置，其取值可为a ，b 和c ； 4. Z 代表是否摘得香蕉，取值为0和1，其中0表示未摘得香蕉而1表示已经摘到了香蕉。 则本问题的初始状态为（a ，0，c ，0），而目标状态为（b ，1，b ，1）(注意：目标状态写为 (U,V,H,1 )也可以，因为我们只关心摘到香蕉)。 本问题中涉及的算符有四个，分别为 1. 移动：Goto （U ），其中U 可取a ，b 和c ，其执行条件为X ＝0（即猴子不在箱子上），其效果如下式 (,0,,)goto()(,0,,)W Y Z U U Y Z ，其中，U ＝a ，b ，c 且U W ≠（注意：加U W ≠是为了减少后面状态图中节点到自身的弧；(,0,,)goto()(,0,,)W Y Z U U Y Z 表示在状态(,0,,)W Y Z 上执行Goto （U ）操作，使得原状态变为状态(,0,,)U Y Z ） 2. 推箱子：Pushbox(U)，其中U 可取a ，b 和c ，其执行条件为W ＝Y （猴子和箱子在同一个位置）且X ＝0（猴子不在箱子上），其效果如下式 (,0,,)Pushbox()(,0,,)V V Z U U U Z ，其中U, V ＝a ，b ，c ，且U V ≠（注意：加U V ≠的作用同上U W ≠） 3. 攀爬：Climb ，其执行条件为W=Y （猴子和箱子在同一个位置）且X ＝0（猴子不在箱子上），其效果如下 (,0,,)Climb(,1,,)U U Z U U Z ，其中U ＝a ，b 或c 4. 摘香蕉：Grasp ，其执行条件为W ＝Y ＝b （猴子和箱子都在b 位置）, X=1（猴子在箱子上）且Z ＝0（猴子未摘得香蕉），其效果如下 (,1,,0)Grasp(,1,,1)b b b b 。 设在同一状态下，检查并应用可应用的必要算符的次序如下：goto(a), goto(b), goto(c), pushbox(a), pushbox(b), pushbox(c), climb, grasp. 则宽度优先搜索树如下图所示，其中状态左上角的数字代表该状态被扩展的顺序（是“生孩子”的顺序而不是 “出生”的顺序）： 2007-05-27 晴 //采用非递归深度优先遍历算法，可以将回溯法表示为一个非递归过程 #include }; private: int Bound(int i); void Backtrack(int i); int c; //背包容量 int n; //物品数 int *w; //物品重量数组int *p; //物品价值数组int cw; //当前重量 int cp; //当前价值 int bestp; //当前最优值int *bestx; //当前最优解int *x; //当前解 }; int Knap::Bound(int i) //装满背包 if(i<=n) b+=p/w*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 数据结构课程实验报告 课程名称数据结构班级计算123 实验日期2014年6月1日--3日 姓名学号实验成绩实验名称实验四图的深度和广度优先遍历 实验目的及要求【实验目的】 熟练掌握图的邻接表存储结构及其图的建立方法和深度和广度优先遍历的方法。 【实验要求】 1.图的存储可采用邻接矩阵或邻接表 2.GraphCreate(): 按从键盘的数据建立图 3.GraphDFS()：深度优先遍历图 4.GraphBFS()：广度优先遍历图 5.编写完整程序完成下面的实验内容并上机运行 6.整理并上交实验报告 实验环境硬件平台：普通的PC机 软件平台：Windows 7 操作系统编程环境：VisualC++ 6.0 实验内容1.以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 算法描述及实验步骤算法： 1)定义图的邻接表存储结构 2）实现图的邻接表存储，即建立图的存储结构 3）实现图的深度优先遍历 4）定义队列的顺序存储结构，并实现队列的基本操作如初始化队列、入队、出对、判断队列是否为空等。利用队列实现图的广度优先遍历。伪代码： 1）定义邻接矩阵和队列的存取结构； 2）创建图L： 1.置空图L->num=0； 2.输入顶点数目num； 3.i++,输入结点L->vexs[i]直到L->num; 3）输出图L的各顶点； 4）深度优先遍历图g中能访问的各个顶点 1.输入起点的下标qidian； 2.标志数组初始化mark[v]=0; 3.for(v=qidian;v DFS与BFS的比较 姓名：班级：学号： 一、图的遍历 1.图的遍历的含义 图的遍历是指从图中某结点出发，按某既定方式访问图中各个可访问到的结点，使每个可访问到的结点恰被访问一次。 2.图的遍历方式：深度优先与广度优先 二、DFS与BFS的区别 1.概念 深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问止。 广度优先遍历可定义如下：假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 2. 路径 深度优先就是，从初始点出发，不断向前走，如果碰到死路了，就往回走一步，尝试另一条路，直到发现了目标位置。这种方法，即使成功也不一定找到一条好路，但是需要记住的位置比较少。 广度优先就是，从初始点出发，把所有可能的路径都走一遍，如果里面没有目标位置，则尝试把所有两步能够到的位置都走一遍，看有没有目标位置；如果还不行，则尝试所有三步可以到的位置。这种方法，一定可以找到一条最短路径，但需要记忆的内容实在很多，要量力而行。 3.算法实现 (1) 图的深度优先算法的一般性描述： long DFS(图s，结点v。) { // 从结点v。出发，深度优先遍历图s，返回访问到的结点总数 int nNodes; //寄存访问到的结点数目 访问v。; 一：单选题 1. 人工智能的目的是让机器能够（D），以实现某些脑力劳动的机械化。 A. 具有完全的智能 B. 和人脑一样考虑问题 C. 完全代替人 D. 模拟、延伸和扩展人的智能 2. 下列关于人工智能的叙述不正确的有（C）。 A. 人工智能技术它与其他科学技术相结合极大地提高了应用技术的智能化水平。 B. 人工智能是科学技术发展的趋势。 C. 因为人工智能的系统研究是从上世纪五十年代才开始的，非常新，所以十分重要。 D. 人工智能有力地促进了社会的发展。 3. 自然语言理解是人工智能的重要应用领域，下面列举中的（C）不是它要实现的目标。 A. 理解别人讲的话。 B. 对自然语言表示的信息进行分析概括或编辑。 C. 欣赏音乐。 D. 机器翻译。 4. 下列不是知识表示法的是（A）。 A. 计算机表示法 B. 谓词表示法 C. 框架表示法 D. 产生式规则表示法 5. 关于“与/或”图表示知识的叙述，错误的有（D）。 A. 用“与/或”图表示知识方便使用程序设计语言表达，也便于计算机存储处理。 B. “与/或”图表示知识时一定同时有“与结点”和“或结点”。 C. “与/或”图能方便地表示陈述性知识和过程性知识。 D. 能用“与/或”图表示的知识不适宜用其他方法表示。 6. 一般来讲，下列语言属于人工智能语言的是（D）。 A. VJ B. C# C. Foxpro D. LISP 7. 专家系统是一个复杂的智能软件，它处理的对象是用符号表示的知识，处理的过程是（C）的过程。 A. 思考 B. 回溯 C. 推理 D. 递归 8. 确定性知识是指（A）知识。 A. 可以精确表示的 B. 正确的 C. 在大学中学到的知识 D. 能够解决问题的 9. 下列关于不精确推理过程的叙述错误的是（B）。 A. 不精确推理过程是从不确定的事实出发 B. 不精确推理过程最终能够推出确定的结论 C. 不精确推理过程是运用不确定的知识 D. 不精确推理过程最终推出不确定性的结论 10. 我国学者吴文俊院士在人工智能的（A）领域作出了贡献。 A. 机器证明 B. 模式识别 C. 人工神经网络 D. 智能代理深度优先与广度优先
图的深度优先遍历算法课程设计报告
图的深度广度优先遍历操作代码
人工智能 实验三 汉诺塔的深度有界搜索求解
深度优先与广度优先
深度优先遍历(邻接矩阵)
图的深度优先遍历实验报告
广度优先搜索和深度优先搜索
邻接矩阵的深度优先遍历
人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
深度优先搜索和广度优先搜索的深入讨论
图的深度优先遍历和广度优先遍历
无向图的深度优先和广度优先遍历
猴子摘香蕉问题的宽度优先和有界深度优先算法
采用非递归深度优先遍历算法
图的深度和广度优先遍历
深度优先算法与广度优先算法的比较
人工智能复习题(答案)
相关主题
文本预览