人工智能课程设计报告-罗马尼亚度假问题

1、人工智能课程设计报告 课 程:人工智能能课程设计计报告 班 级: 姓 名: 学 号: 指导教师:赵曼 2015年年11月 - 49 -人工智能课课程设计报报告课程背景 人工智能（AArtifficiaal Inntellligennce），英英文缩写为为AI。它它是研究、开发用于于模拟、延延伸和扩展展人的智能能的理论、方法、技技术及应用用系统的一一门新的技技术科学。 人工智智能是计算算机科学的的一个分支支，它企图图了解智能能的实质，并并生产出一一种新的能能以人类智智能相似的的方式做出出反应的智智能机器，该该领域的研研究包括机机器人、语语言识别、图像识别别、自然语语言处理和和专家系统统等。人工工

2、智能从诞诞生以来，理理论和技术术日益成熟熟，应用领领域也不断断扩大，可可以设想，未未来人工智智能带来的的科技产品品，将会是是人类智慧慧的“容器”。人工智能是是对人的意意识、思维维的信息过过程的模拟拟。人工智智能不是人人的智能，但但能像人那那样思考、也可能超超过人的智智能。人工智能是是一门极富富挑战性的的科学，从从事这项工工作的人必必须懂得计计算机知识识，心理学学和哲学。人工智能能是包括十十分广泛的的科学，它它由不同的的领域组成成，如机器器学习，计计算机视觉觉等等，总总的说来，人人工智能研研究的一个个主要目标标是使机器器能够胜任任一些通常常需要人类类智能才能能完成的复复杂工作。但不同的的时代、不

3、不同的人对对这种“复杂工作作”的理解是是不同的。人工智能是是计算机学学科的一个个分支，二二十世纪七七十年代以以来被称为为世界三大大尖端技术术之一（空空间技术、能源技术术、人工智智能）。也也被认为是是二十一世世纪三大尖尖端技术（基基因工程、纳米科学学、人工智智能）之一一。这是因因为近三十十年来它获获得了迅速速的发展，在在很多学科科领域都获获得了广泛泛应用，并并取得了丰丰硕的成果果，人工智智能已逐步步成为一个个独立的分分支，无论论在理论和和实践上都都已自成一一个系统。人工智能是是研究使计计算机来模模拟人的某某些思维过过程和智能能行为（如如学习、推推理、思考考、规划等等）的学科科，主要包包括计算机机

4、实现智能能的原理、制造类似似于人脑智智能的计算算机，使计计算机能实实现更高层层次的应用用。人工智智能将涉及及到计算机机科学、心心理学、哲哲学和语言言学等学科科。可以说说几乎是自自然科学和和社会科学学的所有学学科，其范范围已远远远超出了计计算机科学学的范畴，人人工智能与与思维科学学的关系是是实践和理理论的关系系，人工智智能是处于于思维科学学的技术应应用层次，是是它的一个个应用分支支。从思维维观点看，人人工智能不不仅限于逻逻辑思维，要要考虑形象象思维、灵灵感思维才才能促进人人工智能的的突破性的的发展，数数学常被认认为是多种种学科的基基础科学，数数学也进入入语言、思思维领域，人人工智能学学科也必须须

5、借用数学学工具，数数学不仅在在标准逻辑辑、模糊数数学等范围围发挥作用用，数学进进入人工智智能学科，它它们将互相相促进而更更快地发展展。题目一：罗罗马利亚度度假问题一. 问题题描述分别用代价价一致的宽宽度优先、有限制的的深度优先先（预设搜搜索层次）、贪婪算法法和A*算法求解解“罗马利亚亚度假问题题”。即找到从从初始地点点 Araad到 目目的地点 Buchharesst 的一条路路径。要求：分别用文件件存储地图图和启发函函数表，用用生成节点点数比较几几种算法在在问题求解解时的效率率，并列表给出出结果。数据如下：1、地图2、启发函函数值Arad 366 Mehaadia 241 Buchhares

6、st 0 Neammt 2334 Craiiova 160 Oraddea 3380 Dobeerta 242Pitessti 1100 Eforrie 1161 Rimmmicu_Vikeea 1993 Fagaaras 176 Sibiiu 2553 Glurrgiu 77Timissoaraa 3299 Hirssova 151 Urziicenii 80 Iasii 2266 Vasllui 1199 Lugooj 2444 Zeriind 33743、地图数数据表0 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000

