人工智能课程设计报告-罗马尼亚度假问题.pdf
《人工智能课程设计报告-罗马尼亚度假问题.pdf》由会员分享,可在线阅读,更多相关《人工智能课程设计报告-罗马尼亚度假问题.pdf(35页珍藏版)》请在咨信网上搜索。
1、人工智能课程设计报告 课 程:人工智能课程设计报告 班 级:姓 名:学 号:指导教师:赵曼 2015 年 11 月人工智能课程设计报告-1-人工智能课程设计报告人工智能课程设计报告课程背景课程背景 人工智能(Artificial Intelligence),英文缩写为 AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来,理论和技术日益成熟,应用领域也不
2、断扩大,可以设想,未来人工智能带来的科技产品,将会是人类智慧的“容器”。人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能,但能像人那样思考、也可能超过人的智能。人工智能是一门极富挑战性的科学,从事这项工作的人必须懂得计算机知识,心理学和哲学。人工智能是包括十分广泛的科学,它由不同的领域组成,如机器学习,计算机视觉等等,总的说来,人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。人工智能是计算机学科的一个分支,二十世纪七十年代以来被称为世界三大尖端技术之一(空间技术、能源技术、人工智能)。也被
3、认为是二十一世纪三大尖端技术(基因工程、纳米科学、人工智能)之一。这是因为近三十年来它获得了迅速的发展,在很多学科领域都获得了广泛应用,并取得了丰硕的成果,人工智能已逐步成为一个独立的分支,无论在理论和实践上都已自成一个系统。人工智能是研究使计算机来模拟人的某些思维过程和智能行为(如学习、推理、思考、规划等)的学科,主要包括计算机实现智能的原理、制造类似于人脑智能的计算机,使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科,其范围已远远超出了计算机科学的范畴,人工智能与思维科学的关系是实践和理论的关系,人工智能是处于思
4、维科学的技术应用层次,是它的一个应用分支。从思维观点看,人工智能不仅限于逻辑思维,要考虑形象思维、灵感思维才能促进人工智能的突破性的发展,数学常被认为是多种学科的基础科学,数学也进入语言、思维领域,人工智能学科也必须借用数学工具,数学不仅在标准逻辑、模糊数学等范围发挥作用,数学进入人工智能学科,它们将互相促进而更快地发展。人工智能课程设计报告-2-题目一:罗马利亚度假问题题目一:罗马利亚度假问题一一.问题描述问题描述分别用代价一致的宽度优先、有限制的深度优先(预设搜索层次)、贪婪算法和 A*算法求解“罗马利亚度假问题”。即找到从初始地点即找到从初始地点 AradArad 到到 目的地点目的地点
5、 BucharestBucharest 的一条路径。的一条路径。要求:要求:分别用文件存储地图和启发函数表,用生成节点数比较几种算法在问题求解时的效率,并列表给出结果。数据如下:数据如下:1、地图2、启发函数值Arad 366 Mehadia 241 Bucharest 0 Neamt 234 Craiova 160 Oradea 380 Doberta 242Pitesti 100 Eforie 161 Rimmicu_Vikea 193 Fagaras 176 Sibiu 253 Glurgiu 77Timisoara 329 Hirsova 151 Urziceni 80 Iasi 22
6、6 Vaslui 199 Lugoj 244 Zerind 3743、地图数据表0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 140 1000 118 1000 1000 1000 1000 1000 751000 0 1000 1000 1000 1000 75 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 70 10001000 1000 0 1000 1000 1000 1000 101 1000 1000 211 1000 90 1000 1000 85 1000
7、1000 1000 10001000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 87 1000 1000 1000人工智能课程设计报告-3-1000 1000 1000 1000 0 1000 120 138 1000 146 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 151 1000 1000 1000 1000 1000 1000
8、1000 711000 75 1000 1000 120 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 101 1000 138 1000 1000 0 1000 97 1000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 10001000 1000 1000
9、 1000 146 1000 1000 97 1000 0 1000 80 1000 1000 1000 1000 1000 1000 1000 10001000 1000 211 1000 1000 1000 1000 1000 1000 1000 0 99 1000 1000 1000 1000 1000 1000 1000 1000140 1000 1000 1000 1000 151 1000 1000 1000 80 99 0 1000 1000 1000 1000 1000 1000 1000 10001000 1000 90 1000 1000 1000 1000 1000 10
10、00 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000118 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 111 10001000 1000 1000 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 1000 0 98 1000 1000 1000 10001000 1000 85 1000 1000 1000 1000 1000 1000 1000 1000 1000 10
11、00 1000 98 0 1000 1000 1000 10001000 1000 1000 87 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 92 1000 10001000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 92 0 1000 10001000 70 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 111 1000 1000 1000
12、1000 0 100075 1000 1000 1000 1000 71 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0二二.设计分析设计分析1.1.算法分析算法分析 1)1)宽度优先搜索算法宽度优先搜索算法广度优先搜索使用队列(queue)来实现1、把根节点放到队列的末尾。2、每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。3、找到所要找的元素时结束程序。4、如果遍历整个图还没有找到,结束程序。2)深度优先搜索算法深度优先搜索算法深度优先
13、搜索用栈(stack)来实现,整个过程可以想象成一个倒立的树形:1、把根节点压入栈中。人工智能课程设计报告-4-2、每次从栈中弹出一个元素,搜索所有在它下一级的元素,把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。3、找到所要找的元素时结束程序。4、如果遍历整个树还没有找到,结束程序。3)贪婪算法贪婪算法1.建立数学模型来描述问题把求解的问题分成若干个子问题。对每一子问题求解,得到子问题的局部最优解。把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程:从问题的某一初始解出发;while 能朝给定总目标前进一步do求出可行解的一个解元素;由所有解元素组合成问题的一个可行解。4
14、)A*算法算法A*1 (A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。公式表示为:f(n)=g(n)+h(n),其中 f(n)是从初始点经由节点 n 到目标点的估价函数,g(n)是在状态空间中从初始节点到 n 节点的实际代价,h(n)是从 n 到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件,关键在于估价函数 f(n)的选取:估价值 h(n)实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。2.数据结构数据结构1)图结构:图结构:人工智能课程设计报告-5-实现存储“罗马尼亚度假问题”的图空间;抽象图结构的实现:抽象图结构的实现:typedef s
15、truct /图节点类型char cityname20;int value;int cost;Ver;class Graph /图结构public:Graph();Graph();Ver VMaxV;int edgeMaxVMaxV;int numofedges;/注意这个变量的引用位置/读取地图节点信息void ReadVertex();/读取地图边关系信息void ReadEdge();/取与第V个节点的第一个邻接点int GetFirstVertex(int v);/找到第V1个节点的V2之后的下一个邻接节点int GetNextVertex(int v1,int v2);int Get
16、VerValue(int index);/获取Vindex 的ver 的value值int GetVerCost(int index);/获取Vindex 的ver 的cost 值int GetEdge(int row,int col);/获取edgerowcol 的值void SetVerCost(int index,int cost);人工智能课程设计报告-6-;2)队列结构队列结构宽度优先算法以及 A*算法 使用到。抽象队列结构实现:抽象队列结构实现:class SeqQueuepublic:SeqQueue();SeqQueue();void QueueInitiate();int Q
17、ueueNotEmpty();int QueueAppend(int x);int QueueDelete(int*d);int QueueOrderAppend(int x,Graph&G);/A*算法使用int Queue_A_OrderAppend(int x,Graph&G);private:int queueMaxSize;int rear;int front;int count;3)栈结构栈结构人工智能课程设计报告-7-深度优先算法使用;栈结构的抽象类型实现:栈结构的抽象类型实现:class Stackpublic:Stack();Stack();bool StackNotFull
18、();bool StakNotEmpty();void StackPop(Graph&G);void StackPush(int x,Graph&G);void PrintStack(Graph&G);int GetWeight();private:int a100;int top1;int weight;三三.算法设计算法设计1)1)宽度优先搜索算法宽度优先搜索算法人工智能课程设计报告-8-/宽度优先算法void Romania_Trip:BroadFirstSearch(Graph&graph,int v)int u,w;i=0;SeqCQuene queue;visitedv=1;/访问
19、节点count+;if(v=end)return;queue.QueueAppend(v);/入队列while(queue.QueueNotEmpty()/队列非空queue.QueueDelete(&u);/取队列节点w=graph.GetFirstVertex(u);while(w!=-1)/有子节点的话if(!visitedw)/如果子节点未被访问,则访问子节点Visit(w,u);visitedw=1;count+;if(w=end)/找到结果Print(graph,b,end,v);return;queue.QueueAppend(w);/节点压入队列w=graph.GetNextV
20、ertex(u,w);2)深度优先搜索算法深度优先搜索算法/深度优先算法bool isOK=false;int level=0;const int Level=8;/预设的搜索层次void Romania_Trip:DepthFirstSearch(Graph&graph,int v,Stack&stack)int w;i=0;if(isOK=true)return;人工智能课程设计报告-9-if(level+1 Level)return;/大于搜索层次时不再深入level+;visitedv=1;/访问该节点count+;stack.StackPush(v,graph);if(v=end|s
21、tack.GetWeight()=MaxWeight)w=-1;if(v=end&stack.GetWeight()=MaxWeight)cout stack.GetWeight()MaxWeight=stack.GetWeight();*/cout -路径长度为:stack.GetWeight()endl -访问节点数为:count endl-搜索层次:levelendl;isOK=true;elsew=graph.GetFirstVertex(v);/取当前节点的第一个子节点while(w!=-1)if(!visitedw)DepthFirstSearch(graph,w,stack);/
22、递归访问w=graph.GetNextVertex(v,w);/取当前节点的下一个子节点visitedv=0;/返回时置该节点为未访问stack.StackPop(graph);/将该节点弹出栈,并根据graph 中weight 的值更改当前栈值level-;3)贪婪算法贪婪算法/贪婪算法void Romania_Trip:Greedy_Algorithms(Graph&graph,int v)int u,w;人工智能课程设计报告-10-SeqCQuene queue;/队列存储图节点在图中的索引值,优先队列,value小的在队头visitedv=1;if(v=end)return;queue
23、.QueueOrderAppend(v,graph);/图节点按优先顺序入队列count+;/访问节点数+1while(queue.QueueNotEmpty()/宽度优先,循环queue.QueueDelete(&u);/删除队列头元素并返回删除的数值/cout u=u ;w=graph.GetFirstVertex(u);while(w!=-1)if(!visitedw)Visit(w,u);/访问w节点,将way b 的指向更新if(w=end)/cout w=end;count+;return;queue.QueueOrderAppend(w,graph);/图节点按优先顺序入队列co
24、unt+;w=graph.GetNextVertex(u,w);4)A*算法算法/A*算法void Romania_Trip:AStar_Algorithms(Graph&graph,int v)/i=0;count=0;int u,w;SeqCQuene queue;if(v=end)return;/到达终点queue.Queue_A_OrderAppend(v,graph);count+;while(queue.QueueNotEmpty()人工智能课程设计报告-11-queue.QueueDelete(&u);if(u=end)cout -路径长度为:graph.GetVerCost(u
25、)+graph.GetVerValue(u)endl-访问节点数为:count endl;return;w=graph.GetFirstVertex(u);while(w!=-1)int cost=graph.GetVerCost(u)+graph.GetEdge(w,u);graph.SetVerCost(w,cost);/设置当前节点移动到目标节点的预估费用queue.Queue_A_OrderAppend(w,graph);/按预估费用优先入队列 count+;w=graph.GetNextVertex(u,w);四四.运行结果及分析运行结果及分析人工智能课程设计报告-12-分析:节点数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 课程设计 报告 罗马尼亚 度假 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。