罗马尼亚度假问题.doc

二.详细代码 测试类：/*Main类，打印各个算法的结果* author dyl*/classMainint result;int xiabiaoIZ二nu 11;/访问的 卜标publicstaticvoid main1String., args 1Graph graph=newGraph();System, out. printin1罗马尼亚问题“);System, out. printin' "1、深度优先搜索");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 1深度设 15System, out. printin ("3、一致代价搜索");UCS ucs=new UCS1 graph, 0, 121;System, out. printin("4、A*搜索");AXing aXing=newAXing1 :,;aXing. A_Search (graph, graph. H, 0. 15 * : /0-15 即 Arad 到达 Hirsova /*打印* param g:图* param stack：栈*/publicvoid show Graph g,Stack stackif1 stack, size 1 )=0 1System, out. printin'路径搜索失败");return;result=0:System, out. print C访问的下标： “)；for int i 二0; istack size1); i+)System. out print一一>，z+stack. get1 i <System out print1 "n 访I、可过“);xiabiao=newint.stack size 1)_;if' stack. isEmptySystem, out. printin'/'搜索失败);elsefor int i 二0;istack.sizeT; i+) System out print一一"+g cities 一 Integer1 stack get i1_);for int i 二0;istacksize)-l; i+)Iresult+g. path _1 Integer stack get i. _1 Integer1 stack get1i+1 J;System out printin' "n ，总长度为:z，+resuIt+"n");g. marklnit () ; /清空访问/*图类* author dyl*/publicclassGraphpublicint path IJ 二二 newint 二I 0, 75, 10000, 11& 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,11& 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, 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, 13& 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, 9& 10000, 142, 10000, 10000),10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,10000,10000,10 000, 10000, 10000. 9& 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 :；武函数publicStringJ cities二newString"Arad", "Zerind", "Oradea", "Timisoar a , Sibiu , Lugoj ,"RimnicuVilcea", "Fagaras", "Mehadia", "Drobeta", "Craiova", "Pitesti", "Bucharest" ,Giurgiu , Urzicem , Hirsova ,"Eforie", "Vaslui", "Isi", "Neamt" ; .7城市 名publicint 二mark=newint20;/ /访问标记pub 1 i eGraph () 得到数据marklnit1);/*访问标志初始化*/publicvoid marklnit1for int i 二0; i mark length; i+)marki>0:/*第一个孩子* param g* param start* return T表示一个孩子都没有*/publicint getFirstVex int start1if'start >=0&&start path length丨for int j 二0; j path length; j+)if1 path start jj 10000&&path start I j O' J 关系return j:return-1;/*下一个孩子* param start* param w* return表示图G中顶点i的第j个邻接顶点的下一个邻接顶点*返回-1，表示后面没有邻接点了*/publicint getNextVex int start, int wif1 start/=0&&start path length&二0&&wpath length】for int i 二 w+1: ipath.1ength; i+)if1 path startl il 10000&&pathstartli>0)return i;return-1;publicint getNumber11return path, length;I【深度优先】基本原理：深度优先搜索采用堆栈寻找路径，首先从Aad结点岀发，判断是否为目标结点, 若否，寻找与该结点的邻接点，先搜索一条分支上的所有节点，然后再去搜索和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 vg stack push (vO) ; /入栈g. mark IvO=l;. vO 被访问while truex= (Integer) stack, peek (); /査看栈顶 t 素w=g. getFirstVex1 x ;while (g. markw=1) 戮访问，则寻找下-个邻接点w=g getNextVex1x, w ;if (w=T) break;wh订e (W1) /没冇找到下一个邻接点stack, pop);x=1 Integer ：1 stack peek 0 ;w=g. getFirstVex x ;while g. mark_w_lw=g getNextVex-x, w ;if (w=T) break;stack. push1w);g. mark _w_ 二 1;if (w=vg) break;到达终点newMain 0 show g, stack);实验结果：terminatedMain (l)卩负 AppiicotoM EV皿、jdkArdjreW"ubinEeM (2015-4-14 罗B尼亚冋J8l 先搜萦访问的下示： ->0- >1«->2->4->6->10->11- ->12访祠过程：->Arad-«>Zeri(Mi->Oradea->Sibiu->Rininicu Vilcea->Craiova->Pitesti->Bucharest总长度为:762实验分析: 根据结果可只知，在有限状态空间下，树搜索不是完备的，图搜索完备：无限状态下不完备。此结果0->1->2->4->6->10->11->12只是其中一条，但不是最优解。分支因子b,深度do则最坏情况下时间复杂度也髙达，空间复杂度，存需求少。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+) /迭代 depthMax 次if1 dfsearch1 g, vO, vg, i =1break;/材深度搜索* param g：图* param vO：开始节点* param vg： H 的节点* param depthMax： depthMax* return*/publicint dfsearch1 Graph g, int vO, int vg, int depthMax1 int x;int w： zvO的第-个邻接点stack push1 vO ; /At戈g. mark IvO=l; / vO 被访问while truex=(Integer) stack, peek (); /查看栈顶元素w=g. getFirstVex x ;while (g. mark»=l) /被访问，则:j1找 I、- 个w=g getNextVex1x, w :if (w=-l) break;while(w1) /没有找到下一个邻接点stack. pop ();if (stack, size ()=0) /清空了栈里的元素g. marklnit; . 7访问初始化returnO:x=1 Integer1 stack peek1);w=g.getFirstVex x ;while g. ma:rk_w_=lw=g. getNextVex1x, w :if (w=-l) break;stack push(w);g.二 1;if iw二二vg1break; 检查是否达到终点if (stack, size ()二depthMax) /重新迭代则重新初始化值 stack. pop1);newMain1) show g, stack1 ; returnl;实验结果：2、迭代加深的搜索访问过程：->Arad->Zerind->Ora(iea->$ibiu->Fagaras->Bucharest狀度为:607lUirnSINET实验分析：因为迭代加深是从按照深度的递增搜索的，所以说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 =newint20J;/用于保X前结点到起始纟吉点的实I；小路径长度for int i 二0; i pre length; i+)pre i=l;distli二10000;/调用一致搜索算法搜索路径UC_search1 g, start, end, dist, pre 1 ;/打印路径显示函数 displayPath1 start, end, pre,g;/* param start：开始* param goal： LI 的* param prev：询驱节点* param g：图prev, Graph g)*/publicvoid displayPath1int start, int goal, int J Stack Integer> stack =newStack<Integer>();stack. push1 goal ;while prev.goalJ!二 start1stack push'prevZgoal.);goal 二 prev _goaL :stack. push(start);System, out. print访问的下标：”)；for int i = stack.size)T; i >=0; i) System out print一一>，z+stack get1 i ;System. out print' "n 访I、可过程:“);for int i = stack.sizeT; i >=0; i-) System out print'"一一>"+ g.cities .stack. get i);System, out. print ("n 总长度为:“);int result=0;for int i 二0; i stack.sizel; i+) result+=g. path stack get1i' stack get i+1'_;System. out print1 result );System. out printin'"n");g. marklnit;/* param g：图* param start：开始* param goal： U fit)* param prev： |j了驱节点*/publicvoid UC_search1 Graph g, int start, int goal, intJ dist, intJ pre-List Integer list =newArrayList Integer>();list add1 start：1 ;while 1!list. isEmpty111moveMinToTop (list, dist): 将dis亠I中最小值所对应的结点,移至list队首int current二list, remove(0);/将list队首的纟吉点出队，并展开g. mark.current.=1;if1 current = goalreturn;for int j 二0; j g. path.current_1ength; j+)if1g pathlcurrentl Ijl 10000&& g. markj二二0if (! isInList j list) / 结点 j 不在队歹ij 4-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 isEmpty111System, out. printin'搜索不成功! “)；/*检查结点d,是否在队列list里publicboolean isInList int a,List Integer list1for int i 二0; i list.size1);i+)if1 list, get i) a1returntrue:returnfalse;/*将dist数组中的最小值所对应的结点，从list队列中移至队列头*/publicvoid moveMinToTop List Integer> list, int dist1int index 二0;int min 二 dist .index.;for int i 二0; i list.size);i+)int a 二 list.get i1;if1dist'a min1index 二 i;min = dist _a.:int temp 二 list.get index1:for int i 二 index; i 0; i-)list, set1 i, list, get1 i T；list, set1 0, temp 1 ;实验结果：3. 一狡代价揑案访河的"F 粽:->0- - >4->6->11->12访河述：:->Arad->Sibiu«->Rimnicu Vilcea->Pitesti->8uchares.t 总长度为：41S实验分析：从结果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 dylpublicclassAXingintMaxWeight=10000： /表示无穷大Stack stack=newStack<Integer> ();搜索* param g：图* param H： 启发式函数值* param vO：初始值* param end： U 标值*/publicvoid A_Search1 Graph g, int H_J, int vO, int endboolean flag二true;int x;/表示栈顶元素int vex;/寻找I标节点intMinF, MinVex二vO; /记录最小的f (n)和对应的节点int GHF=newint Ig. path, length 3;分别用于存储 g(n), h(n), f (n) for int i 二0; i g. path.length; i+)GHFEi0>0;GHF：i： ：2： =MaxWeight:对 f(n)初始化，1000丿l?力'丿、stack, push(vO) ;. vO 入栈GHFEvO0=0;/g(n)GHFvOl=HvO;/h(n)GHFLvO 2>GHF：vO： 0>GHF：v0 1 ;/f (n)g. mark _v0二 1;while flag 1MinFMaxWeight;x二iInteger 1 stack, peek1);处理第一个子节点vex二g. getFirstVex1x1;if 'vexend找到I I标盯点stack, push(vex);g. mark 一vex.二1;break;if(vex!-l)子 找到，继:辻(g. mark vex二二0) 访间GHFvex 0二GHFx 0+g. pathEx vex;/ 肖点 vex 的 g(n)GHFEvex l=Hvex ;/节点 vex 的 h(n)GHFEvex： L2>GHF：vex； ：0HGHF：vex： 1：;if(GHFvex2<MinF)MinF二GHFlvex2;MinVex二vex;处理剩下的邻接点(宽度遍历)while 1vex!=lvex=g. getNextVex1x, vex1;if (vex! =-l&&g. mark vex =0) 有邻节点GHFlvexI lOlGHFlx! lOl+g. pathlxl IvexZ ；节点 vex 的 g(n)GHF:vex： ：1>H:vex ;/vex 的 h (n)GHFlvexJ2二GHFvex0-GHFvex1;if(GHFvex2<MinF)MinF=GHF：vex2;MinVex=vex:if (vex=-l) /没有邻援点了，此时确定最小消耗节点，并爪栈 stack. push'MinVex1;g. mai?k_MinVex二 1;break;if1 vex二二end、stack, push (vex) ; /I k栈 L I 标节点g. mark .vex一二 1;flag=false;break;elsef没冇子节点或者子节点被访问J，循环出栈while 1 vex=Tstack. pop 1);newMain() show g, stack);实验结果：4. AT殊访问的 TIf »->0->4 >6->11->12->14->15访问itfl：->Arad >Sibiu->Riimicu Vilcea->Pitesti->Bucharest->Urziceni->Hirsova 总长度为：601实验分析:A*搜索估价值h(n)<= n到目标盯点的距离实际值，这种情况下.搜索的点数多，搜索围大, 效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索 将严格沿着最短路径进行，此时的搜索效率是最高的。如果估价值实际值，搜索的点数 少，搜索围小，效率髙，但不能保证得到最优解。三.实验结果:.HZSES W jMdx 眩 OccUrXicn Oamdc '江 Q D<bugcteroMted> Man (1) Apolcbor) E:kvjWaFrejre.6u'bha?“vQ6e (2315414 Fg：殆52)罗9尼亚伺題1、床JE仇夭搜5?VJ 冋的T 缺->6->10->11->12WflSR:>Arad>Zerind ->Oradea->Sibiu八 >Rinnicu Vilcea->Craiova>Pitc$ti->Bucharest总良I#力：7622、爸闵加滾的；猜游冋曲"F标：->0->1->2->4- ->7->12iSfiiSfx:A”d >7ori nd - ->0rdp.a- -、Sibiu、"沪 r25、BiKh"Q$t 2弋力:6073、一数代VJffiNTB；ifiplCfi:->Arad->Sibiu->Rimnicu Vilcca->PitestiBucharest怎垛庚加4184 A«»jR访同KT»： ->0->4->6->11->12->14->15访砸程->/rad->Sibiu->Rimnicu Vilcea->Piteti->BucharGt->Urzi<：Gni->Hirsova 59力：6Q1sniscs*