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

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

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

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

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

5、用，数学进入入人工智能学学科，它们将将互相促进而而更快地发展展。题目一：罗马利利亚度假问题题一. 问题描述述分别用代价一致致的宽度优先先、有限制的的深度优先（预预设搜索层次次）、贪婪算算法和A*算法求解“罗马利亚度度假问题”。即找到从初初始地点 AArad到 目的地点 Buchaarest 的一条路径径。要求：分别用文件存储储地图和启发发函数表，用用生成节点数数比较几种算算法在问题求求解时的效率率，并列表给出结结果。数据如下：1、地图2、启发函数值值Arad 3666 Mehaddia 2441 Buchaarest 0 Neamtt 234 Craioova 1660 Oradeea 380

6、0 Doberrta 2442Pitestii 100 Eforiie 1611 Rimmiicu_Viikea 1193 Fagarras 1776 Sibiuu 253 Glurggiu 777Timisoaara 3229 Hirsoova 1551 Urzicceni 880 Iasi 226 Vasluui 1999 Lugojj 244 Zerinnd 37443、地图数据表表0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 1440 1000 118 10000 10000 10000 10000 1000

7、0 751000 0 10000 10000 10000 10000 75 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 70 100001000 10000 0 10000 10000 10000 10000 1011 10000 10000 211 10000 90 10000 10000 85 10000 10000 10000 100001000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 1000

8、0 10000 87 10000 10000 100001000 10000 10000 10000 0 10000 1200 138 1000 146 10000 10000 10000 10000 10000 10000 10000 10000 10000 100001000 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 1511 10000 10000 10000 10000 10000 10000 10000 711000 755 10000 10000 120 1000 0 1000 1000 1000 1000 10

9、00 1000 1000 1000 1000 1000 1000 1000 10001000 10000 1001 1000 138 1000 1000 0 1000 97 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 10000 10000 10000 10000 10000 10000 10000 0 10000 10000 10000 10000 10000 866 10000 10000 10000 10000 100001000 10000 10000 10000 1446 1000 1000 97 1000 0 1000

10、 80 10000 10000 10000 10000 10000 10000 10000 100001000 10000 2111 1000 1000 1000 1000 1000 1000 1000 0 999 10000 10000 10000 10000 10000 10000 10000 10000140 10000 10000 10000 10000 1551 1000 1000 1000 80 99 0 1000 1000 1000 1000 1000 1000 1000 10001000 10000 900 10000 10000 10000 10000 10000 10000

11、 10000 10000 10000 0 10000 10000 10000 10000 10000 10000 10000118 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 0 10000 10000 10000 10000 1111 10001000 10000 10000 10000 10000 10000 10000 10000 866 10000 10000 10000 10000 10000 0 98 10000 10000 10000 100001000 10000 855 100

12、00 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 98 0 10000 10000 10000 100001000 10000 10000 877 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 0 92 10000 100001000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 922 0

13、 10000 100001000 700 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 111 1000 1000 1000 1000 0 100075 10000 10000 10000 10000 711 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 0二.设计分析1.算法分析 1) 宽宽度优先搜索索算法广度优先搜索使使用队列（qqueue）来来实现1、把根节点放放到队列的末末尾。2、每次从队列列

14、的头部取出出一个元素，查查看这个元素素所有的下一一级元素，把把它们放到队队列的末尾。并并把这个元素素记为它下一一级元素的前前驱。3、找到所要找找的元素时结结束程序。4、如果遍历整整个图还没有找到到，结束程序序。2)深度优先搜搜索算法深度优先搜索用用栈（staack）来实实现，整个过过程可以想象象成一个倒立立的树形：1、把根节点压压入栈中。2、每次从栈中中弹出一个元元素，搜索所所有在它下一一级的元素，把把这些元素压压入栈中。并并把这个元素素记为它下一一级元素的前前驱。3、找到所要找找的元素时结结束程序。4、如果遍历整整个树还没有有找到，结束束程序。3)贪婪算法1.建立数学模模型来描述问问题把求解