7、 1440 10000 1188 10000 10000 11000 10000 10000 7551000 0 10000 10000 11000 10000 75 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 70 100001000 10000 0 10000 11000 10000 10000 1001 10000 10000 2211 10000 900 10000 11000 85 10000 10000 11000 100001000 10000 10000 0 10000 11000 1000

8、0 10000 10000 11000 10000 10000 10000 11000 10000 10000 877 10000 10000 110001000 10000 10000 10000 00 10000 1200 138 10000 1466 10000 10000 11000 10000 10000 10000 11000 10000 10000 100001000 10000 10000 10000 11000 0 10000 10000 11000 10000 10000 1551 10000 10000 11000 10000 10000 10000 11000 7110

9、00 75 10000 10000 1120 10000 0 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 100001000 10000 1011 10000 1388 10000 10000 0 10000 997 10000 10000 10000 11000 10000 10000 10000 11000 10000 100001000 10000 10000 10000 11000 10000 10000 10000 00 11000 10000 10000 10000 11000 86

10、 10000 10000 11000 10000 100001000 10000 10000 10000 1146 10000 10000 977 10000 0 10000 880 10000 11000 10000 10000 10000 11000 10000 100001000 10000 2111 10000 10000 10000 11000 10000 10000 10000 00 999 10000 10000 10000 11000 10000 10000 10000 11000140 10000 10000 10000 11000 151 10000 10000 10000

11、 880 99 0 10000 10000 10000 11000 10000 10000 10000 110001000 10000 90 10000 10000 11000 10000 10000 10000 11000 10000 10000 0 10000 11000 10000 10000 10000 11000 10000118 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 0 10000 10000 11000 10000 1111 100001000 10000 10000 100

12、00 11000 10000 10000 10000 886 10000 10000 10000 11000 10000 0 988 10000 11000 10000 100001000 10000 85 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 98 0 10000 10000 10000 110001000 10000 10000 877 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 10000 0 922 100

13、00 100001000 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 992 0 10000 100001000 70 10000 10000 11000 10000 10000 10000 11000 10000 10000 10000 11000 111 10000 10000 10000 11000 0 1000075 10000 10000 10000 11000 71 10000 10000 11000 10000 10000 10000 11000

14、 10000 10000 10000 11000 10000 10000 0二.设计分分析1.算法分分析 1) 宽度优先先搜索算法广度优先搜搜索使用队队列（quueue）来来实现1、把根节节点放到队队列的末尾尾。2、每次从从队列的头头部取出一一个元素，查查看这个元元素所有的的下一级元元素，把它它们放到队队列的末尾尾。并把这这个元素记记为它下一一级元素的的前驱。3、找到所所要找的元元素时结束束程序。4、如果遍遍历整个图图还没有找找到，结束束程序。2)深度优优先搜索算算法深度优先搜搜索用栈（sstackk）来实现现，整个过过程可以想想象成一个个倒立的树树形：1、把根节节点压入栈栈中。2、每次从从栈

15、中弹出出一个元素素，搜索所所有在它下下一级的元元素，把这这些元素压压入栈中。并把这个个元素记为为它下一级级元素的前前驱。3、找到所所要找的元元素时结束束程序。4、如果遍遍历整个树树还没有找找到，结束束程序。3)贪婪算算法1.建立数数学模型来来描述问题题把求解的的问题分成成若干个子子问题。对每一子子问题求解解，得到子子问题的局局部最优解解。把子问题题的解局部部最优解合合成原来解解问题的一一个解。实现该算法法的过程：从问题的某某一初始解解出发；whilee 能朝给给定总目标标前进一步步do求出可行解解的一个解解元素；由所有解元元素组合成成问题的一一个可行解解。4)A*算算法A*1 （AA-Staa

16、r)算法法是一种静静态路网中中求解最短短路最有效效的直接搜搜索方法。公式表示为为： f(n)=gg(n)+h(n),其中 f(n) 是是从初始点点经由节点点n到目标标点的估价价函数，g(n) 是在状态态空间中从从初始节点点到n节点点的实际代代价，h(n) 是从n到到目标节点点最佳路径径的估计代代价。保证找到最最短路径（最最优解的）条条件，关键键在于估价价函数f(n)的选选取：估价值h(n)实际际值,搜索索的点数少少，搜索范范围小，效效率高，但但不能保证证得到最优优解。2.数据结结构1)图结构构： 实现存储储“罗马尼亚亚度假问题题”的图空间间； 抽象图结结构的实现现：typeddef struu

