罗马尼亚度假问题.docx

《罗马尼亚度假问题.docx》由会员分享，可在线阅读，更多相关《罗马尼亚度假问题.docx（13页珍藏版）》请在三一文库上搜索。

1、二、详细代码测试类：/*Main类，打印各个算法的结果* author dyl */classMainint result;int xiabiaoL =nu 11; /访问 的 卜标 publicstaticvoid main1String., args 1 Graph graph=newGraph i);System. out. printin1罗马尼亚问题“);System. out. printin深度优先搜索”);DFS dfs=new DFS ();dfs. DF_Search1 graph, 0, 12，;System. out. printin(2、迭代加深的搜索”);IDS i

2、ds二new IDS();ids. IDS_Search1 graph, 0, 12, 15);深度设 15System. out. printin (3、一致代价搜索);UCS ucs=new UCS1 graph, 0, ;System. out. printin(4、A*搜索);AXing aXing=newAXing1);aXing. A_Search (graph, graph. H, 0. 15 , : /0-15 即 Arad 至lj达 Hirsova )/*打印* param g:图* param stack：栈*/publicvoid show Graph g,Stack s

3、tack, if1 stack. size 1 )=0，System, out. printin路径搜索失败);return;result=0:System. out. print C访问的下标： )；for int i =0; i stack. size1) ; i+) System. out. print1 一一，z+stack. get1 i 1 ; System. out. print1访I、可过Ef；：;xiabiao=newint .stack. size 1)_ ;if stack. isEmpty 1 1System, out. print In搜索失败);elsefor in

4、t i =0; i stack. size1) ; i+) System, out. print1一一+g. cities - Integer1 stack. get i 1 _);)for int i =0; i stack, size )-1; i+) result+g. path _1 Integer1 stack. get i. _1 Integer1 stack. get1i+1 J;System. out. println,，zn ，总长度为:;g. marklnit1); /清空访问)/*图类* author dyl*/publicclassGraphpublicint path

5、 IJ 二二 newint 二二0, 75, 10000, 118, 140, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 100 00),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, 1

6、0000, 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, 1000 0,10000,10000,10000, 10000, 10000, 10000, 10000,140, 10000, 151, 10000, 0, 10000, 80, 99, 10000, 10000, 10000, 10000,

7、 10000, 1000 0,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, 10 000,10000,10000. 10000, 10000, 10

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

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

10、101, 1 0000,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,10 000, 90, 0, 10000, 10000, 10000, 10000, 1000

11、0, 10000),(10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10 000, 85, 10000, 0, 98, 10000, 142, 10000, 10000),10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,10000,10000,10 000, 10000, 10000. 98, 0, 86, 10000, 10000, 10000,10000, 10000, 10000, 10000, 10000

12、, 10000, 10000, 10000, 10000,10000,10000,10 000, 10000, 10000. 10000, 86, 0, 10000, 10000, 10000),10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,10000,10000,10 000, 10000, 10000, 142, 10000, 10000, 0, 92, 10000),10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,1000

13、0,10 000, 10000, 10000, 10000, 10000, 10000, 92, 0, 87),10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,10000,10000,10 000, 10000, 10000, 10000, 10000, 10000, 10000, 87, 0);publicintH=newint (516, 524, 530, 479, 403, 394, 343, 326, 391, 392, 310, 160 ,150,155,100, 0); 1 式函数 publicStrin

14、gJ cities=newString JArad, Zerind, Oradea, Timisoar a , Sibiu , Lugoj , “RimnicuVilcea, Fagaras, Mehadia, Drobeta, Craiova, Pitesti, Bucharest” ,Giurgiu , Urzicem , Hirsova , “Eforie, Vaslui, Isi, Neamt ; .7城市 X publicint _mark=newint 20;/ /访问标记 pub 1 icGraph () (得到数据 marklnit1);)/*访问标志初始化*/publicvo

15、id marklnit11for int i =0; i mark. length; i+) marki0:) ) /*第一个孩子 * param g* param start* return T表示一个孩子都没有*/publicint getFirstVex int start1 if * start =0&start path. length1 for int j =0; j path. length; j+) if =O&wpath, length1 for int i = w+1; i path. length; i+) if1 path startl il 10000&pathsta

