罗马尼亚人工智能实验报告

人工智能 4 易雪媛 智能1201 罗马尼亚问题一、问题描述（1）罗马尼亚问题：Find Bucharest starting at Arad分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，列表给出结果。（2） 附（罗马尼亚地图）（3）（3）各结点启发值：二、实现算法1.深度优先 1.1算法思想： 深度优先搜索是一种每次都要达到被搜索结构的叶结点的搜索方法 ，直到不能再深入为止，然后返回到另一个结点，继续对该结点进行深搜。当有目标结点出现时，返回目标结点，搜索结束；否则，若待扩展结点表已空，且未找到目标结点，则返回失败，停止搜索。同样，深度优先搜索从Arad结点出发，判断是否为目标结点，若否，探寻与该结点相连的结点，算法首先搜索一条分支上的所有顶点，然后再去搜索和Arad的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。 1.2算法核心代码：void DFS(int start,char name,int path20,bool visited) /*深度遍历*/visitedstart=true;coutnamestart-;for(int 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、设置一个固定的深度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(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同样不是完备的（除非查找空间是有限的），同时，它也不能找到最优解。迭代加深深度优先的时间复杂度：O(bd)；空间复杂度：O(bd)（b为分支因子，d为深度界限，仅有一枝需要存储）。3.一致代价搜索算法 3.1算法思想： 当所有路径耗散相等的时候，广度优先搜索是最优的，因为它总是先扩展深度最浅的结点。更一般地，如果路径耗散是结点深度的非递减函数，广度优先搜索也是最优的。而代价一致（UniformCost）搜索扩展的是路径消耗最低的结点。而如果搜有单独耗散都相等的话，这种算法就和广度优先搜索算法是一样的。代价一致搜索对一条路径的步数并不关心，而关心所经历步骤总的消耗。因此，在扩展到一个具有能返回同一状态的零耗散行动的结点时就会陷入无限循环。在实现上，广度优先搜索只需要使用先进先出队列，而代价一致搜索则需要使用优先级队列。 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 = 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.println(搜索不成功！); 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 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 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;/* * 启发式函数为：