17、ct /图节节点类型charr cittynamme200;int vallue;int cosst;Ver;classs Grapph /图图结构publiic:Grapph();Graaph(); VVer VVMaxxV;int edgeeMaxxVMaxxV;int numoofedgges; /注意这这个变量的的引用位置置/读取取地图节点点信息voidd ReaadVerrtex();/读取取地图边关关系信息voidd ReaadEdgge();/取与与第V个节节点的第一一个邻接点点int GetFFirsttVerttex(iint vv);/找到到第V1个个节点的VV2之后的的下

18、一个邻邻接节点int GetNNextVVerteex(innt v11, innt v22);int GetVVerVaalue(int iindexx);/获取Vindeex 的的ver 的vallue值int GetVVerCoost(iint iindexx);/获取Vindeex 的的ver 的cosst 值int GetEEdge(int rrow, int ccol);/获取取edgeerowwcool 的的值voidd SettVerCCost(int iindexx,intt cosst);2)队列结结构宽度优先算算法以及AA*算法 使用到。抽象队列结结构实现：classs

19、SeqQQueueepubliic:SeqQQueuee();SeqqQueuue();voidd QueeueInnitiaate();int QueuueNottEmptty();int QueuueApppend(int xx);int QueuueDellete(int *d);int QueuueOrdderApppendd(intt x, Grapph &GG);/A*算法使用用int Queuue_A_OrdeerApppend(int xx, Grraph &G);privaate:int queuueMaaxSizze;int rearr;int fronnt;int cou

20、nnt;3)栈结构构深度优先算算法使用；栈结构的抽抽象类型实实现：classs Stacckpubliic:Stacck();Staack();booll StaackNootFulll();booll StaakNottEmptty();voidd StaackPoop(Grraph &G);voidd StaackPuush(iint xx, Grraph &G);voidd PriintSttack(Grapph &GG);int GetWWeighht();privaate:int a1000;int top11;int weigght;三.算法设设计1) 宽度度优先搜索索算法/宽度优

21、优先算法void Romaania_Tripp:BrroadFFirsttSearrch(GGraphh &graaph, int v)int u, ww; i = 0;SeqCCQuenne quueue;visiitedv = 1;/访问节点点counnt+;if (v = end)retuurn;queuue.QuueueAAppennd( vv);/入入队列whille (qqueuee.QueeueNootEmppty()/队队列非空queeue.QQueueeDeleete(&u);/取队列列节点w = graaph.GGetFiirstVVerteex( uu);whiile (

22、w != -1) /有子子节点的话话iff (!vvisittedww)/如果子节节点未被访访问，则访问子子节点VVisitt(w, u);vvisittedww = 1;ccountt+;iif (ww = end)/找到到结果Prinnt(grraph, b, end, v);retuurn;qqueuee.QueeueApppendd(w);/节点点压入队列列w = grraph.GetNNextVVerteex(u, w);2)深度优优先搜索算算法/深度优优先算法bool isOKK = ffalsee;int llevell = 00;constt int LLevell = 88;

23、/预预设的搜索索层次void Romaania_Tripp:DeepthFFirsttSearrch(GGraphh &graaph, int v, Stackk &staack)int w; ii = 00;if (isOKK = truee)retuurn;if (leveel+1 Leevel)retuurn;/大于于搜索层次次时不再深深入leveel+;visiitedv = 1;/访问该节节点counnt+;stacck.SttackPPush(v, graaph);if (v = end | sstackk.GettWeigght() = MaxWWeighht)w = -1;if

24、 (v = end&staack.GGetWeeightt() = MaaxWeiight)coout sttack.GetWWeighht()MMaxWeeightt = sstackk.GettWeigght();*/coout 路径径长度为： staack.GGetWeeightt() enndl 访问问节点数为为： coount eendl搜索层层次：levvelendll;issOK = truue;elseew = graaph.GGetFiirstVVerteex(v);/取取当前节点点的第一个个子节点whille (ww != -1)if (!viisiteedw)Deepth