15、的问题题分成若干个个子问题。对每一子问题题求解，得到到子问题的局局部最优解。把子问题的解解局部最优解解合成原来解解问题的一个个解。实现该算法的过过程：从问题的某一初初始解出发；while 能能朝给定总目目标前进一步步do求出可行解的一一个解元素；由所有解元素组组合成问题的的一个可行解解。4)A*算法A*1 （A-Sttar)算法法是一种静态态路网中求解解最短路最有有效的直接搜搜索方法。公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始始点经由节点点n到目标点点的估价函数数，g(n) 是在在状态空间中中从初始节点点到n节点的的实际代价，h(n) 是从从n到目标节节点最佳路径径的

16、估计代价价。保证找到最短路路径（最优解解的）条件，关关键在于估价价函数f(nn)的选取：估价值h(n)实际值,搜搜索的点数少少，搜索范围围小，效率高高，但不能保保证得到最优优解。2.数据结构1)图结构： 实现存储“罗罗马尼亚度假假问题”的图空间； 抽象图结构的的实现：typedeff strucct /图节节点类型char ccitynaame200;int vvalue;int ccost;Ver;class GGraph /图结构public:Graph();Graphh(); Verr VMaxxV;int eddgeMaaxVMaxVV;int nuumofeddges; /注意这个变

17、变量的引用位位置/读取地图图节点信息void RReadVeertex();/读取地图图边关系信息息void RReadEddge();/取与第VV个节点的第第一个邻接点点int GeetFirsstVerttex(innt v);/找到第VV1个节点的的V2之后的的下一个邻接接节点int GeetNexttVerteex(intt v1, int v22);int GeetVerVValue(int inndex);/获取VVindeex 的vver 的vvalue值值int GeetVerCCost(iint inndex);/获取VVindeex 的vver 的ccost 值值int G

18、eetEdgee(int roow, innt coll);/获获取edgeerowcol 的值void SSetVerrCost(int inndex,iint coost);2)队列结构宽度优先算法以以及A*算法法 使用到。抽象队列结构实实现：class SSeqQueeuepublic:SeqQueeue();SeqQuueue();void QQueueIInitiaate();int QuueueNootEmptty();int QuueueApppend(int x);int QuueueDeelete(int *dd);int QuueueOrrderApppend(int x,

19、 Grapph &G);/A*算法法使用int Quueue_AA_OrdeerAppeend(innt x, Graphh &G);privatee:int quueueMMaxSizze;int reear;int frront;int coount;3)栈结构深度优先算法使使用；栈结构的抽象类类型实现：class SStackpublic:Stack();Stackk();bool SStackNNotFulll();bool SStakNootEmptty();void SStackPPop(Grraph &G);void SStackPPush(iint x, Grapph &G);

20、void PPrintSStack(Graphh &G);int GeetWeigght();privatee:int a100;int toop1;int weeight;三.算法设计1) 宽度优先先搜索算法/宽度优先算算法void Roomaniaa_Tripp:BrooadFirrstSeaarch(GGraph &grapph, int v)int u, w; ii = 0;SeqCQuuene qqueue;visiteedv = 11;/访问问节点count+;if (v = ennd)retturn;queue.QueueeAppennd( v);/入队队列while (queu

21、ue.QueeueNottEmptyy()/队列非空queuee.QueuueDeleete(&uu);/取取队列节点w = ggraph.GetFiirstVeertex( u);whilee (w != -1) /有子节点点的话if (!visiitedww)/如如果子节点未未被访问，则访问子节节点Vissit(w, u);vissitedw = 1;couunt+;if (w = end)/找到结结果Prrint(ggraph, b, eend, vv);reeturn;queeue.QuueueApppend(w);/节点压入队队列w = graphh.GetNNextVeertex(

22、u, w);2)深度优先搜搜索算法/深度优先算算法bool issOK = falsee;int levvel = 0;const iint Leevel = 8;/预设的搜索索层次void Roomaniaa_Tripp:DeppthFirrstSeaarch(GGraph &grapph, int v, Stack &stackk)int w; i = 0;if (issOK = truee)returrn;if (leevel+11 Leevel)rreturnn;/大于搜搜索层次时不不再深入level+;visiteedv = 11;/访问问该节点count+;stack.Stackk