16、rtli0) return i;)return-1;publicint getNumber11 return path, length; ) )I【深度优先】基本原理：深度优先搜索采用堆栈寻找路径，首先从Arad结点出发，判断是否为目标结点, 若否，寻找与该结点的邻接点，先搜索一条分支上的所有节点，然后再去搜索和Arad的其 它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若 否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则 返回失败。深度优先搜索类：/*深度优先搜索类* author dyl */publicclass DFSSta

17、ck stackz:newStack (); int x;int w ： vO的第一个邻接点 /*深度优先搜索一非递归式 * param g ：图* param vO：开始节点* param vg：最终节点*/publicvoid DF_Search1 Graph g, int vO, int vgstack, push (vO); 入栈g. mark!vO=l;. vO 被访问while truex= (Integer) stack. peek (); 查看栈顶三素w=g. getFirstVex1 x1 ;while (g. markw=l) 被访问，则寻找下一个邻接点w=g. getNe

18、xtVex1x, w ;if(w=-l) break;)while(w=-l) 没有找到下一个邻接点stack. pop);x=1 Integer ：1 stack. peek 0 ;w=g. getFirstVex * x1 ;while g. mark_w_lw=g. getNextVex1 x, w1 ;if(w=-l) break;)stack. push1w);g. mark _w_ =1;if(w=vg)break;到达终点)newMain 0. show g, stack);实验结果：七次枷皿 0MMx艮1“破a 0河收IS卷岫terminatedMain (I) IJm App

19、iicaton EiVjdkArdi(2015-4-14弱尼亚丽1、承直优先搜索访同的 F恒： -0- -1-2-4-6-10-11- -12访问过程:-oArad-oZeriftd-Oradea-oSibiu-oRimnicu ViIcea- -Craiova - Pitesti- Bucharest 息长度加762nnni实验分析：根据结果可只知，在有限状态空间下，树搜索不是完备的，图搜索完备；无限状态下不完备。 此结果0-1-2-4-只是其中一条，但不是最优解。分支因子b,深度d0则最坏情况下时间复杂度也高达，空间复杂度，存需求少。I【迭代加深】基本原理：迭代加深搜索是以DFS为基础的，

20、它限制DFS递归的层数。迭代加深搜索的基本步骤是：1、设置一个固定的深度depth,通常是depth = 1,即只搜索初始状态2、DFS进行搜索，限制层数为depth,如果找到答案，则结束，如果没有找到答案则继续 下一步3、如果DFS途中遇到过更深的层，则+depth,并重复2；如果没有遇到，说明搜索已 经结束，没有答案/*迭代加深* author dyl* /publicclass IDSStack stack=newStack Integer();/*迭代加深搜索* param g：图* param vO：开始节点* param vg：目的节点* param depthMax： depth

21、Max*/publicvoid IDS_Search1 Graph g, int vO, int vg, int depthMaxfor int i =2: i 二depthMax; i+) ,7迭代 depthMax 次if1 dfsearch1 g, vO, vg, i =1 break;)/*深度搜索* param g：图* param vO：开始节点* param vg：目的节点* param depthMax： depthMax* return*/publicint dfsearch1 Graph g, int vO, int vg, int depthMax1 int x;int

22、w： vO的第一个邻接点stack. push1 vO1 ;/入栈g. mark vO=l; / vO 被访问while truex= (Integer) stack, peek () ; /查看栈顶元素w=g. getFirstVex1 x1 ;while(g. mark二二 1) 被访问，则:，我下一个w=g. getNextVex1x, w ;if(w二二一1) break;)while(w=-l) /没有找到下一个邻接点stack, pop ();if (stack. size ()=0) 清空了栈里的元素g. marklnit; /7访问初始化returnO:)x=1 Integer