25、FFirsttSearrch(ggraphh, w, staack);/递归归访问w = graaph.GGetNeextVeertexx(v, w);/取取当前节点点的下一个个子节点visiitedv = 0;/返回时置置该节点为为未访问stacck.SttackPPop( grapph);/将将该节点弹弹出栈，并并根据grraph 中weiight 的值更改改当前栈值值leveel-;3)贪婪算算法/贪婪算算法void Romaania_Tripp:Grreedyy_Alggoritthms(Grapph &graaph, int v)int u, ww;SeqCCQuenne quueu

26、e;/队列列存储图节节点在图中中的索引值值,优先队队列，vaalue小小的在队头头visiitedv = 1;if (v = end) reeturnn; queuue.QuueueOOrderrAppeend( v, graaph);/图节节点按优先先顺序入队队列counnt+; /访访问节点数数+1whille (qqueuee.QueeueNootEmppty()/宽宽度优先，循循环queeue.QQueueeDeleete( &u);/删除除队列头元元素并返回回删除的数数值/ccout u= u ;w = graaph.GGetFiirstVVerteex(u);whiile (w !

27、= -1)iff (!vvisittedww)VVisitt(w, u);/访问ww节点，将将way b 的指指向更新iif (ww = end) /coout ww=ennd;counnt+; retuurn; qqueuee.QueeueOrrderAAppennd( ww, grraph); /图节点按按优先顺序序入队列ccountt+;w = grraph.GetNNextVVerteex(u, w);4)A*算法/A*算算法void Romaania_Tripp:ASStar_Algoorithhms(GGraphh &graaph, int v)/i = 0; couunt = 0