23、Push(v, grapph);if (v = ennd | stackk.GetWWeightt() = MaxWWeightt)w = -1;if (vv = eend&sstack.GetWeeight() = MaxWeeight)coutt staack.GeetWeigght()MaxxWeighht = sstack.GetWeeight();*/coutt 路径径长度为： sttack.GGetWeiight() eendl 访访问节点数为为： counnt endl搜索索层次：leveelenndl;isOKK = trrue;elsew = ggraph.GetFiirst

24、Veertex(v);/取当当前节点的第第一个子节点点while (w != -1)if (!visittedw)DeptthFirsstSearrch(grraph, w, sttack);/递归访访问w = ggraph.GetNeextVerrtex(vv, w);/取当前前节点的下一一个子节点visiteedv = 00;/返回回时置该节点点为未访问stack.StackkPop( graphh);/将该该节点弹出栈栈，并根据ggraph 中weigght 的值值更改当前栈栈值level;3)贪婪算法/贪婪算法void Roomaniaa_Tripp:Greeedy_AAlgoriit

25、hms(Graphh &grapph, int v)int u, w;SeqCQuuene qqueue;/队列存存储图节点在在图中的索引引值,优先队队列，vallue小的在在队头visiteedv = 11;if (v = ennd) rreturnn; queue.QueueeOrderrAppennd( v, grapph);/图节节点按优先顺顺序入队列count+; /访访问节点数+1while (queuue.QueeueNottEmptyy()/宽度优先，循循环queuee.QueuueDeleete( &u);/删除队列头头元素并返回回删除的数值值/couut u= uu ;w

26、= ggraph.GetFiirstVeertex(u);whilee (w != -1)if (!visiitedww)Vissit(w, u);/访问w节节点，将waay b 的的指向更新if (w = end) /cout ww=endd;coount+; reeturn; queeue.QuueueOrrderApppend( w, ggraph); /图图节点按优先先顺序入队列列couunt+;w = graphh.GetNNextVeertex(u, w);4)A*算法法/A*算法void Roomaniaa_Tripp:ASttar_Allgoritthms(GGraph &gr

27、apph, int v)/i = 0; coount = 0;int u, w;SeqCQuuene qqueue;if (v = ennd) reeturn;/到达终终点queue.Queuee_A_OrrderApppend(v, grapph); count+;while (queuue.QueeueNottEmptyy()queuee.QueuueDeleete( &u);if (uu = eend)coutt 路径径长度为： grraph.GGetVerrCost(u) + graphh.GetVVerVallue(u) eendl 访访问节点数为为： counnt endl;ret

28、uurn;w = ggraph.GetFiirstVeertex( u);whilee (w != -1)int cost=graphh.GetVVerCosst(u) + graaph.GeetEdgee(w,u);grapph.SettVerCoost(w, costt);/设设置当前节点点移动到目标标节点的预估估费用queuue.Queeue_A_OrderrAppennd( w, grapph);/按预预估费用优先先入队列 counnt+;w = graphh.GetNNextVeertex(u, w);四.运行结果及及分析分析：节点数路径长度耗时msOptimallity: Comp

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

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

31、来看看，BFS和和贪婪算法的的效率较高，但但解并非最优优，而A*算算法的效率稍稍逊色，但解解为最优；DDFS（回溯溯+剪枝）搜搜索虽能找到到最优解但效效率最低。源代码/Graphh.h#pragmaa onceusing nnamesppace sstd;#definee MaxV 220 /*#ifnddef MYY_DEBUUG#definee MY_DDEBUG #endif*/typedeff strucctchar ccitynaame200;/城城市名int vvalue;/权值int ccost;/A*算法法中从当前节节点移动到目目标节点的预预估费用Ver;class GGrap

32、hpublic:Graph();Graphh(); Verr VMaxxV;int eddgeMaaxVMaxVV;int nuumofeddges; /注意这个变变量的引用位位置/读取地图图节点信息void RReadVeertex();/读取地图图边关系信息息void RReadEddge();/取与第VV个节点的第第一个邻接点点int GeetFirsstVerttex(innt v);/找到第VV1个节点的的V2之后的的下一个邻接接节点int GeetNexttVerteex(intt v1, int v22);int GeetVerVValue(int inndex);/获取VVin

33、deex 的vver 的vvalue值值int GeetVerCCost(iint inndex);/获取VVindeex 的vver 的ccost 值值int GeetEdgee(int roow, innt coll);/获获取edgeerowcol 的值void SSetVerrCost(int inndex,iint coost);privatee:;/Queuee.h#pragmaa once#includde#includde Stacck.h#definee MaxSiize 300/*#ifnddef MYY_DEBUUG#definee MY_DDEBUG #endif/*/

34、class SSeqQueeuepublic:SeqQueeue();SeqQuueue();void QQueueIInitiaate();int QuueueNootEmptty();int QuueueApppend(int x);int QuueueDeelete(int *dd);int QuueueOrrderApppend(int x, Grapph &G);/A*算法法使用int Quueue_AA_OrdeerAppeend(innt x, Graphh &G);privatee:int quueueMMaxSizze;int reear;int frront;int coo

35、unt;typedeff SeqQuueue SeqCQQuene;/Romannia_Trrip.h#pragmaa once#includde Queuue.htypedeff strucctint faather;int mee;way;class RRomaniia_Triippublic:Romaniia_Triip();Romannia_Trrip();void VVisit(int v, int u);void PPrint(Graphh &graaph, wway *bb, intt end, int sttart);void BBroadFFirstSSearchh(Grap

36、ph &grraph, int v);void DDepthFFirstSSearchh(Grapph &grraph, int v,Stackk &staack);void GGreedyy_Algoorithmms(Graaph &ggraph, int v);void AAStar_Algorrithmss(Grapph &grraph, int v);void RReSet();int GeetCounnt();int GeetMaxWWeightt();int GeetEnd();way* GGetB();privatee:way *bb;int i;int ennd;int coo

