《罗马尼亚人工智能实验报告(共8页).doc》由会员分享，可在线阅读，更多相关《罗马尼亚人工智能实验报告(共8页).doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 4 易雪媛 智能1201 罗马尼亚问题一、问题描述（1）罗马尼亚问题：Find Bucharest starting at Arad分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，列表给出结果。（2） 附（罗马尼亚地图）（3）（3）各结点启发值：二、实现算法1.深度优先 1.1算法思想： 深度优先搜索是一种每次都要达到被搜索结构的叶结点的搜索方法 ，直到不能再深入为止，然后返回到另一个结点，继续对该结点进行深搜。当有目标结点出现时，返回目标结点，搜索结束；否则，若
2、待扩展结点表已空，且未找到目标结点，则返回失败，停止搜索。同样，深度优先搜索从Arad结点出发，判断是否为目标结点，若否，探寻与该结点相连的结点，算法首先搜索一条分支上的所有顶点，然后再去搜索和Arad的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。 1.2算法核心代码：void DFS(int start,char name,int path20,bool visited) /*深度遍历*/visitedstart=true;coutnamestart-;for(int
3、 i = 0;i20 & start!=1;i+)if(pathstarti!=0 & pathstarti!=1000 & visitedi=false )/寻找与当前结点相连的未访问的结点DFS(i,name,path,visited); 1.3运行结果： 1.4算法分析：DFS不是完备的（除非查找空间是有限的），同时，它也不能找到最优解。深度优先的时间复杂度：；空间复杂度：（b为分支因子，m为深度，仅有一枝需要存储）。2.迭代加深的深度搜索算法 2.1算法思想： 迭代加深搜索是以DFS为基础的，它限制DFS递归的层数（即栈的容量，即所说的“深度”）。迭代加深搜索的基本步骤是：1、设置一个
4、固定的深度deep，通常是depth = 1，即只搜索初始状态2、DFS进行搜索，限制层数为deep，如果找到答案，则结束，如果没有找到答案则继续下一步3、如果DFS途中遇到过更深的层，则+deep，并重复2；如果没有遇到，说明搜索已经结束，没有答案。 2.2算法核心代码：bool DDFS(int start,char name,int path20,bool visited,int deep) /*深度遍历*/if(deep = 0) coutn;return false;else deep = deep-1;/深度减一visitedstart=true;coutnamestart;for
5、(int i = 0;i20 & start!=1;i+)if(pathstarti!=0 & pathstarti!=1000 & visitedi=false )/寻找与当前结点相连的未访问的结点DDFS(i,name,path,visited,deep);/*main函数中的调用*/cout路径为第一行endl;for(int deep = 1;deep8;deep+)for(int m = 0;m20;m+)visitedm=false;cout第deependl;DDFS(0,name,path,visited,deep); 2.3运行结果： 2.4算法分析：DDFS同样不是完备的（
6、除非查找空间是有限的），同时，它也不能找到最优解。迭代加深深度优先的时间复杂度：O(bd)；空间复杂度：O(bd)（b为分支因子，d为深度界限，仅有一枝需要存储）。3.一致代价搜索算法 3.1算法思想： 当所有路径耗散相等的时候，广度优先搜索是最优的，因为它总是先扩展深度最浅的结点。更一般地，如果路径耗散是结点深度的非递减函数，广度优先搜索也是最优的。而代价一致（UniformCost）搜索扩展的是路径消耗最低的结点。而如果搜有单独耗散都相等的话，这种算法就和广度优先搜索算法是一样的。代价一致搜索对一条路径的步数并不关心，而关心所经历步骤总的消耗。因此，在扩展到一个具有能返回同一状态的零耗散行
7、动的结点时就会陷入无限循环。在实现上，广度优先搜索只需要使用先进先出队列，而代价一致搜索则需要使用优先级队列。 3.2算法核心代码：public void UC_search(int start, int goal, int a, int dist, boolean isVisited, int pre)List list = new LinkedList();list.add(start);while(!list.isEmpty()moveMinToTop(list, dist);int temp = list.remove(0);isVisitedtemp = true;if(temp =
8、 goal)System.out.println(搜索成功了！);return; for(int j = 0; j atemp.length; j+) if(atempj 10000 & !isVisitedj) if(isInList(j, list) = -1) / 结点j不在队列里 list.add(j); prej = temp; distj = disttemp + atempj; if(disttemp + atempj) distj)prej = temp;distj = disttemp + atempj; if(list.isEmpty() System.out.printl
9、n(搜索不成功！); 3.3运行结果： 3.4算法分析：UCS同样不是完备的（除非查找空间是有限的），同时，它也不能找到最优解。时间复杂度：O(bd)，空间复杂度：O(bd)。4.A*搜索算法 4.1算法思想： A*算法用公式表示为： f(n)=g(n)+h(n), 其中f(n) 是从初始点经由结点n到目标点的估价函数；g(n) 是在状态空间中从初始节点到n节点的实际代价， h(n)是从n到目标节点最佳路径的估计代价。 A*能找到最优解的条件，关键在于估价函数h(n)的选取；若估价值实际值, 则能保证得到最优解。 4.2算法核心代码：public void AStart_search(int
10、start, int goal, int c, boolean isVisited, int directLen, int cost, int dist, int prev)List list = new ArrayList();list.add(start);while(!list.isEmpty()moveMinToTop(list, cost);int current = list.remove(0);isVisitedcurrent = true;if(current = goal)System.out.println(搜索成功);break;elsefor(int i = 0; i
11、c0.length; i+)if(ccurrenti 10000 & !isVisitedi)if(isInList(i, list) = -1) / 结点i不在队列里list.add(i);previ = current;disti = distcurrent + ccurrenti;/* * 启发式函数为： * 起始结点到中间结点的实际距离 + * 中间结点到Bucharest的直线距离 + * 目标结点到Bucharest的直线距离 */costi = disti + directLeni + directLengoal; if(distcurrent + ccurrenti disti)disti = distcurrent + ccurrenti; / 刷新结点的实际距离previ = current;/* * 启发式函数为： * 起始结点到中间结点的实际距离 + * 中间结点到Bucharest的直线距离 + * 目标结点到Bucharest的直线距离 */costi = disti + directLeni + directLengoal; 4.3运行结果： 4.4算法分析：A*算法是完备的，且能够找到最优解；其时间复杂度：扩展节点的数目；空间复杂度：所有生成的结点。专心-专注-专业