28、;int u, ww;SeqCCQuenne quueue;if (v = end) retturn;/到达达终点queuue.Quueue_A_OrrderAAppennd(v, graaph); counnt+;whille (qqueuee.QueeueNootEmppty()queeue.QQueueeDeleete( &u);if (u = ennd)coout 路径径长度为： graaph.GGetVeerCosst(u) + ggraphh.GettVerVValuee(u) eendl 访问问节点数为为： coount eendl;reeturnn;w = graaph.GGe

29、tFiirstVVerteex( uu);whiile (w != -1)innt coost=ggraphh.GettVerCCost(u) + graaph.GGetEddge(ww,u);grraph.SetVVerCoost(ww, coost);/设置置当前节点点移动到目目标节点的的预估费用用quueue.Queuue_A_OrdeerApppend( w, grapph);/按按预估费用用优先入队队列 coount+;w = grraph.GetNNextVVerteex(u, w);四.运行结结果及分析析分析：节点数路径长度耗时msOptimmalitty: Complleten

30、ness: BFS1145016NoYESDFS 1260531NoNOGreeddy845016NONOA*算法164180YESYES通过比较，GGreeddy搜索生生成的结点点数目最少少，为8个个，效率最最高；A*算法生成成的结点数数目最多，为为30个，效效率最低。DFS（一一般）、BFS和和Greeedy搜索索找到的都都不一定最最优解， A*算法法具有完备备性且始终终找到的是是最优解。宽度优先先虽然是完完备的（如如果分支因因子有限的的话），在在任何情况况下宽度优优先都能找找到一个解解，但是，它它找到的第第一个解并并非最优的的，此外，最最坏的情况况是，当目目标结点是是第d层的的最后一个个

31、被扩展的的结点时，它它将耗费大大量的时间间。宽度优优先时间复复杂度：（bb为分支因因子，d为为深度）；空间复杂杂度为所存存储的节点点的个数。DFS不不是完备的的（除非查查找空间是是有限的），同同时，它也也不能找到到最优解。深度优先先的时间复复杂度：；空间复杂杂度：（bb为分支因因子，m为为深度，仅仅有一枝需需要存储）；。贪婪算算法不是完完备的。同同时，它找找到的解也也不一定是是最优解。其时间复复杂度：（bb代表分支支数，m为为深度）；空间复杂杂度为）。所以只有有A*算法法和DFSS（回溯+剪枝）是是完备的，且且能够找到到最优解；其时间复复杂度：扩扩展节点的的数目；空空间复杂度度：所有生生成的结

32、点点。综合来来看，BFFS和贪婪婪算法的效效率较高，但但解并非最最优，而AA*算法的的效率稍逊逊色，但解解为最优；DFS（回回溯+剪枝枝）搜索虽虽能找到最最优解但效效率最低。源代码/Graaph.hh#praggma onceeusingg nameespacce sttd;#defiine MaxVV 20 /*#iffndeff MY_DEBUUG#defiine MMY_DEEBUG #endiif*/typeddef struuctcharr cittynamme200;/城市名int vallue;/权值int cosst;/A*算法法中从当前前节点移动动到目标节节点的预估估费用Ve

33、r;classs Grapphpubliic:Grapph();Graaph(); VVer VVMaxxV;int edgeeMaxxVMaxxV;int numoofedgges; /注意这这个变量的的引用位置置/读取取地图节点点信息voidd ReaadVerrtex();/读取取地图边关关系信息voidd ReaadEdgge();/取与与第V个节节点的第一一个邻接点点int GetFFirsttVerttex(iint vv);/找到到第V1个个节点的VV2之后的的下一个邻邻接节点int GetNNextVVerteex(innt v11, innt v22);int GetVVer

34、Vaalue(int iindexx);/获取Vindeex 的的ver 的vallue值int GetVVerCoost(iint iindexx);/获取Vindeex 的的ver 的cosst 值int GetEEdge(int rrow, int ccol);/获取取edgeerowwcool 的的值voidd SettVerCCost(int iindexx,intt cosst);privaate:;/Queeue.hh#praggma oncee#incllude#incllude Staack.hh#defiine MaxSSize 30/*#iffndeff MY_DEBUU

35、G#defiine MMY_DEEBUG #endiif/*/classs SeqQQueueepubliic:SeqQQueuee();SeqqQueuue();voidd QueeueInnitiaate();int QueuueNottEmptty();int QueuueApppend(int xx);int QueuueDellete(int *d);int QueuueOrdderApppendd(intt x, Grapph &GG);/A*算法使用用int Queuue_A_OrdeerApppend(int xx, Grraph &G);privaate:int queuue

36、MaaxSizze;int rearr;int fronnt;int counnt;typeddef SeqQQueuee SeqCCQuenne;/Rommaniaa_Triip.h#praggma oncee#incllude Queeue.hhtypeddef struuctint fathher;int me;way;classs Romaania_Tripppubliic:Romaania_Tripp();Rommaniaa_Triip();voidd Vissit(iint vv, innt u);voidd Priint(GGraphh &grraph, wayy *b, int

37、t endd, innt sttart);voidd BrooadFiirstSSearcch(Grraph &graaph, int vv);voidd DeppthFiirstSSearcch(Grraph &graaph, int vv,Staack &stacck);voidd Greeedy_Algoorithhms(GGraphh &grraph, intt v);voidd ASttar_AAlgorrithmms(Grraph &graaph, int vv);voidd ReSSet();int GetCCountt();int GetMMaxWeeightt();int G

38、etEEnd();way* GettB();privaate:way *b;int i;int end;int counnt;int visiitedCCity20;int MaxWWeighht;int visiited20;/Staack.hh#praggma oncee#inclludeGrapph.h#inclludeusingg nameespacce sttd;/*#iffndeff MY_DEBUUG#defiine MMY_DEEBUG #endiif*/classs Stacckpubliic:Stacck();Staack();booll StaackNootFulll()

39、;booll StaakNottEmptty();voidd StaackPoop(Grraph &G);voidd StaackPuush(iint xx, Grraph &G);voidd PriintSttack(Grapph &GG);int GetWWeighht();privaate:int a1000;int top11;int weigght;/Graaph.ccpp#inclludeGrapph.h#incllude#incllude#incllude#inclludeusingg nameespacce sttd;Graphh:Graaph()numoofedgges =

40、0;Graphh:GGraphh()void Grapph:RReadVVerteex()int i=0, v;charr ch20;fstrream infiile(启发式数数值.txxt, ios:in);whille (iinfille ch & iinfille v)#ifdeef MYY_DEBBUGpriintf(%st%dn, ch, v);#endiifVii.vaalue = v;Vii.coost = 0;strrcpy(Vi.cittynamme, cch);i+;void Grapph:RReadEEdge()int valuu, i;fstrream infiile(