37、unt;int viisiteddCity20;int MaaxWeigght;int viisitedd20;/Stackk.h#pragmaa once#includdeGraaph.h#includdeusing nnamesppace sstd;/*#ifnddef MYY_DEBUUG#definee MY_DDEBUG #endif*/class SStackpublic:Stack();Stackk();bool SStackNNotFulll();bool SStakNootEmptty();void SStackPPop(Grraph &G);void SStackPPush

38、(iint x, Grapph &G);void PPrintSStack(Graphh &G);int GeetWeigght();privatee:int a100;int toop1;int weeight;/Graphh.cpp#includdeGraaph.h#includde#includde#includde#includdeusing nnamesppace sstd;Graph:Graphh()numofeedges = 0;Graph:Grapph()void Grraph:ReadVVertexx()int i=0, v;char cch20;fstreaam inffi

39、le(启发式数值值.txt, ios:iin);while (infiile ch & inffile v)#ifdef MY_DEEBUGprinttf(%sst%dn, cch, v);#endifVi.valuee = v;Vi.cost = 0;strcppy(Vii.cittynamee, ch);i+;void Grraph:ReadEEdge()int vaalu, ii;fstreaam inffile(地图数据表表.txt, ios:iin);i = 0;while (infiile valuu)edgei / 220i % 20 = vaalu;#ifdef MY_DEEB

40、UGif (ii % 200 = 00)coutt eendl;coutedgeei/200i%220t;#endifi+;/取与第V个个节点的第一一个邻接点int Graaph:GGetFirrstVerrtex(iint v)if (v= 220)returrn -1;for (iint cool = 00; coll0 & edggevcoll10000)returrn coll;returnn -1;/找到第V11个节点的VV2之后的下下一个邻接节节点int Graaph:GGetNexxtVerttex(innt v1, int v2)if (v11= 20 | v2= 20)ret

