罗马尼亚度假问题

1、二、详细代码测试类：/*Main类，打印各个算法的结果* author dyl*/classMainint result;int xiabiao=null;/访问的下标publicstaticvoid main(String args)Graph graph=newGraph();System.out.println("-罗马尼亚问题-");System.out.println("1、深度优先搜索");DFS dfs=new DFS();dfs.DF_Search(graph,0,12);Sys

2、tem.out.println("2、迭代加深的搜索");IDS ids=new IDS();ids.IDS_Search(graph,0,12,15);/深度设15System.out.println("3、一致代价搜索");UCS ucs=new UCS(graph,0,12);System.out.println("4、A*搜索");AXing aXing=newAXing();aXing.A_Search(graph, graph.H,0,15);/0-15即Arad到达Hirsova/

3、*打印* param g:图* param stack：栈*/publicvoid show(Graph g,Stack stack)if(stack.size()=0)System.out.println("路径搜索失败");return;result=0;System.out.print("访问的下标： ");for(int i =0; i < stack.size(); i+)System.out.print("->"+stac

4、k.get(i);System.out.print("n访问过程： ");xiabiao=newintstack.size();if(stack.isEmpty()System.out.println("搜索失败");elsefor(int i =0; i < stack.size(); i+)System.out.print("->"+g.cities(Integer) stack.get(i);for(int i =0; 

5、;i < stack.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*/publicclassGraphpublicint path=newint0,75,10000,118,140,10000,10000,10000,10000,10000,

6、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,1

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

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

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

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

11、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

12、,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,

13、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;/启发式函数publicString cities=newString"Arad","Zerind","Oradea","Timisoara","Sibiu","Lugoj","Rimnicu V

14、ilcea","Fagaras","Mehadia","Drobeta","Craiova","Pitesti","Bucharest","Giurgiu","Urziceni","Hirsova","Eforie","Vaslui","Isi","Neamt"/城市名publicintmark=newint20;/访问标记pu

15、blicGraph()/得到数据markInit(); /* 访问标志初始化*/publicvoid markInit()for(int i =0; i < mark.length; i+)marki=0;/*第一个孩子* param g* param start* return -1表示一个孩子都没有*/publicint getFirstVex(int start)if(start>=0&&start<path.length)for(int j&#

16、160;=0; j < path.length; j+)if(pathstartj<10000&&pathstartj>0)/有关系return j;return-1; /*下一个孩子* param start* param w* return 表示图G中顶点i的第j个邻接顶点的下一个邻接顶点* 返回-1，表示后面没有邻接点了*/publicint getNextVex(int start,int w)if(start>=0&&start<pa

17、th.length&&w>=0&&w<path.length)for(int i = w+1; i < path.length; i+)if(pathstarti<10000&&pathstarti>0)return i;return-1;publicint getNumber()return path.length; l 【深度优先】基本原理：深度优先搜索采用堆栈寻找路径，首先从Arad结点出发，

18、判断是否为目标结点，若否，寻找与该结点的邻接点，先搜索一条分支上的所有节 点，然后再去搜索和Arad的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点 进行扩展，并将扩展后的结点存进该表，若是，则返回失败。深度优先搜索类：/*深度优先搜索类* author dyl*/publicclass DFS Stack stack=newStack<Integer>();int x;int w;/v0的第一个邻接点/*深度优先搜索-非递归式* param g ：图* para

19、m v0：开始节点* param vg：最终节点*/publicvoid DF_Search(Graph g,int v0,int vg)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=(In

20、teger) 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，深

21、度d。则最坏情况下时间复杂度也高达,空间复杂度  ，内存需求少。 l 【迭代加深】基本原理：迭代加深搜索是以DFS为基础的，它限制DFS递归的层数。迭代加深搜索的基本步骤是：1、设置一个固定的深度depth，通常是depth = 1，即只搜索初始状态2、DFS进行搜索，限制层数为depth，如果找到答案，则结束，如果没有找到答案 则继续下一步3、如果DFS途中遇到过更深的层，则+depth，并重复2；如果没有遇到，说明搜 索已经结束，没有答案/*迭代加深* author dyl*/publicclass IDS Stack&

22、#160;stack=newStack<Integer>();/*迭代加深搜索* param g：图* param v0：开始节点* param vg：目的节点* param depthMax：depthMax*/publicvoid IDS_Search(Graph g,int v0,int vg,int depthMax)for(int i =2; i <=depthMax; i+)/迭代depthMax次if(dfsearch(g, v0, vg,i)

23、=1)break;/*深度搜索* param g：图* param v0：开始节点* param vg：目的节点* param depthMax：depthMax* return*/publicint dfsearch(Graph g,int v0,int vg,int depthMax)int x;int w;/v0的第一个邻接点stack.push(v0);/入栈g.markv0=1;/v0被访问while(true)x=(Integer) stack.peek();/查看栈顶元素w=g.getFirstVex

24、(x);while(g.markw=1)/被访问，则寻找下一个邻接点w=g.getNextVex(x, w);if(w=-1)break;while(w=-1)/没有找到下一个邻接点stack.pop();if(stack.size()=0)/清空了栈里的元素g.markInit();/访问初始化return0;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)b

25、reak;/检查是否达到终点if(stack.size()>=depthMax)/重新迭代则重新初始化值stack.pop();newMain().show(g, stack);return1;实验结果： 实验分析：         因为迭代加深是从按照深度的递增搜索的，所以说0-1-2-4-7-12这条 路径，只是在深度最低的情况下找到的结果，并不是最优解。是完备的，时间复杂度也 高达,空间复杂度。 l 【一致代价】基本原理：扩展的是路径消耗g(n)最小的节点n,用优先队列来实现，对解的路径步数不

26、关心，只关心路径总代价。即使找到目标节点也不会结束，而是再检查新路径是不是要比老路径好，确实好，则丢弃老路径。 /* 一致代价类*/publicclass UCS  public UCS(Graph g,int start,int end)int pre =newint20;/ 保存各个结点的前驱结点int dist =newint20;/ 用于保存当前结点到起始结点的实际路径长度for(int i =0; i < pr

27、e.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：图*/publicvoid displayPath(int start,int goal,int prev,Graph g)S

28、tack<Integer> stack =newStack<Integer>();stack.push(goal);while(prevgoal!= start)stack.push(prevgoal);goal = prevgoal;stack.push(start);System.out.print("访问的下标: ");for(int i = stack.size()-1; i >=0; i-)System.out.print(&

29、quot;->"+stack.get(i);System.out.print("n访问过程: ");for(int i = stack.size()-1; i >=0; i-)System.out.print("->"+ g.citiesstack.get(i);System.out.print("n总长度为： ");int result=0;for(int i =0; i <

30、60;stack.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：前驱节点*/publicvoid UC_search(Graph g,int start,int goal,int dist,int pre)Lis

31、t<Integer> list =newArrayList<Integer>();list.add(start);while(!list.isEmpty()moveMinToTop(list, dist);/ 将dist数组中最小值所对应的结点，移至list队首int current = list.remove(0);/ 将list队首的结点出队，并展开g.markcurrent=1;if(current = goal)return; for(int j =0;

32、 j < g.pathcurrent.length; j+)if(g.pathcurrentj<10000&& 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=&#

33、160;distcurrent+ g.pathcurrentj;if(list.isEmpty()System.out.println("搜索不成功！");/* 检查结点a，是否在队列list里*/publicboolean isInList(int a,List<Integer> list)for(int i =0; i < list.size(); i+)if(list.get(i)= a)returntrue;returnfalse;/* 将

34、dist数组中的最小值所对应的结点，从list队列中移至队列头*/publicvoid moveMinToTop(List<Integer> list,int dist)int index =0;int min = distindex;for(int i =0; i < list.size(); i+)int a = list.get(i);if(dista< min)index =

35、 i;min = dista;int temp = list.get(index);for(int i = index; i >0; i-)list.set(i, list.get(i -1);list.set(0, temp);实验结果： 实验分析：从结果0-4-6-11-12可以看出。是最优解，他的复杂度不能简单地使用b、d刻画。得使用C*表示最优解的耗散值。时间复杂度，空间复杂度。 l 【A*搜索】基本原

36、理：公式表示为： 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是目标解吗？是，找到一个解（继续寻找，或终止算法）。  &

37、#160;  3、将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1。import java.util.Stack; /* A*搜索类* author dyl*/publicclassAXingintMaxWeight=10000;/表示无穷大Stack stack=newStack<Integer>();/*A*搜索* param g：图* param H：启发式函数值* param v0：初始值* param end：目标值*/publicvoid A_Search(Graph g,int H,int v0,int end)boolean flag=true;int x;/表示栈顶元素int vex;/寻找目