41、地图数据据表.txxt, ios:in);i = 0;whille (iinfille vallu)edggei / 200i % 200 = valuu;#ifdeef MYY_DEBBUGif (i % 20 = 00)couut enddl;couuteedgei/200i%20tt;#endiifi+;/取与第第V个节点点的第一个个邻接点int GGraphh:GeetFirrstVeertexx(intt v)if (v= 20)retturn -1;for (intt coll = 00; cool00 & edgeevcool11000)retturn col;retuurn -

42、1;/找到第第V1个节节点的V22之后的下下一个邻接接节点int GGraphh:GeetNexxtVerrtex(int v1, intt v2)if (v1= 20 | vv2= 20)retturn -1;for (intt coll= v22 + 11; cool0 & edggev11cool11000)retturn col;retuurn -1;int GGraphh:GeetVerrValuue(innt indeex)/获取取Vinndex 的veer 的vvaluees值retuurn VVinddex.valuue;int GGraphh:GeetVerrCostt(in

43、tt indeex)/获取取Vinndex 的veer 的ccost 值retuurn VVinddex.costt;int GGraphh:GeetEdgge(innt row, int col)/获取取edgeerowwcool 的的值retuurn eedgerowcol;void Grapph:SSetVeerCosst(innt indeex, intt costt)Vinndex.cosst = costt;/Queeue.ccpp#inclludeQueuue.h#incllude#incllude Staack.hhSeqQuueue:SeqqQueuue()rearr = 0

44、0;fronnt = 0;counnt = 0;SeqQuueue:SeeqQueeue()int SSeqQuueue:QueeueNootEmppty()if (counnt != 0)rreturrn 1;elsee retuurn 00;int SSeqQuueue:QueeueApppendd( innt x)if (counnt0 & rrear = ffrontt)couut 队列列已满 eendl;retturn 0;elseequeeuerrear = xx;reaar = (reaar + 1) % MaxxSizee;couunt+;retturn 1;int SSeqQ

45、uueue:QueeueDeeletee( innt *d)if (counnt = 0)couut 队列列已空 0 & rrear = ffrontt)couut 队列列已满 = GG.Vqqueueereaar - 1.valuue)/队尾插入入quueuerearr = x;reear = (reear + 1) % MaaxSizze;coount+;reeturnn 1;elsseiff (G.Vx.vaalue G.Vqqueueepossitioon.valuue)posiitionn+;iint ii;ffor (i = fronnt; ii0 & rrear = ffront

46、t)couut 队列列已满 x22 )/队尾插入入quueuerearr = x;reear = (reear + 1) % MaaxSizze;coount+;reeturnn 1;elsse /队头插插入iff (G.Vx.vaalue + G.Vx.coost G.Vqqueueepossitioon%MaaxSizze.valuue + G.Vqqueueepossitioon%MaaxSizze.costt)posiitionn+;iint ii;ffor (i = fronnt; iipossitioon; ii+)queuue(ii - 11 + MMaxSiize) % Maa

47、xSizze = queeueii%MaxxSizee;qqueuee(i - 1 + MaaxSizze) % MaxxSizee = x;ffrontt = (fronnt - 1 + MaxSSize) % MMaxSiize;ccountt+;rreturrn 1;retuurn 00;/Romaania_Tripp.cppp#inclludeRomaania_Tripp.h#incllude#incllude#inclludeusingg nameespacce sttd;Romannia_TTrip:Rommaniaa_Triip()b = new way1100;i = 0;en

48、d = 2;counnt = 0;MaxWWeighht = 100000;for (sizze_t i = 0; ii 220; ii+)vissiteddi = 0;void Romaania_Tripp:ReeSet()if(NNULL!=b)ddelettebb;b = new way220;i = 0;end = 2;counnt = 0;for (sizze_t i = 0; ii 220; ii+)vissiteddi = 0;Romannia_TTrip:Roomaniia_Trrip()if (NULLL != b)deeleteeb;void Romaania_Tripp:

49、Viisit(int v, intt u)bi.fatther = u;bi.me = v;i +;void Romaania_Tripp:Prrint(Grapph &graaph, way *b, intt end, int starrt)int Bwayy = 00;vecttor CityyNamee;striing nname = grraph.Vennd.ccitynname;CityyNamee.pussh_baack(nname);whille (11)forr (intt j = 0; ji; j+)iff (bj.me = ennd)nname = grraph.Vbj.f