41、urrn -1;for (iint cool= v22 + 1; col0 & edggev1cool10000)returrn coll;returnn -1;int Graaph:GGetVerrValuee(int indexx)/获取VVindeex 的vver 的vvaluess值returnn Vinddex.vvalue;int Graaph:GGetVerrCost(int indexx)/获取VVindeex 的vver 的ccost 值值returnn Vinddex.ccost;int Graaph:GGetEdgge(intt row, int col)/获取eedge

42、rrowccol 的的值returnn edgeerowcol;void Grraph:SetVeerCostt(int indexx, int cost)Vindeex.coost = cost;/Queuee.cpp#includdeQueeue.h#includde#includde Stacck.hSeqQueuue:SeeqQueuue()rear = 0;front = 0;count = 0;SeqQueuue:SSeqQueeue()int SeqqQueuee:QueeueNottEmptyy()if (coount != 0)rreturnn 1;else rreturnn

43、 0;int SeqqQueuee:QueeueApppend( int x)if (coount00 & rrear = froont)cout 队队列已满 enndl;returrn 0;elsequeueerearr = xx;rear = (reear + 1) % MaxSiize;countt+;returrn 1;int SeqqQueuee:QueeueDellete( int *d)if (coount = 0)cout 队队列已空 00 & rrear = froont)cout 队队列已满 = G.Vquueuerrear - 1.valuee)/队尾尾插入queuuer

44、eaar = x;rearr = (rrear + 1) % MaxSSize;counnt+;retuurn 1;elseif (G.Vx.vallue G.Vquueueppositiion.valuee)poositioon+;intt i;forr (i = fronnt; i00 & rrear = froont)cout 队队列已满 x2 )/队尾插插入queuuereaar = x;rearr = (rrear + 1) % MaxSSize;counnt+;retuurn 1;else /队头插插入if (G.Vx.vallue + G.Vx.cosst G.Vqueeuepo

45、ositioon%MaxxSize.vallue + G.Vquueueppositiion%MaaxSizee.coost)poositioon+;intt i;forr (i = fronnt; iposittion; i+)quueue(i - 11 + MaaxSizee) % MaaxSizee = qqueuei%MaxxSize;queeue(ii - 1 + MaxxSize) % MaaxSizee = x;froont = (fronnt - 11 + MaaxSizee) % MaaxSizee;couunt+;retturn 11;returnn 0;/Romaniia

46、_Triip.cppp#includdeRommania_Trip.h#includde#includde#includdeusing nnamesppace sstd;Romaniaa_Tripp:Rommania_Trip()b = neew way1000;i = 0;end = 2;count = 0;MaxWeiight = 100000;for (ssize_tt i = 0; i 20; i+)visittedi = 0;void Roomaniaa_Tripp:ReSSet()if(NULLL!=b)deletteb;b = neew way200;i = 0;end = 2;

47、count = 0;for (ssize_tt i = 0; i 20; i+)visittedi = 0;Romaniaa_Tripp:Roomaniaa_Tripp()if (NUULL != b)deeleteb;void Roomaniaa_Tripp:Vissit(innt v, int u)bi.ffatherr = u;bi.mme = vv;i +;void Roomaniaa_Tripp:Priint(Grraph &graphh, way *b, int end, int startt)int Bwway = 0;vectorr CiityNamme;stringg nam

48、ee = grraph.VVend.ccitynaame;CityNaame.puush_baack(naame);while (1)for (int j = 0; ji; j+)if (bj.mme = end)namme = ggraph.Vbj.ffatherr.cittynamee;CittyNamee.pushh_backk(namee);Bwaay += graphh.edgeebj.mmebj.ffatherr;endd = bj.ffatherr;if (eend = starrt)breakk;cout 0; i-)cout CiityNammei ;cout Bucchar