23、 stack. peek1);w=g.getFirstVex1x1;while g. mark_w_ 1w=g. getNextVex1x, w ;if(w二二一1) break;)stack, push(w);g. mark_w_=l;if,w=vg(break;/检查是否达到终点if (stack. size。=depthMax) 重新迭代则重新初始化值 stack, pop1);)newMain1). show g, stack1 ;returnl;实验结果：2、迭代加深的搜索访问过程：-Arad-Zerind-Ora(iea-$ibiu-Fagaras-Bucharest总长度为:60

24、7实验分析：因为迭代加深是从按照深度的递增搜索的，所以说0-1-2-4-7-12这条路 径，只是在深度最低的情况下找到的结果，并不是最优解。是完备的，时间复杂度也高达, 空间复杂度。I【一致代价】基本原理：扩展的是路径消耗g(n)最小的节点n,用优先队列来实现，对解的路径步数不关心，只关心 路径总代价。即使找到目标节点也不会结束，而是再检查新路径是不是要比老路径好，确实 好，则丢弃老路径。/* 一致代价类publicclass UCS public UCS1 Graph g, int start, int end,int pre =newint 20; 保存各个结点的前驱结点int： dist

25、 Fewint20l;用于保存当前结点到起始结点的却小路仆K度for int i =0; i pre. length; i+) pre i=-l; distLiJ=10000; /调用一致搜索算法搜索路径UC_search1 g, start, end, dist, pre 1 ;/打印路径显示函数 displayPath1 start, end, pre, g ); /* param start：开始* param goal：目的* param prev：前驱节点* param g：图*/prev, Graph g)publicvoid displayPath1int start, int

26、goal, int ,J (Stack Integer stack =newStack(); stack. push1goal1;while prev.goalJ!= start1 (stack, push*prevgoal.);goal = prev _goal_ ;)stack, push(start);System. out. print1”访问的下标：”)； for int i = stack. size1)-1; i =0; i) System, out. print一一+stack. get1i ;)System, out. print1 z，n 访问过程：”)； for int

27、i = stack. size1; i =0; i) System, out. print,一一+ g.cities .stack, get i)1); System, out. print1 n 总长度为:);int result=0;for int i =0; i stack. size1; i+) result+=g. path stack.get1i l stack. get1i+1 _; )System. out. print1 result);System, out. printin，zn);g. marklnit1); /* param g：图* param start：开始*

28、param goal：目的* param prev：前.驱节点 */publicvoid UC_search1 Graph g, int start, int goal, intJ dist, intJ pre1(List Integer list =newArrayList Integer();list. add1 start：1 ;while 1!list. isEmpty111 (moveMinToTop (list, dist) ;/将dis-I中最小值所对应的结点，移至list队首int current=list. remove(O);将list队首的结点出队，并展开 g. mark

29、.current.=1;if1 current = goal (return;for int j =0; j g. path.current. length; j+) if1 g. pathlcurrentl Ijl 10000& g. markjI=0 (if (! isInList1 j, list) / 结点 j 不在队列里. (list. add1j * ;pre _current;dist _j二= dist current+ g. path .current.j_ ;elseif 1dist .current.+ g. pathcurrent) dist J) ( pre _j_=

30、 current：dist _j_二 dist current.+ g. path .current_ _j_ ; if list. isEmpty111 (System. out. printin ”搜索不成功！ );) /* *检查结点a,是否在队列list里 */publicboolean isInList int a,List Integer list?(for int i =0； i list.size1); i+)(if list, get i)= a1returntrue;) returnfalse; /*将dist数组中的最小值所对应的结点，从list队列中移至队列头 */pu

31、blicvoid moveMinToTop1 List Integer list, int dist1 ( int index =0;int min = dist .index.;for int i =0; i list, size1); i+) int a 二 list.get i1;if1distla min1(index 二 i;min = dist a;) int temp = list.get index1; for int i = index; i 0; i一) (list, set 1 i, list, get1 i -11 ：; list, set10, temp 1;)实验结

32、果：3、一现代价授案访问的下标:-4-6-11-12访何过程: -Arad-Sibiu-Rimnicu Vilcea-Pitesti-8uchares.t 息长度为：41ft，】皿闾HETl实验分析：从结果0-4-6-11-12可以看出。是最优解，他的复杂度不能简单地使用b、d刻画。 得使用C*表示最优解的耗散值。时间复杂度，空间复杂度。I【A*搜索】基本原理：公式表示为：f(n)=g(n)+h(n)z其中f(n)是从初始点经由自点n到目标点的估价函数，g(n)是在状态空间中从初始行点到n行点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件，关键在于估价

