罗马尼亚度假问题

1、二、详细代码测试类：/*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(g

2、raph,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;resu

3、lt=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.

4、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,10

5、000,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,100

6、00,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,100

7、00,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,1000

8、0,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,100

9、00,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,1000

10、0,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,

11、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;/启发式函数publicStringciti

12、es=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

13、=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

14、;l【深度优先】基本原理：深度优先搜索采用堆栈寻找路径，首先从Arad结点出发，判断是否为目标结点，若否，寻找与该结点的邻接点，先搜索一条分支上的所有节 点，然后再去搜索和Arad的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点 进行扩展，并将扩展后的结点存进该表，若是，则返回失败。深度优先搜索类：/*深度优先搜索类* author dyl*/publicclassDFSStackstack=newStack();intx;intw;/v0的第一个邻接点/*深度优先搜索-非递归式* param g ：图* param v0：

15、开始节点* 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);whi

16、le(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、设置一个固定的

17、深度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,int

18、depthMax)for(inti=2;i=depthMax)/重新迭代则重新初始化值stack.pop();newMain().show(g,stack);return1;实验结果：实验分析： 因为迭代加深是从按照深度的递增搜索的，所以说0-1-2-4-7-12这条 路径，只是在深度最低的情况下找到的结果，并不是最优解。是完备的，时间复杂度也 高达,空间复杂度。l【一致代价】基本原理：扩展的是路径消耗g(n)最小的节点n,用优先队列来实现，对解的路径步数不关心，只关心路径总代价。即使找到目标节点也不会结束，而是再检查新路径是不是要比老路径好，确实好，则丢弃老路径。/* 一致代价类*/publ

19、icclassUCSpublicUCS(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

20、：图*/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=stac

21、k.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：前驱节点*/publicvoidU

22、C_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.pathcurrentj100

23、00&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;i

24、list.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可以看出。是最优解，他的复杂度不能

25、简单地使用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可以直接关联的结点

26、（子结点），如果不在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;GHFi