50、athher.cityynamee;CCityNName.pushh_bacck(naame);BBway += ggraphh.edggebj.mebj.fathher;eend = bj.fathher;if (endd = starrt)breaak;coutt 0; i)couut CittyNammei ;coutt Buchharesst enddl;coutt 路径长度度为： BBway eendl 访访问节点数数为： ccountt Leevel)retuurn;/大于于搜索层次次时不再深深入leveel+;visiitedv = 1;/访问该节节点counnt+;stacck

51、.SttackPPush(v, graaph);if (v = end | sstackk.GettWeigght() = MaxWWeighht)w = -1;if (v = end&staack.GGetWeeightt() = MaaxWeiight)coout sttack.GetWWeighht()MMaxWeeightt = sstackk.GettWeigght();*/coout 路径径长度为： staack.GGetWeeightt() enndl 访问问节点数为为： coount eendl搜索层层次：levvelendll;issOK = truue;elseew = g

52、raaph.GGetFiirstVVerteex(v);/取取当前节点点的第一个个子节点whille (ww != -1)if (!viisiteedw)DeepthFFirsttSearrch(ggraphh, w, staack);/递归归访问w = graaph.GGetNeextVeertexx(v, w);/取取当前节点点的下一个个子节点visiitedv = 0;/返回时置置该节点为为未访问stacck.SttackPPop( grapph);/将将该节点弹弹出栈，并并根据grraph 中weiight 的值更改改当前栈值值leveel-;/贪婪算算法void Romaania_T

53、ripp:Grreedyy_Alggoritthms(Grapph &graaph, int v)int u, ww;SeqCCQuenne quueue;/队列列存储图节节点在图中中的索引值值,优先队队列，vaalue小小的在队头头visiitedv = 1;if (v = end) reeturnn; queuue.QuueueOOrderrAppeend( v, graaph);/图节节点按优先先顺序入队队列counnt+; /访访问节点数数+1whille (qqueuee.QueeueNootEmppty()/宽宽度优先，循循环queeue.QQueueeDeleete( &u);/

54、删除除队列头元元素并返回回删除的数数值/ccout u= u ;w = graaph.GGetFiirstVVerteex(u);whiile (w != -1)iff (!vvisittedww)VVisitt(w, u);/访问ww节点，将将way b 的指指向更新iif (ww = end) /coout ww=ennd;counnt+; retuurn; qqueuee.QueeueOrrderAAppennd( ww, grraph); /图节点按按优先顺序序入队列ccountt+;w = grraph.GetNNextVVerteex(u, w);/A*算算法void Romaan

55、ia_Tripp:ASStar_Algoorithhms(GGraphh &graaph, int v)/i = 0; couunt = 0;int u, ww;SeqCCQuenne quueue;if (v = end) retturn;/到达达终点queuue.Quueue_A_OrrderAAppennd(v, graaph); counnt+;whille (qqueuee.QueeueNootEmppty()queeue.QQueueeDeleete( &u);if (u = ennd)coout 路径径长度为： graaph.GGetVeerCosst(u) + ggraphh.

56、GettVerVValuee(u) eendl 访问问节点数为为： coount eendl;reeturnn;w = graaph.GGetFiirstVVerteex( uu);whiile (w != -1)innt coost=ggraphh.GettVerCCost(u) + graaph.GGetEddge(ww,u);grraph.SetVVerCoost(ww, coost);/设置置当前节点点移动到目目标节点的的预估费用用quueue.Queuue_A_OrdeerApppend( w, grapph);/按按预估费用用优先入队队列 coount+;w = grraph.Ge

57、tNNextVVerteex(u, w);int RRomannia_TTrip:GettCounnt()retuurn ccountt;int RRomannia_TTrip:GettMaxWWeighht()retuurn MMaxWeeightt;int RRomannia_TTrip:GettEnd()retuurn eend;way *Romaania_Tripp:GeetB()retuurn bb;/Souurce.cpp/*On holiiday in RRomannia; currrentlly inn AraadFlighht leeavess tommorroow frrom BBuchaaresttFormuulatee goaal：Bee in BuchharesstFormuulatee prooblemmStatees: vvarioous ccitieesActioons: drivve beetweeen ciitiessFind soluutionnSequeence of ccitiees; ee.g. Aradd, Siibiu, Faggarass,Buchaarestt,*/#inclludeGrapph.h#inclludeQueuue.h#inclludeStacck.h#inclludeRomaania_Tripp.h#in