33、函数f(n)的选取：首先将起始结点S放入OPEN表，CLOSE表置空，算法开始时：1、如果OPEN表不为空，从表头取一个结点n,如果为空算法失败。2、n是目标解吗？是，找到一个解(继续寻找，或终止算法)。3、将n的所有后继结点展开，就是从n可以直接关联的结点(子结点)，如果不在CLOSE 表中，就将它们放入OPEN表，并把S放入CLOSE表，同时冲算每一个后继结点的估价值 f(n),将OPEN表按f(x)排序，最小的放在表头，重复算法，回到1。import java.util.Stack;/* A*搜索类* author dylpublicclassAXingintMaxWe i ght= 1

34、0000 ： / 左东无穷大Stack stack=newStack ();/*A*搜索* param g：图* param H： 启发式函数值* param vO：初始值* param end：目标值*/publicvoid A_Search1 Graph g, int H_J, int vO, int end boolean flag=true;int x; 表示栈顶元素int vex; 寻找I标节点intMinF, MinVex=vO; . 7记录最小的f (n)和对应的节点int GHF=newint lg. path, length 3;分别用于存储 g(n), h(n), f (n

35、) for int i =0; i g. path, length; i+)GHFi0=0;GHF：i： ：2MaxWeight:对 f (n)初始化，1000无穷大)stack. push (vO) ;. vO 入栈GHFvO0=0;/g(n)GHFvOl=HvO： ;/h(n)GHFLvO2=GHFLvOOj+GHFvO1;/f(n)g. mark _v0=l;while flag 1MinF二MaxWe ight;x=Integer? stack, peek1);处理第一个子节点vex=g. getFirstVex1x1;if vex二二end二 找到11标节点stack, push(v

36、ex);g. mark -vex=二l;break;if (vex!=T) 子找到，继:if (g. mark二vex二=0) 访问GHFtvexl IO=GHFlxj 10+g. pathEx vexj; 廿点 vex 的 g(n)GHFvex l=Hvex; 节点 vex 的 h(n)GHFEvex： 2=GHF：vex ：0HGHF：vex： 1：;if(GHF：vex2MinF)MinF=GHF：vex2;MinVex=vex;处理剩下的邻接点(宽度遍历)while 1vex!=lvex=g. getNextVex1x, vex1;if( vex!mark vex =0) 有邻 节点G

37、HFtvex 0=GHFx 0+g. pathx vex; 节点 vex 的 g(n)GHFvex 1=H：vex ; / vex 的 h(n)GHFlvexJ L2j=GHF：vex： ：0j-GHF：vexJ 1;if (GHFvex 2 Arad-Sibiu-Rirrnicu Vilcea-Pitesti-Bucharest-Urziceni-Hirsova 生长度为：601实验分析:A*搜索估价值h(n)v=n到目标行点的距离实际值，这种情况下，搜索的点数多，搜索围大, 效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离，那么搜索 将严格沿着最短路径进行

38、，此时的搜索效率是最高的。如果估价值实际值，搜索的点数 少，搜索围小，效率高，但不能保证得到最优解。三、实验结果:2“ Jividx k Occirtticn CcW 注 DtbugcteTTUMted M&n (1) Jwt Apolcbor) E:kvWdkA9reWe.6ub2avsexe123154M J必52)笏马尼亚同通】、承安伏无搜察访问的下你:-0-1-2-46-10-11-12访问武此：AradZerind -0radea-SibiuRinnicu Vilcea-CraiovaPitc$ti-Bucharest总长度力：7622、途切求的;蟀询同归下标：-7-12访问过现： Arad-7ori nd - Sibiu-3Fagar2s 、Buchaa$t急长度力：6073、一致代t彳搜室ifiplCfi: -Arad-5ibiu-Rimnicu Vilcca-PitestiBucharest 怨长度力；4184. A4按策访问依下保：-0-4-6-11-12-14-15访配碎 一/radSibiu-Rimnicu Vilcea-Piteti-BucharGt-UrziHirsova 息长戾力：6Q1