罗马尼亚度假问题.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为基础的,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 罗马尼亚 度假 问题
链接地址:https://www.31doc.com/p-14397397.html