罗马尼亚度假问题.docx

二、详细代码测试类：/*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 ids二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 stack, 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 int 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 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, 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, 1000 0,10000,10000,10000, 10000, 10000, 10000, 10000,140, 10000, 151, 10000, 0, 10000, 80, 99, 10000, 10000, 10000, 10000, 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, 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, 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, 10000, 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, 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,10000,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 "式函数 publicStringJ cities=newString J'Arad", "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);)/*访问标志初始化*/publicvoid marklnit11for int i =0; i mark. length; i+) marki>0:) ) /*第一个孩子 * 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 <pathEstartJ jj 10000&&pathstartj '仃关系return j: return-1： )/*下一个孩子* param start * param w* return表示图G中顶点i的第j个邻接顶点的下一个邻接顶点* 返回-1，表示后面没有邻接点了* / publicint getNextVex int start, int w if1 start/=0&&start path. 1ength&&w>=O&&wpath, length1 for int i = w+1; i path. length; i+) if1 path startl il 10000&&pathstartli>0) return i;)return-1;publicint getNumber11 return path, length; ) )I【深度优先】基本原理：深度优先搜索采用堆栈寻找路径，首先从Arad结点出发，判断是否为目标结点, 若否，寻找与该结点的邻接点，先搜索一条分支上的所有节点，然后再去搜索和Arad的其 它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若 否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则 返回失败。深度优先搜索类：/*深度优先搜索类* author dyl */publicclass DFSStack stackz:newStack<Integer> (); 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. getNextVex1x, 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 Appiicaton 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为基础的，它限制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： depthMax*/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 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 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总长度为:607实验分析：因为迭代加深是从按照深度的递增搜索的，所以说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 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 goal, int ,J (Stack Integer> stack =newStack<Integer>(); 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 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：开始* 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.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_= 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队列中移至队列头 */publicvoid 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;)实验结果：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到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件，关键在于估价函数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= 10000 ： / 左东无穷大Stack stack=newStack<Integer> ();/*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) for int i =0; i g. path, length; i+)GHFi0=0;GHF：i： ：2>MaxWeight:对 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(vex);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：vex2<MinF)MinF=GHF：vex2'MinVex=vex;处理剩下的邻接点(宽度遍历)while 1vex!="lvex=g. getNextVex1x, vex1;if( vex!mark vex =0) 有邻 节点GHFtvex 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 <MinF) MinF=GHF：vex2;MinVex=vex:if(vex=-1) 没有邻接点了，此时确定最小、消耗节点，并压栈 stack. push'MinVex1 ;g. mark_MinVex=l;break;if1 vex-end ,stack. push (vex); 选栈I标节点g. mark_vex_=l;flag=false;break;)else没有子节点或者子节点被访问J',循环HI栈while 1 vex-lstack. pop 1);)newMainO. show g, stack);)实验结果：4.AF炼访问过程：->Arad->Sibiu->Rirrnicu Vilcea->Pitesti->Bucharest->Urziceni->Hirsova 生长度为：601实验分析:A*搜索估价值h(n)v=n到目标行点的距离实际值，这种情况下，搜索的点数多，搜索围大, 效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离，那么搜索 将严格沿着最短路径进行，此时的搜索效率是最高的。如果估价值>实际值，搜索的点数 少，搜索围小，效率高，但不能保证得到最优解。三、实验结果:2“ Jividx k Occirtticn CcW 注 © DtbugcteTTUMted> M&n (1) 'Jwt Apolcbor) E:kvWdkA9reWe.6ub2avsexe123154M ' J必52)笏马尼亚同通】、承安伏无搜察访问的下你:->0->1->2->4>6->10->11->12访问武此：>Arad>Zerind ->0radea->Sibiu>Rinnicu Vilcea->Craiova>Pitc$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访配碎 一>/rad>Sibiu->Rimnicu Vilcea->Piteti->BucharGt->Urzi<Gni->Hirsova 息长戾力：6Q1