罗马尼亚度假问题

二、具体代码测试类：/*Main类，打印各个算法的成果* author dyl*/classMainintresult;intxiabiao=null;/访问的下标publicstaticvoidmain(Stringargs)Graphgraph=newGraph();System.out.println(-罗马尼亚问题-);System.out.println(1、深度优先搜索);DFS dfs=newDFS();dfs.DF_Search(graph,0,12);System.out.println(2、迭代加深的搜索);IDS ids=newIDS();ids.IDS_Search(graph,0,12,15);/深度设15System.out.println(3、一致代价搜索);UCS ucs=newUCS(graph,0,12);System.out.println(4、A*搜索);AXingaXing=newAXing();aXing.A_Search(graph,graph.H,0,15);/0-15即Arad达到Hirsova/*打印* param g:图* param stack：栈*/publicvoidshow(Graphg,Stackstack)if(stack.size()=0)System.out.println(途径搜索失败);return;result=0;System.out.print(访问的下标： );for(inti=0;i+stack.get(i);System.out.print(n访问过程： );xiabiao=newintstack.size();if(stack.isEmpty()System.out.println(搜索失败);elsefor(inti=0;i+g.cities(Integer)stack.get(i);for(inti=0;istack.size()-1;i+)result+=g.path(Integer)stack.get(i)(Integer)stack.get(i+1);System.out.println(n总长度为：+result+n);g.markInit();/清空访问/*图类* author dyl*/publicclassGraphpublicintpath=newint0,75,10000,118,140,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,75,0,71,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,71,0,10000,151,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,118,10000,10000,0,10000,111,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,140,10000,151,10000,0,10000,80,99,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,111,10000,0,10000,10000,70,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,80,10000,0,10000,10000,10000,146,97,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,99,10000,10000,0,10000,10000,10000,10000,211,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,70,10000,10000,0,75,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,75,0,120,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,146,10000,10000,120,0,138,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,97,10000,10000,10000,138,0,101,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,211,10000,10000,10000,101,0,90,85,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,90,0,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,85,10000,0,98,10000,142,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,98,0,86,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,86,0,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,142,10000,10000,0,92,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,92,0,87,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,87,0;publicintH=newint516,524,530,479,403,394,343,326,391,392,310,160,150,155,100,0;/启发式函数publicStringcities=newStringArad,Zerind,Oradea,Timisoara,Sibiu,Lugoj,Rimnicu Vilcea,Fagaras,Mehadia,Drobeta,Craiova,Pitesti,Bucharest,Giurgiu,Urziceni,Hirsova,Eforie,Vaslui,Isi,Neamt;/都市名publicintmark=newint20;/访问标记publicGraph()/得到数据markInit();/* 访问标志初始化*/publicvoidmarkInit()for(inti=0;i=0&startpath.length)for(intj=0;jpath.length;j+)if(pathstartj0)/有关系returnj;return-1;/*下一种孩子* param start* param w* return 表达图G中顶点i的第j个邻接顶点的下一种邻接顶点* 返回-1，表达背面没有邻接点了*/publicintgetNextVex(intstart,intw)if(start=0&start=0&wpath.length)for(inti=w+1;ipath.length;i+)if(pathstarti0)returni;return-1;publicintgetNumber()returnpath.length;l【深度优先】基本原理：深度优先搜索采用堆栈寻找途径，一方面从Arad结点出发，判断与否为目的结点，若否，寻找与该结点的邻接点，先搜索一条分支上的所有节 点，然后再去搜索和Arad的其他分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表与否为空，若否，则从待扩展结点表中取出一种结点 进行扩展，并将扩展后的结点存进该表，若是，则返回失败。深度优先搜索类：/*深度优先搜索类* author dyl*/publicclassDFSStackstack=newStack();intx;intw;/v0的第一种邻接点/*深度优先搜索-非递归式* param g ：图* param v0：开始节点* param vg：最后节点*/publicvoidDF_Search(Graphg,intv0,intvg)stack.push(v0);/入栈g.markv0=1;/v0被访问while(true)x=(Integer)stack.peek();/查看栈顶元素w=g.getFirstVex(x);while(g.markw=1)/被访问，则寻找下一种邻接点w=g.getNextVex(x,w);if(w=-1)break;while(w=-1)/没有找到下一种邻接点stack.pop();x=(Integer)stack.peek();w=g.getFirstVex(x);while(g.markw=1)w=g.getNextVex(x,w);if(w=-1)break;stack.push(w);g.markw=1;if(w=vg)break;/达到终点newMain().show(g,stack);实验成果：实验分析：根据成果可只知，在有限状态空间下，树搜索不是完备的，图搜索完备；无限状态下不完备。此成果0-1-2-4-6-10-11-12只是其中一条，但不是最优解。分支因子b，深度d。则最坏状况下时间复杂度也高达,空间复杂度 ，内存需求少。l【迭代加深】基本原理：迭代加深搜索是以DFS为基本的，它限制DFS递归的层数。迭代加深搜索的基本环节是：1、设立一种固定的深度depth，一般是depth=1，即只搜索初始状态2、DFS进行搜索，限制层数为depth，如果找到答案，则结束，如果没有找到答案 则继续下一步3、如果DFS途中遇到过更深的层，则+depth，并反复2；如果没有遇到，阐明搜 索已经结束，没有答案/*迭代加深* author dyl*/publicclassIDSStackstack=newStack();/*迭代加深搜索* param g：图* param v0：开始节点* param vg：目的节点* param depthMax：depthMax*/publicvoidIDS_Search(Graphg,intv0,intvg,intdepthMax)for(inti=2;i=depthMax)/重新迭代则重新初始化值stack.pop();newMain().show(g,stack);return1;实验成果：实验分析： 由于迭代加深是从按照深度的递增搜索的，因此说0-1-2-4-7-12这条 途径，只是在深度最低的状况下找到的成果，并不是最优解。是完备的，时间复杂度也 高达,空间复杂度。l【一致代价】基本原理：扩展的是途径消耗g(n)最小的节点n,用优先队列来实现，对解的途径步数不关怀，只关怀途径总代价。虽然找到目的节点也不会结束，而是再检查新途径是不是要比老途径好，的确好，则丢弃老途径。/* 一致代价类*/publicclassUCSpublicUCS(Graphg,intstart,intend)intpre=newint20;/ 保存各个结点的前驱结点intdist=newint20;/ 用于保存目前结点到起始结点的实际途径长度for(inti=0;ipre.length;i+)prei=-1;disti=10000;/ 调用一致搜索算法搜索途径UC_search(g,start,end,dist,pre);/ 打印途径显示函数displayPath(start,end,pre,g);/* param start：开始* param goal：目的* param prev：前驱节点* param g：图*/publicvoiddisplayPath(intstart,intgoal,intprev,Graphg)Stackstack=newStack();stack.push(goal);while(prevgoal!=start)stack.push(prevgoal);goal=prevgoal;stack.push(start);System.out.print(访问的下标: );for(inti=stack.size()-1;i=0;i-)System.out.print(-+stack.get(i);System.out.print(n访问过程: );for(inti=stack.size()-1;i=0;i-)System.out.print(-+g.citiesstack.get(i);System.out.print(n总长度为： );intresult=0;for(inti=0;istack.size()-1;i+)result+=g.pathstack.get(i)stack.get(i+1);System.out.print(result);System.out.println(n);g.markInit();/* param g：图* param start：开始* param goal：目的* param prev：前驱节点*/publicvoidUC_search(Graphg,intstart,intgoal,intdist,intpre)Listlist=newArrayList();list.add(start);while(!list.isEmpty()moveMinToTop(list,dist);/ 将dist数组中最小值所相应的结点，移至list队首intcurrent=list.remove(0);/ 将list队首的结点出队，并展开g.markcurrent=1;if(current=goal)return;for(intj=0;jg.pathcurrent.length;j+)if(g.pathcurrentj10000&g.markj=0)if(!isInList(j,list)/ 结点j不在队列里list.add(j);prej=current;distj=distcurrent+g.pathcurrentj;elseif(distcurrent+g.pathcurrentj)distj)prej=current;distj=distcurrent+g.pathcurrentj;if(list.isEmpty()System.out.println(搜索不成功！);/* 检查结点a，与否在队列list里*/publicbooleanisInList(inta,Listlist)for(inti=0;ilist.size();i+)if(list.get(i)=a)returntrue;returnfalse;/* 将dist数组中的最小值所相应的结点，从list队列中移至队列头*/publicvoidmoveMinToTop(Listlist,intdist)intindex=0;intmin=distindex;for(inti=0;ilist.size();i+)inta=list.get(i);if(dista0;i-)list.set(i,list.get(i-1);list.set(0,temp);实验成果：实验分析：从成果0-4-6-11-12可以看出。是最优解，她的复杂度不能简朴地使用b、d刻画。得使用C*表达最优解的耗散值。时间复杂度，空间复杂度。l【A*搜索】基本原理：公式表达为：f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到目的点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目的节点最佳途径的估计代价。保证找到最短途径（最优解的）条件，核心在于估价函数f(n)的选用：一方面将起始结点S放入OPEN表，CLOSE表置空，算法开始时： 1、如果OPEN表不为空，从表头取一种结点n，如果为空算法失败。 2、n是目的解吗？是，找到一种解（继续寻找，或终结算法）。 3、将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同步计算每一种后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，反复算法，回到1。importjava.util.Stack;/* A*搜索类* author dyl*/publicclassAXingintMaxWeight=10000;/表达无穷大Stackstack=newStack();/*A*搜索* param g：图* param H：启发式函数值* param v0：初始值* param end：目的值*/publicvoidA_Search(Graphg,intH,intv0,intend)booleanflag=true;intx;/表达栈顶元素intvex;/寻找目的节点intMinF,MinVex=v0;/记录最小的f(n)和相应的节点intGHF=newintg.path.length3;/分别用于存储g(n),h(n),f(n)for(inti=0;ig.path.length;i+)GHFi0=0;GHFi2=MaxWeight;/对f(n)初始化,1000表达无穷大stack.push(v0);/v0入栈GHFv00=0;/g(n)GHFv01=Hv0;/h(n)GHFv02=GHFv00+GHFv01;/f(n)g.markv0=1;while(flag)MinF=MaxWeight;x=(Integer)stack.peek();/解决第一种子节点vex=g.getFirstVex(x);if(vex=end)/找到目的节点stack.push(vex);g.markvex=1;break;if(vex!=-1)/子节点能找到，继续if(g.markvex=0)/没被访问GHFvex0=GHFx0+g.pathxvex;/节点vex的g(n)GHFvex1=Hvex;/节点vex的h(n)GHFvex2=GHFvex0+GHFvex1;if(GHFvex2MinF)MinF=GHFvex2;MinVex=vex;/解决剩余的邻接点（宽度遍历）while(vex!=-1)vex=g.getNextVex(x,vex);if(vex!=-1&g.markvex=0)/有邻节点GHFvex0=GHFx0+g.pathxvex;/节点vex的g(n)GHFvex1=Hvex;/节点vex的h(n)GHFvex2=GHFvex0+GHFvex1;if(GHFvex2MinF)MinF=GHFvex2;MinVex=vex;if(vex=-1)/没有邻接点了，此时拟定最小消耗节点，并压栈stack.push(MinVex);g.markMinVex=1;break;if(vex=end)stack.push(vex);/压栈目的节点g.markvex=1;flag=false;break;else/没有子节点或者子节点被访问了，循环出栈while(vex=-1)stack.pop();newMain().show(g,stack);实验成果：实验分析：A*搜索估价值h(n)实际值,搜索的点数少，搜索范畴小，效率高，但不能保证得到最优解。三、实验成果：