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

人工智能课程设计

报告-罗马尼亚度假

问题2020年5月29日2020年5月29日文档仅供参考课程:人工智能课程设计报告班级：姓名：学号：指导教师:赵曼11月2020年5月29日文档仅供参考人工智能课程设计报告课程背景人工智能（ArtificialIntelligence）,英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，能够设想,未来人工智能带来的科技产品,将会是人类智慧的“容器”。人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识,心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些一般需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种”复杂工作”的理解是不同的。人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐2020年5月29日文档仅供参考步成为一个独立的分支，无论在理论和实践上都已自成一个系统。人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。能够说几乎是自然科学和社会科学的所有学科,其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不但限于逻辑思维,要考虑形象思维、灵感思维才能促进人工智能的突破性的发展,数学常被认为是多种学科的基础科学,数学也进入语言、思维领域，人工智能学科也必须借用数学工具,数学不但在标准逻辑、模糊数学等范围发挥作用,数学进入人工智能学科，它们将互相促进而更快地发展。题目一:罗马利亚度假问题一.问题描述分别用代价一致的宽度优先、有限制的深度优先（预设搜索层次）、贪婪算法-2-2020年5月29日文档仅供参考和人算法求解”罗马利亚度假问题”。即找到从初始地点Arad到目的地点Bucharest的一条路径。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。数据如下:1、地图2、启发函数值Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Doberta242Pitesti100Eforie161Rimmicu_Vikea193Fagaras176Sibiu253Glurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind3742020年5月29日文档仅供参考3、地图数据表010001000100010001000100010001000100010001401000118100010001000100010007510000100010001000100075100010001000100010001000100010001000100010007010001000100001000100010001000101100010002111000901000100085100010001000100010001000100001000100010001000100010001000100010001000100010008710001000100010001000100010000100012013810001461000100010001000100010001000100010001000100010001000100010000100010001000100010001511000100010001000100010001000711000751000100012010000100010001000100010001000100010001000100010001000100010001000101100013810001000010009710001000100010001000100010001000100010001000100010001000100010001000100001000100010001000100086100010001000100010002020年5月29日文档仅供参考1000100010001000146100010009710000100080100010001000100010001000100010001000100021110001000100010001000100010000991000100010001000100010001000100014010001000100010001511000100010008099010001000100010001000100010001000100010009010001000100010001000100010001000100001000100010001000100010001000118100010001000100010001000100010001000100010001000010001000100010001111000100010001000100010001000100010008610001000100010001000098100010001000100010001000851000100010001000100010001000100010001000100098010001000100010001000100010008710001000100010001000100010001000100010001000100009210001000100010001000100010001000100010001000100010001000100010001000100092010001000100070100010001000100010001000100010001000100010001111000100010001000010002020年5月29日文档仅供参考7510001000100010007110001000100010001000100010001000100010001000100010000二.设计分析1.算法分析1）宽度优先搜索算法广度优先搜索使用队列9起起）来实现1、把根节点放到队列的末尾。2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素杷它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。3、找到所要找的元素时结束程序。4、如果遍历整个图还没有找到，结束程序。2）深度优先搜索算法深度优先搜索用栈（stack）来实现，整个过程能够想象成一个倒立的树形：1、把根节点压入栈中。2、每次从栈中弹出一个元素，搜索所有在它下一级的元素杷这些元素压入栈中。并把这个元素记为它下一级元素的前驱。3、找到所要找的元素时结束程序。2020年5月29日文档仅供参考4、如果遍历整个树还没有找到，结束程序。3)贪婪算法.建立数学模型来描述问题.把求解的问题分成若干个子问题。.对每一子问题求解稿到子问题的局部最优解。.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。4)A*算法A*[1](A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。公式表示为:f(n)=g(n)+h(n),其中f(n)是从初始点经由节点n到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件，关键在于估价函数f(n)的选取：2020年5月29日文档仅供参考估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多,搜索范围大,效率低。但能得到最优解。而且如果h(n)=d(n),即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行,此时的搜索效率是最高的。如果估价值>实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。2.数据结构1)图结构：抽象图结构的实现：typedefstruct〃图节点类型(charcityname[20];intvalue;2020年5月29日文档仅供参考intcost;}Ver;classGraph〃图结构(public:Graph();〜Graph();VerV[MaxV];intedge[MaxV][MaxV];intnumofedges;〃注意这个变量的引用位置〃读取地图节点信息voidReadVertex();〃读取地图边关系信息voidReadEdge();〃取与第丫个节点的第一个邻接点intGetFirstVertex(intv);〃找到第丫1个节点的V2之后的下一个邻接节点intGetNextVertex(intv1,intv2);intGetVerValue(intindex);〃获取V[index]的ver的value值intGetVerCost(intindex);〃获取V[index]的ver的cost值2020年5月29日

文档仅供参考intGetEdge(introw,intcol);〃获取edge[row][col]的值voidSetVerCost(intindex,intcost);classSeqQueue(public:SeqQueue();〜SeqQueue();voidQueueInitiate();intQueueNotEmpty();-10-2020年5月29日文档仅供参考intQueueAppend(intx);intQueueDelete(int*d);intQueueOrderAppend(intx,Graph&G);/伏*算法使用intQueue_A_OrderAppend(intx,Graph&G);private:intqueue[MaxSize];intrear;intfront;Push深度优先算法使用;3）栈结构intcount;);Push深度优先算法使用;3）栈结构intcount;);2020年5月29日-11-文档仅供参考栈结构的抽象类型实现:classStack(public:Stack();~Stack();boolStackNotFull();boolStakNotEmpty();voidStackPop(Graph&G);voidStackPush(intx,Graph&G);voidPrintStack(Graph&G);intGetWeight();private:inta[100];inttopi;intweight;三i-12-2020年5月29日文档仅供参考1)宽度优先搜索算法〃宽度优先算法voidRomania_Trip::BroadFirstSearch(Graph&graph,intv)(intu,w;i=0;SeqCQuenequeue;visited[v]=1;//访问节点count++;if(v==end)return;queue.QueueAppend(丫);//入队列while(queue.QueueNotEmpty())//队列非空(queue.QueueDelete(&u);//取队列节点w=graph.GetFirstVertex(u);while(w!=-1)〃有子节点的话(if(!visited[w])//如果子节点未被访问，则访问子节点(Visit(w,u);visited[w]=1;-13-2020年5月29日文档仅供参考count++;if(w==end)//找到结果Print(graph,b,end,v);return;queue.QueueAppend(w);〃节点压入队列w=graph.GetNextVertex(u,w);2）深度优先搜索算法〃深度优先算法boolisOK=false;intlevel=0;constintLevel=8;//预设的搜索层次voidRomania_Trip::DepthFirstSearch(Graph&graph,int、，Stack&stack)intw;i=0;-14-2020年5月29日文档仅供参考if(isOK==true)return;if(level+1>匕6丫61)阳可口;//大于搜索层次时不再深入1eve1++;visited[v]=1；//访问该节点count++;stack.StackPush(v,graph);if(v==end||stack.GetWeight()>=MaxWeight)(w=-1;if(v==end&&stack.GetWeight()<=MaxWeight)(cout<<"---深度优先遍历路径为:“；stack.PrintStack(graph);/*if(MaxWeight>stack.GetWeight())MaxWeight=stack.GetWeight();*/cout<<"---路径长度为:"<<stack.GetWeight()<<endl<<"---访问节点数为:"<<count<<endl<<"---搜索层次:"<<level<<endl;isOK=true;)-15-2020年5月29日文档仅供参考)else(w=graph.GetFirstVertex(v);//取当前节点的第一个子节点)while(w!=-1)(if(!visited[w])DepthFirstSearch(graph,w,stack);//递归访问w=graph.GetNextVertex(v,w);//取当前节点的下一个子节点)visited[v]=0;〃返回时置该节点为未访问stack.StackPop(graph);//)E该节点弹出栈，并根据且为卜中亚618批的值更改当前栈值level--;3)贪婪算法〃贪婪算法voidRomania_Trip::Greedy_Algorithms(Graph&graph,intv)(-16-2020年5月29日文档仅供参考intu,w;SeqCQuenequeueJ/队列存储图节点在图中的索引值，优先队列川用其小的在队头visited[v]=1;if(v==end){return;}queue.QueueOrderAppend(v,graph);//图节点按优先顺序入队列count++;〃访问节点数+1while(queue.QueueNotEmpty())//宽度优先彳循环queue.QueueDelete(&u);//删除队列头元素并返回删除的数值//cout<<"u="<<u<<"";w=graph.GetFirstVertex(u);while(w!=-1)if(!visited[w])Visit(w,u);//访问w节点,)^wayb的指向更新if(w==end)-17-2020年5月29日文档仅供参考//cout<<"w==end";count++;return;queue.QueueOrderAppend(w,graph);//图节点按优先顺序入队列count++;w=graph.GetNextVertex(u,w);}4)A*算法//A*算法voidRomaniaTrip::AStar_Algorithms(Graph&graph,intvvoidRomania//i=0;count=0;intu,w;SeqCQuenequeue;if(v==end)return;〃到达终点queue.Queue_A_OrderAppend(,graph);-18-2020年5月29日文档仅供参考count++;while(queue.QueueNotEmpty())(queue.QueueDelete(&u);if(u==end)(cout<<"---路径长度为:"<<graph.GetVerCost(u)+graph.GetVerValue(u)<<endl<<"---访问节点数为:"<<count<<endl;return;)w=graph.GetFirstVertex(u);while(w!=-1)(intcost二graph.GetVerCost(u)+graph.GetEdge(w,u);graph.SetVerCost(w,cost);//设置当前节点移动到目标节点的预估费用queue.Queue_A_OrderAppend(w,graph);//按预估费用优先入队列count++;-19-2020年5月29日文档仅供参考w=graph.GetNextVertex(u,w);)))四.运行结果及分析-20-2020年5月29日

文档仅供参考C:\windows\system32\cmd.exe 7: . 遍历路径为：Arad->Sibiu->Fagaras->Bucharest 匹径长度为；450——独向书春薮为；11 耗Itnc第HJ-,鼠刁第HJ-,鼠刁s阳空数n辛先度点31法机S2

尼有51E:p1n-T星算法■-T星算法■揩飙3J5041S:16请按任意键维续一一一”狗疾音输入法全，分析:节点数路径长度耗时msOptimalitv:Completeness:BFS1145016NoYESDFS1260531NoNOGreedy845016NONOA*算法164180YESYES-21-2020年5月29日文档仅供参考经过比较,Greedy搜索生成的结点数目最少，为8个，效率最高;八*算法生成的结点数目最多,为30个，效率最低。DFS（一般）、BFS和Greedy搜索找到的都不一定最优解,八*算法具有完备性且始终找到的是最优解。宽度优先虽然是完备的（如果分支因子有限的话），在任何情况下宽度优先都能找到一个解，可是，它找到的第一个解并非最优的，另外,最坏的情况是，当目标结点是第d层的最后一个被扩展的结点时，它将耗费大量的时间。宽度优先时间复杂度:2人一--'一"厂J（b为分支因子4为深度）;空间复杂度为所存储的节点的个数。DFS不是完备的（除非查找空间是有限的），同时，它也不能找到最优解。深度优先的时间复杂度。"।；空间复杂度:。Wb为分支因子,m为深度，仅有一枝需要存储）;。贪婪算法不是完备的。同时，它找到的解也不一定是最优解。其时间复杂度。:「（b代表分支数,m为深度）;空间复杂度为1"」）。因此只有A嶂法和DFS（回溯+剪枝）是完备的且能够找到最优解;其时间复杂度:扩展节点的数目;空间复杂度:所有生成的结点。综合来看,BFS和贪婪算法的效率较高，但解并非最优而八*算法的效率稍逊色，但解为最优;DFS（回溯+剪枝）搜索虽能找到最优解但效率最低。-22-2020年5月29日文档仅供参考源代码//Graph.h#pragmaonceusingnamespacestd;#defineMaxV20/*#ifndefMY_DEBUG#defineMY_DEBUG#endif*/typedefstruct(charcityname[20];//城市名-23-2020年5月29日文档仅供参考intvalue;〃权值int8凌;/伏*算法中从当前节点移动到目标节点的预估费用}Ver;classGraph(public:Graph();〜Graph();VerV[MaxV];intedge[MaxV][MaxV];intnumofedges;〃注意这个变量的引用位置〃读取地图节点信息voidReadVertex();〃读取地图边关系信息voidReadEdge();〃取与第丫个节点的第一个邻接点intGetFirstVertex(intv);〃找到第丫1个节点的V2之后的下一个邻接节点intGetNextVertex(intv1,intv2);-24-2020年5月29日文档仅供参考intGetVerValue(intindex);〃获取V[index]的ver的value值intGetVerCost(intindex);〃获取V[index]的ver的cost值intGetEdge(introw,intcol);〃获取edge[row][col]的值voidSetVerCost(intindex,intcost);private:);//Queue.h#pragmaonce#include<iostream>#include"Stack.h"#defineMaxSize30/*#ifndefMY_DEBUG#defineMY_DEBUG#endif/*/classSeqQueue(public:SeqQueue();-25-2020年5月29日文档仅供参考〜SeqQueue();voidQueueInitiate();intQueueNotEmpty();intQueueAppend(intx);intQueueDelete(int*d);intQueueOrderAppend(intx,Graph&G);/伏*算法使用intQueue_A_OrderAppend(intx,Graph&G);private:intqueue[MaxSize];intrear;intfront;intcount;);typedefSeqQueueSeqCQuene;//Romania_Trip.h#pragmaonce#include"Queue.h-26-2020年5月29日文档仅供参考typedefstruct(intfather;intme;}way;classRomania_Trip(public:Romania_Trip();~Romania_Trip();voidVisit(intv,intu);voidPrint(Graph&graph,way*b,intend,intstart);voidBroadFirstSearch(Graph&graph,intv);voidDepthFirstSearch(Graph&graph,intv,Stack&stack);voidGreedy_Algorithms(Graph&graph,intv);voidAStar_Algorithms(Graph&graph,intv);voidReSet();-27-2020年5月29日文档仅供参考intGetCount();intGetMaxWeight();intGetEnd();way*GetB();private:way*b;inti;intend;intcount;intvisitedCity[20];intMaxWeight;intvisited[20];);//Stack.h#pragmaonce#include"Graph.h"#include<iostream>usingnamespacestd;/*#ifndefMY_DEBUG#defineMY_DEBUG-28-2020年5月29日文档仅供参考#endif*/classStack(public:Stack();~Stack();boolStackNotFull();boolStakNotEmpty();voidStackPop(Graph&G);voidStackPush(intx,Graph&G);voidPrintStack(Graph&G);intGetWeight();private:inta[100];inttopi;intweight;);//Graph.cpp#include"Graph.h"#include<iostream>-29-2020年5月29日文档仅供参考#include<stdlib.h>#include<fstream>#include<string>usingnamespacestd;Graph::Graph()(numofedges=0;)Graph::〜Graph()()voidGraph::ReadVertex()(inti=0,v;charch[20];fstreaminfile("启发式数值.txt",ios::in);while(infile>>ch&&infile>>v)(#ifdefMY_DEBUG-30-2020年5月29日文档仅供参考printf("%s\t%d\n",ch,v);#endifV[i].value=v;V[i].cost=0;strcpy(V[i].cityname,ch);i++;))voidGraph::ReadEdge()(intvalu,i;fstream♦—.("地图数据表取犬,ios::in);i=0;while(infile>>valu)(edge[i/20][i%20]=valu;#ifdefMY_DEBUGif(i%20==0)cout<<endl;cout<<edge[i/20][i%20]<<"\t";#endif-31-2020年5月29日文档仅供参考i++；))〃取与第丫个节点的第一个邻接点intGraph::GetFirstVertex(intv)(if(v<0IIv>=20)(return-1;)for(intcol=0;col<20;col++)if(edge[v][col]>0&&edge[v][col]<1000)returncol;return-1;)//找到第丫1个节点的V2之后的下一个邻接节点intGraph::GetNextVertex(intv1,intv2)(-32-2020年5月29日文档仅供参考if(v1<0IIv1>=20IIv2<0IIv2>=20)(return-1;)for(intcol=v2+1;col<20;col++)if(edge[v1][col]>0&&edge[v1][col]<1000)returncol;return-1;)intGraph::GetVerValue(intindex)〃获取V[index]的ver的values值(returnV[index].value;)intGraph::GetVerCost(intindex)〃获取V[index]的ver的cost值(returnV[index].cost;)intGraph::GetEdge(introw,intcol)〃获取edge[row][col]的值(-33-2020年5月29日文档仅供参考returnedge[row][col];)voidGraph::SetVerCost(intindex,intcost){V[index].cost=cost;)//Queue.cpp#include"Queue.h"#include<iostream>#include"Stack.h"SeqQueue::SeqQueue(){rear=0;front=0;count=0;)SeqQueue::〜SeqQueue()-34-2020年5月29日文档仅供参考()intSeqQueue::QueueNotEmpty()(if(count!=0)return1;elsereturn0;)intSeqQueue::QueueAppend(intx)(if(count>0&&rear==front)(cout<<"队列已满"<<endl;return0;)else(queue[rear]=x;rear=(rear+1)%MaxSize;count++;return1;-35-2020年5月29日文档仅供参考intSeqQueue::QueueDelete(int*d)if(count==0)cout<<"队列已空"<<endl;return0;else*d=queue[front];front=(front+1)%MaxSize;count--;return1;intSeqQueue::QueueOrderAppend(intx,Graph&G)if(count>0&&rear==front)-36-2020年5月29日文档仅供参考(cout<<"队列已满"<<endl;return0;)else(if(count==0IIG.V[x].value>=G.V[queue[rear-1]].value)〃队尾插入(queue[rear]=x;rear=(rear+1)%MaxSize;count++;return1;)else(if(G.V[x].value<=G.V[queue[front]].value)//队头插入(queue[front-1]=x;front=(front-1+MaxSize)%MaxSize;count++;-37-2020年5月29日文档仅供参考return1;else〃排序找位置插入intposition=front;while(G.V[x].value>G.V[queue[position]].value)position++;queue[i%MaxSize];inti;for(i=front;i<position;i++)queue[(i-1+MaxSize)%MaxSize]=)queue[(i-1+MaxSize)%MaxSize]=x;front=(front-1+MaxSize)%MaxSize;count++;return1;-38-2020年5月29日文档仅供参考return0;//A*intSeqQueue::Queue_A_OrderAppend(intx,Graph&G)if(count>0&&rear==front)cout<<"队列已满"<<endl;return0;elseintx1=G.V[x].value+G.V[x].cost;intx2=0;1]].cost;if(count!=0)x2=G.V[queue[rear-1]].value+G.V[queue[rear1]].cost;if(count==0||x1>x2)〃队尾插入-39-39-2020年5月29日文档仅供参考queue[rear]=x;rear=(rear+1)%MaxSize;count++;return1;else〃队头插入if(G.V[x].value+G.V[x].cost<G.V[queue[front]].value+G.V[queue[front]].cost)queue[front-1]=x;front=(front-1+MaxSize)%MaxSize;count++;return1;)else〃排序找位置插入(intposition=front;while(G.V[x].value+G.V[x].cost>-40-2020年5月29日文档仅供参考G.V[queue[position%MaxSize]].value+G.V[queue[position%MaxSize]].cost)position++;inti;for(i=front;i<position;i++)queue[(i-1+MaxSize)%MaxSize]=queue[i%MaxSize];queue[(i-1+MaxSize)%MaxSize]=x;front=(front-1+MaxSize)%MaxSize;count++;return1;)))return0;)-41-2020年5月29日文档仅供参考/Romania_Trip.cpp#include"Romania_Trip.h"#include<iostream>#include<vector>#include<string>usingnamespacestd;Romania_Trip::Romania_Trip()(b=newway[100];i=0;end=2;count=0;MaxWeight=10000;for(size_ti=0;i<20;i++)(visited[i]=0;)-42-2020年5月29日文档仅供参考voidRomania_Trip::ReSet()(if(NULL!=b)delete[]b;b=newway[20];i=0;end=2;count=0;for(size_ti=0;i<20;i++)(visited[i]=0;))Romania_Trip::~Romania_Trip()(if(NULL!=b)delete[]b;)voidRomania_Trip::Visit(intv,intu)(b[i].father=u;b[i].me=v;-43-2020年5月29日文档仅供参考i++；)voidRomania_Trip::Print(Graph&graph,way*b,intend,intstart)(intBway=0;vector<string>CityName;stringname=graph.V[end].cityname;CityName.push_back(name);while(1){for(intj=0;j<i;j++)if(b[j].me==end)name=graph.V[b[j].father].cityname;CityName.push_back(name);Bway+=graph.edge[b[j].me][b[j].father];end=b[j].father;-44-2020年5月29日文档仅供参考if(end==start)break;)cout<<"---遍历路径为：for(size_ti=CityName.size()-1;i>0;i--)(cout<<CityName[i]<<"->";)cout<<"Bucharest”<<endl;cout<<"---路径长度为:"<<Bway<<endl<<"---访问节点数为:"<<count<<endl;)〃宽度优先算法voidRomania_Trip::BroadFirstSearch(Graph&graph,intv)(intu,w;i=0;SeqCQuenequeue;visited[v]=1;count++;if(v==end)return;queue.QueueAppend(v);-45-2020年5月29日文档仅供参考while(queue.QueueNotEmptyOV/队列非空4皿皿©皿皿口61616（&口）；//取队列节点w=graph.GetFirstVertex(u);while(w!=-1)〃有子节点的话if(!visited[w])Visit(w,u);visited[w]=1;count++;if(w==end)Print(graph,b,end,v);return;queue.QueueAppend(w);〃节点压入队列w=graph.GetNextVertex(u,w);-46-2020年5月29日文档仅供参考))〃深度优先算法boolisOK=false;intlevel=0;constintLevel=8;//预设的搜索层次voidRomania_Trip::DepthFirstSearch(Graph&graph,intv,Stack&stack)(intw;i=0;if(isOK==true)return;if(level+1>Level)return;//大于搜索层次时不再深入level++;visited[v]=1;〃访问该节点count++;stack.StackPush(v,graph);if(v==end||stack.GetWeight()>=MaxWeight)(w=-1;if(v==end&&stack.GetWeight()<=MaxWeight)-47-2020年5月29日文档仅供参考cout<<"---深度优先遍历路径为:“；stack.PrintStack(graph);/*if(MaxWeight>stack.GetWeight())MaxWeight=stack.GetWeight();*/cout<<"---路径长度为:"<<stack.GetWeight()<<endl<<"---访问节点数为:"<<count<<endl<<"---搜索层次:"<<level<<endl;isOK=true;))else(w=graph.GetFirstVertex(v);//取当前节点的第一个子节点)while(w!=-1)(if(!visited[w])DepthFirstSearch(graph,w,stack);//递归访问w=graph.GetNextVertex(v,w);//取当前节点的下一个子节点-48-2020年5月29日文档仅供参考)visited[v]=0；〃返回时置该节点为未访问stack.StackPop(graph);//)E该节点弹出栈，并根据且为卜中亚618批的值更改当前栈值level--;)〃贪婪算法voidRomania_Trip::Greedy_Algorithms(Graph&graph,intv)(intu,w;SeqCQuenequeueJ/队列存储图节点在图中的索引值，优先队列川用其小的在队头visited[v]=1;if(v==end){return;}queue.QueueOrderAppend(v,graph);//图节点按优先顺序入队列count++; 〃访问节点数+1while(queue.QueueNotEmpty())//宽度优先彳循环{queue.QueueDelete(&u);//删除队列头元素并返回删除的数值//cout<<"u="<<u<<"";-49-2020年5月29日文档仅供参考w=graph.GetFirstVertex(u);while(w!=-1)(if(!visited[w])(Visit(w,u);//访问w节点,)^wayb的指向更新if(w==end)(//cout<<"w==end";count++;return;)queue.QueueOrderAppend(w,graph);//图节点按优先顺序入队列count++;)w=graph.GetNextVertex(u,w);))-50-2020年5月29日文档仅供参考)//A*算法voidRomania_Trip::AStar_Algorithms(Graph&graph,intv)(//i=0;count=0;intu,w;SeqCQuenequeue;if(v==end)return;〃到达终点queue.Queue_A_OrderAppend(,graph);count++;while(queue.QueueNotEmpty())queue.QueueDelete(&u);if(u==end)cout<<"---路径长度为:"<<graph.GetVerCost(u)+graph.GetVerValue(u)<<endl<<"---访问节点数为:"<<count<<endl;return;-51-2020年5月29日文档仅供参考w=graph.GetFirstVertex(u);while(w!=-1)(intcost二graph.GetVerCost(u)+graph.GetEdge(w,u);graph.SetVerCost(w,cost);//设置当前节点移动到目标节点的预估费用queue.Queue_A_OrderAppend(w,graph);//按预估费用优先入队列count++;w=graph.GetNextVertex(u,w);)))intRomania_Trip::GetCount()(returncount;)intRomania_Trip::GetMaxWeight()(-52-2020年5月29日文档仅供参考returnMaxWeight;)intRomania_Trip::GetEnd()(returnend;)way*Romania_Trip::GetB()(returnb;)//Source.cpp/*OnholidayinRomania;currentlyinAradFlightleavestomorrowfromBucharestFormulategoal:BeinBucharestFormulateproblemStates:variouscitiesActions:drivebetweencities-53-2020年5月29日

文档仅供参考FindsolutionSequenceofcities;e.g.Arad,Sibiu,Fagaras,Bucharest,*/#include"Graph.h"#include"Queue.h"#include"Stack.h"#include"Romania_Trip.h"#include<iostream>#include<ctime>usingnamespacestd;intmain()(longinttime1,time2;"<<endl;co