49、esst endl;cout 路径长度度为： Bwaay endl 访问节节点数为： ccount Leevel)rreturnn;/大于搜搜索层次时不不再深入level+;visiteedv = 11;/访问问该节点count+;stack.StackkPush(v, grapph);if (v = ennd | stackk.GetWWeightt() = MaxWWeightt)w = -1;if (vv = eend&sstack.GetWeeight() = MaxWeeight)coutt staack.GeetWeigght()MaxxWeighht = sstack.GetWe

50、eight();*/coutt 路径径长度为： sttack.GGetWeiight() eendl 访访问节点数为为： counnt endl搜索索层次：leveelenndl;isOKK = trrue;elsew = ggraph.GetFiirstVeertex(v);/取当当前节点的第第一个子节点点while (w != -1)if (!visittedw)DeptthFirsstSearrch(grraph, w, sttack);/递归访访问w = ggraph.GetNeextVerrtex(vv, w);/取当前前节点的下一一个子节点visiteedv = 00;/返回回时置

51、该节点点为未访问stack.StackkPop( graphh);/将该该节点弹出栈栈，并根据ggraph 中weigght 的值值更改当前栈栈值level;/贪婪算法void Roomaniaa_Tripp:Greeedy_AAlgoriithms(Graphh &grapph, int v)int u, w;SeqCQuuene qqueue;/队列存存储图节点在在图中的索引引值,优先队队列，vallue小的在在队头visiteedv = 11;if (v = ennd) rreturnn; queue.QueueeOrderrAppennd( v, grapph);/图节节点按优先顺顺序

52、入队列count+; /访访问节点数+1while (queuue.QueeueNottEmptyy()/宽度优先，循循环queuee.QueuueDeleete( &u);/删除队列头头元素并返回回删除的数值值/couut u= uu ;w = ggraph.GetFiirstVeertex(u);whilee (w != -1)if (!visiitedww)Vissit(w, u);/访问w节节点，将waay b 的的指向更新if (w = end) /cout ww=endd;coount+; reeturn; queeue.QuueueOrrderApppend( w, ggraph

53、); /图图节点按优先先顺序入队列列couunt+;w = graphh.GetNNextVeertex(u, w);/A*算法void Roomaniaa_Tripp:ASttar_Allgoritthms(GGraph &grapph, int v)/i = 0; coount = 0;int u, w;SeqCQuuene qqueue;if (v = ennd) reeturn;/到达终终点queue.Queuee_A_OrrderApppend(v, grapph); count+;while (queuue.QueeueNottEmptyy()queuee.QueuueDeleet

54、e( &u);if (uu = eend)coutt 路径径长度为： grraph.GGetVerrCost(u) + graphh.GetVVerVallue(u) eendl 访访问节点数为为： counnt endl;retuurn;w = ggraph.GetFiirstVeertex( u);whilee (w != -1)int cost=graphh.GetVVerCosst(u) + graaph.GeetEdgee(w,u);grapph.SettVerCoost(w, costt);/设设置当前节点点移动到目标标节点的预估估费用queuue.Queeue_A_OrderrA

55、ppennd( w, grapph);/按预预估费用优先先入队列 counnt+;w = graphh.GetNNextVeertex(u, w);int Rommania_Trip:GetCCount()returnn counnt;int Rommania_Trip:GetMMaxWeiight()returnn MaxWWeightt;int Rommania_Trip:GetEEnd()returnn end;way *Roomaniaa_Tripp:GettB()returnn b;/Sourcce.cppp/*On hoolidayy in RRomaniia; cuurrenttly inn AraddFlight leavees tommorroww fromm BuchharesttFormulaate gooal：Bee in BBucharrestFormulaate prroblemmStates: variious ccitiessActionss: driive beetweenn citiiesFind soolutioonSequencce of citiees; e.g. Arrad, SSibiu, Fagaaras,Buchareest,*/#includdeGraaph.h#includdeQueeue.h#includdeStaack.