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

———课程:人工智能课程设计报告班级:姓名:学号:指导教师:赵曼2015年11月———人工智能课程设计报告课程背景人工智能（ArtificialIntelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。———题目一：罗马利亚度假问题一.问题描述分别用代价一致的宽度优先、有限制的深度优先（预设搜索层次）、贪婪算法和A*算法求解“罗马利亚度假问题”。即找到从初始地点Arad到目的地点Bucharest的一条路径。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，并列表给出结果。数据如下：1、地图2、启发函数值Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Doberta242Pitesti100Eforie161Rimmicu_Vikea193Fagaras176Sibiu253Glurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind3743、地图数据表01000100010001000100010001000100010001000140100011810001000100010001000751000010001000100010007510001000100010001000100010001000100010001000701000———1000100001000100010001000101100010002111000901000100085100010001000100010001000100001000100010001000100010001000100010001000100010008710001000100010001000100010000100012013810001461000100010001000100010001000100010001000100010001000100010000100010001000100010001511000100010001000100010001000711000751000100012010000100010001000100010001000100010001000100010001000100010001000101100013810001000010009710001000100010001000100010001000100010001000100010001000100010001000100001000100010001000100086100010001000100010001000100010001000146100010009710000100080100010001000100010001000100010001000100021110001000100010001000100010000991000100010001000100010001000100014010001000100010001511000100010008099010001000100010001000100010001000100010009010001000100010001000100010001000100001000100010001000100010001000118100010001000100010001000100010001000100010001000010001000100010001111000100010001000100010001000100010008610001000100010001000098100010001000100010001000851000100010001000100010001000100010001000100098010001000100010001000100010008710001000100010001000100010001000100010001000100009210001000100010001000100010001000100010001000100010001000100010001000100092010001000100070100010001000100010001000100010001000100010001111000100010001000010007510001000100010007110001000100010001000100010001000100010001000100010000———二.设计分析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])//如果子节点未被访问，则访问子节点{V