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

课程:人工智能课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 班级:姓名:学号:指导教师:赵曼2015年11月人工智能课程设计报告课程背景人工智能（ArtificialIntelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。题目一：罗马利亚度假问题一.问题描述分别用代价一致的宽度优先、有限制的深度优先（预设搜索层次）、贪婪算法和A*算法求解“罗马利亚度假问题”。即找到从初始地点Arad到目的地点Bucharest的一条路径。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。数据如下：1、地图2、启发函数值Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Doberta242Pitesti100Eforie161Rimmicu_Vikea193Fagaras176Sibiu253Glurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind3743、地图数据表010001000100010001000100010001000100010001401000118100010001000100010007510000100010001000100075100010001000100010001000100010001000100010007010001000100001000100010001000101100010002111000901000100085100010001000100010001000100001000100010001000100010001000100010001000100010008710001000100010001000100010000100012013810001461000100010001000100010001000100010001000100010001000100010000100010001000100010001511000100010001000100010001000711000751000100012010000100010001000100010001000100010001000100010001000100010001000101100013810001000010009710001000100010001000100010001000100010001000100010001000100010001000100001000100010001000100086100010001000100010001000100010001000146100010009710000100080100010001000100010001000100010001000100021110001000100010001000100010000991000100010001000100010001000100014010001000100010001511000100010008099010001000100010001000100010001000100010009010001000100010001000100010001000100001000100010001000100010001000118100010001000100010001000100010001000100010001000010001000100010001111000100010001000100010001000100010008610001000100010001000098100010001000100010001000851000100010001000100010001000100010001000100098010001000100010001000100010008710001000100010001000100010001000100010001000100009210001000100010001000100010001000100010001000100010001000100010001000100092010001000100070100010001000100010001000100010001000100010001111000100010001000010007510001000100010007110001000100010001000100010001000100010001000100010000二.设计分析1.算法分析1)宽度优先搜索算法广度优先搜索使用队列（queue）来实现1、把根节点放到队列的末尾。2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。3、找到所要找的元素时结束程序。4、如果遍历整个图还没有找到，结束程序。2)深度优先搜索算法深度优先搜索用栈（stack）来实现，整个过程可以想象成一个倒立的树形：1、把根节点压入栈中。2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。3、找到所要找的元素时结束程序。4、如果遍历整个树还没有找到，结束程序。3)贪婪算法1.建立数学模型来描述问题⒉把求解的问题分成若干个子问题。⒊对每一子问题求解，得到子问题的局部最优解。⒋把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；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)的选取：估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行，此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。2.数据结构1)图结构：实现存储“罗马尼亚度假问题”的图空间；抽象图结构的实现：typedefstruct//图节点类型{charcityname[20];intvalue;intcost;}Ver;classGraph//图结构{public:Graph();~Graph();VerV[MaxV];intedge[MaxV][MaxV];intnumofedges;//注意这个变量的引用位置//读取地图节点信息voidReadVertex();//读取地图边关系信息voidReadEdge();//取与第V个节点的第一个邻接点intGetFirstVertex(intv);//找到第V1个节点的V2之后的下一个邻接节点intGetNextVertex(intv1,intv2);intGetVerValue(intindex);//获取V[index]的ver的value值intGetVerCost(intindex);//获取V[index]的ver的cost值intGetEdge(introw,intcol);//获取edge[row][col]的值voidSetVerCost(intindex,intcost);};2)队列结构宽度优先算法以及A*算法使用到。抽象队列结构实现：classSeqQueue{public:SeqQueue();~SeqQueue();voidQueueInitiate();intQueueNotEmpty();intQueueAppend(intx);intQueueDelete(int*d);intQueueOrderAppend(intx,Graph&G);//A*算法使用intQueue_A_OrderAppend(intx,Graph&G);private:intqueue[MaxSize];intrear;intfront;intcount;};3)栈结构深度优先算法使用；栈结构的抽象类型实现：classStack{public:Stack();~Stack();boolStackNotFull();boolStakNotEmpty();voidStackPop(Graph&G);voidStackPush(intx,Graph&G);voidPrintStack(Graph&G);intGetWeight();private:inta[100];inttop1;intweight;};三.算法设计1)宽度优先搜索算法//宽度优先算法voidRomania_Trip::BroadFirstSearch(Graph&graph,intv){intu,w;i=0;SeqCQuenequeue;visited[v]=1;//访问节点count++;if(v==end)return;queue.QueueAppend(v);//入队列while(queue.QueueNotEmpty())//队列非空{queue.QueueDelete(&u);//取队列节点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);}}}2)深度优先搜索算法//深度优先算法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){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);//取当前节点的下一个子节点}visited[v]=0;//返回时置该节点为未访问stack.StackPop(graph);//将该节点弹出栈，并根据graph中weight的值更改当前栈值level--;}3)贪婪算法//贪婪算法voidRomania_Trip::Greedy_Algorithms(Graph&graph,intv){intu,w;SeqCQuenequeue;//队列存储图节点在图中的索引值,优先队列，value小的在队头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){//cout<<"w==end";count++;return;}queue.QueueOrderAppend(w,graph);//图节点按优先顺序入队列count++;}w=graph.GetNextVertex(u,w);}}}4)A*算法//A*算法voidRomania_Trip::AStar_Algorithms(Graph&graph,intv){//i=0;count=0;intu,w;SeqCQuenequeue;if(v==end)return;//到达终点queue.Queue_A_OrderAppend(v,graph);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++;w=graph.GetNextVertex(u,w);}}}四.运行结果及分析分析： 节点数 路径长度 耗时ms Optimality: Completeness: BFS 11 450 16 No YES DFS 12 605 31 No NO Greedy 8 450 16 NO NO A*算法 16 418 0 YES YES通过比较，Greedy搜索生成的结点数目最少，为8个，效率最高；A*算法生成的结点数目最多，为30个，效率最低。DFS（一般）、BFS和Greedy搜索找到的都不一定最优解，A*算法具有完备性且始终找到的是最优解。宽度优先虽然是完备的（如果分支因子有限的话），在任何情况下宽度优先都能找到一个解，但是，它找到的第一个解并非最优的，此外，最坏的情况是，当目标结点是第d层的最后一个被扩展的结点时，它将耗费大量的时间。宽度优先时间复杂度：（b为分支因子，d为深度）；空间复杂度为所存储的节点的个数。DFS不是完备的（除非查找空间是有限的），同时，它也不能找到最优解。深度优先的时间复杂度：；空间复杂度：（b为分支因子，m为深度，仅有一枝需要存储）；。贪婪算法不是完备的。同时，它找到的解也不一定是最优解。其时间复杂度：（b代表分支数，m为深度）；空间复杂度为）。所以只有A*算法和DFS（回溯+剪枝）是完备的，且能够找到最优解；其时间复杂度：扩展节点的数目；空间复杂度：所有生成的结点。综合来看，BFS和贪婪算法的效率较高，但解并非最优，而A*算法的效率稍逊色，但解为最优；DFS（回溯+剪枝）搜索虽能找到最优解但效率最低。源代码//Graph.h#pragmaonceusingnamespacestd;#defineMaxV20/*#ifndefMY_DEBUG#defineMY_DEBUG#endif*/typedefstruct{charcityname[20];//城市名intvalue;//权值intcost;//A*算法中从当前节点移动到目标节点的预估费用}Ver;classGraph{public:Graph();~Graph();VerV[MaxV];intedge[MaxV][MaxV];intnumofedges;//注意这个变量的引用位置//读取地图节点信息voidReadVertex();//读取地图边关系信息voidReadEdge();//取与第V个节点的第一个邻接点intGetFirstVertex(intv);//找到第V1个节点的V2之后的下一个邻接节点intGetNextVertex(intv1,intv2);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();~SeqQueue();voidQueueInitiate();intQueueNotEmpty();intQueueAppend(intx);intQueueDelete(int*d);intQueueOrderAppend(intx,Graph&G);//A*算法使用intQueue_A_OrderAppend(intx,Graph&G);private:intqueue[MaxSize];intrear;intfront;intcount;};typedefSeqQueueSeqCQuene;//Romania_Trip.h#pragmaonce#include"Queue.h"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();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#endif*/classStack{public:Stack();~Stack();boolStackNotFull();boolStakNotEmpty();voidStackPop(Graph&G);voidStackPush(intx,Graph&G);voidPrintStack(Graph&G);intGetWeight();private:inta[100];inttop1;intweight;};//Graph.cpp#include"Graph.h"#include<iostream>#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_DEBUGprintf("%s\t%d\n",ch,v);#endifV[i].value=v;V[i].cost=0;strcpy(V[i].cityname,ch);i++;}}voidGraph::ReadEdge(){intvalu,i;fstreaminfile("地图数据表.txt",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";#endifi++;}}//取与第V个节点的第一个邻接点intGraph::GetFirstVertex(intv){if(v<0||v>=20){return-1;}for(intcol=0;col<20;col++)if(edge[v][col]>0&&edge[v][col]<1000)returncol;return-1;}//找到第V1个节点的V2之后的下一个邻接节点intGraph::GetNextVertex(intv1,intv2){if(v1<0||v1>=20||v2<0||v2>=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]的值{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(){}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;}}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){cout<<"队列已满"<<endl;return0;}else{if(count==0||G.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++;return1;}else//排序找位置插入{intposition=front;while(G.V[x].value>G.V[queue[position]].value){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;}//A*intSeqQueue::Queue_A_OrderAppend(intx,Graph&G){if(count>0&&rear==front){cout<<"队列已满"<<endl;return0;}else{intx1=G.V[x].value+G.V[x].cost;intx2=0;if(count!=0)x2=G.V[queue[rear-1]].value+G.V[queue[rear-1]].cost;if(count==0||x1>x2)//队尾插入{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>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;}/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;}}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;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;}}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);while(queue.QueueNotEmpty())//队列非空{queue.QueueDelete(&u);//取队列节点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);}}}//深度优先算法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){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);//取当前节点的下一个子节点}visited[v]=0;//返回时置该节点为未访问stack.StackPop(graph);//将该节点弹出栈，并根据graph中weight的值更改当前栈值level--;}//贪婪算法voidRomania_Trip::Greedy_Algorithms(Graph&graph,intv){intu,w;SeqCQuenequeue;//队列存储图节点在图中的索引值,优先队列，value小的在队头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){//cout<<"w==end";count++;return;}queue.QueueOrderAppend(w,graph);//图节点按优先顺序入队列count++;}w=graph.GetNextVertex(u,w);}}}//A*算法voidRomania_Trip::AStar_Algorithms(Graph&graph,intv){//i=0;count=0;intu,w;SeqCQuenequeue;if(v==end)return;//到达终点queue.Queue_A_OrderAppend(v,graph);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++;w=graph.GetNextVertex(u,w);}}}intRomania_Trip::GetCount(){returncount;}intRomania_Trip::GetMaxWeight(){returnMaxWeight;}intRomania_Trip::GetEnd(){returnend;}way*Romania_Trip::GetB(){returnb;}//Source.cpp/*OnholidayinRomania;currentlyinAradFlightleavestomorrowfromBucharestFormulategoal：BeinBucharestFormulateproblemStates:variouscitiesActions:drivebetweencitiesFindsolutionSequenceofcities;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;cout<<endl<<"----------宽度优先算法-----------"<<endl;GraphgraphForBFS;graphForBFS.ReadVertex();graphForBFS.ReadEdge();Romania_Triptrip;time1=clock();trip.BroadFirstSearch(graphForBFS,0);time2=clock();cout<<"---耗时："<<time2-time1<<"ms"<<endl;cout<<endl<<"----------深度优先算法---------"<<endl;trip.ReSet();Stackstack;GraphgraphForDFS;//要重新取得原始的始地图数据，graphForDFS.ReadVertex();graphForDFS.ReadEdge();time1=clock();trip.DepthFirstSearch(graphForDFS,0,stack);time2=clock();cout<<"---耗时："<<time2-time1<<"ms"<<endl;cout<<endl<<"----------贪婪算法---------------"<<endl;trip.ReSet();GraphgraphForGreedy;//要重新取得原始的始地图数据，graphForGreedy.ReadVertex();graphForGreedy.ReadEdge();time1=clock();trip.Greedy_Algorithms(graphForGreedy,0);trip.Print(graphForGreedy,trip.GetB(),trip.GetEnd(),0);time2=clock();cout<<"---耗时："<<time2-time1<<"ms"<<endl;cout<<endl;cout<<endl<<"-------"<<"A星算法---------"<<endl;trip.ReSet();GraphgraphForAStar;//要重新取得原始的始地图数据，graphForAStar.ReadVertex();graphForAStar.ReadEdge();time1=clock();trip.AStar_Algorithms(graphForAStar,0);time2=clock();cout<<"---耗时："<<time2-time1<<"ms"<<endl;cout<<endl;return0;}//Stack.cpp#include"Stack.h"#include<iostream>usingnamespacestd;Stack::Stack(){top1=0;weight=0;}Stack::~Stack(){}boolStack::StackNotFull(){if(top1<100)returntrue;elsereturnfalse;}boolStack::StakNotEmpty(){if(top1>0)returntrue;elsereturnfalse;}voidStack::StackPop(Graph&G){intx;if(StakNotEmpty()){top1--;x=a[top1];if(top1>0)weight-=G.edge[a[top1-1]][x];//弹出节点是weight的值要减少相应的数值}elsecout<<"栈已空！"<<endl;}//将x入栈voidStack::StackPush(intx,Graph&G){if(StackNotFull()){a[top1]=x;if(top1>0)weight=weight+G.edge[a[top1-1]][a[top1]];top1++;}elsecout<<"栈已满！"<<endl;}voidStack::PrintStack(Graph&G){intx=0,nWeight=0;while(x<top1){cout<<G.V[a[x]].cityname;if(x<top1-1)cout<<"->";nWeight+=weight;x++;}#ifdefMY_DEBUGcout<<endl<<"路径长度为："<<nWeight<<endl;#endifcout<<endl;}intStack::GetWeight(){returnweight;}