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

人工智能课程设计报告 课 程 人工智能课程设计报告 班 级 姓 名 学 号 指导教师 赵曼 2015 年 11 月 人工智能课程设计报告 1 人工智能课程设计报告人工智能课程设计报告 课程背景课程背景 人工智能 Artificial Intelligence 英文缩写为 AI 它是研究 开发用于模拟 延伸和扩展人的智 能的理论 方法 技术及应用系统的一门新的技术科学 人工智能是计算机科学的一个分支 它企图了解智 能的实质 并生产出一种新的能以人类智能相似的方式做出反应的智能机器 该领域的研究包括机器人 语言 识别 图像识别 自然语言处理和专家系统等 人工智能从诞生以来 理论和技术日益成熟 应用领域也不断 扩大 可以设想 未来人工智能带来的科技产品 将会是人类智慧的 容器 人工智能是对人的意识 思维的信息过程的模拟 人工智能不是人的智能 但能像人那样思考 也可能超 过人的智能 人工智能是一门极富挑战性的科学 从事这项工作的人必须懂得计算机知识 心理学和哲学 人工智能是 包括十分广泛的科学 它由不同的领域组成 如机器学习 计算机视觉等等 总的说来 人工智能研究的一个 主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作 但不同的时代 不同的人对这种 复 杂工作 的理解是不同的 人工智能是计算机学科的一个分支 二十世纪七十年代以来被称为世界三大尖端技术之一 空间技术 能 源技术 人工智能 也被认为是二十一世纪三大尖端技术 基因工程 纳米科学 人工智能 之一 这是因 为近三十年来它获得了迅速的发展 在很多学科领域都获得了广泛应用 并取得了丰硕的成果 人工智能已逐 步成为一个独立的分支 无论在理论和实践上都已自成一个系统 人工智能是研究使计算机来模拟人的某些思维过程和智能行为 如学习 推理 思考 规划等 的学科 主要包括计算机实现智能的原理 制造类似于人脑智能的计算机 使计算机能实现更高层次的应用 人工智能 将涉及到计算机科学 心理学 哲学和语言学等学科 可以说几乎是自然科学和社会科学的所有学科 其范围 已远远超出了计算机科学的范畴 人工智能与思维科学的关系是实践和理论的关系 人工智能是处于思维科学 的技术应用层次 是它的一个应用分支 从思维观点看 人工智能不仅限于逻辑思维 要考虑形象思维 灵感 思维才能促进人工智能的突破性的发展 数学常被认为是多种学科的基础科学 数学也进入语言 思维领域 人工智能学科也必须借用数学工具 数学不仅在标准逻辑 模糊数学等范围发挥作用 数学进入人工智能学科 它们将互相促进而更快地发展 人工智能课程设计报告 2 题目一 罗马利亚度假问题题目一 罗马利亚度假问题 一一 问题描述问题描述 分别用代价一致的宽度优先 有限制的深度优先 预设搜索层次 贪婪算法和 A 算法求 解 罗马利亚度假问题 即找到从初始地点即找到从初始地点 AradArad 到到 目的地点目的地点 BucharestBucharest 的一条路径 的一条路径 要求 要求 分别用文件存储地图和启发函数表 用生成节点数比较几种算法在问题求解时的效率 并列 表给出结果 数据如下 数据如下 1 地图 2 启发函数值 Arad 366 Mehadia 241 Bucharest 0 Neamt 234 Craiova 160 Oradea 380 Doberta 242 Pitesti 100 Eforie 161 Rimmicu Vikea 193 Fagaras 176 Sibiu 253 Glurgiu 77 Timisoara 329 Hirsova 151 Urziceni 80 Iasi 226 Vaslui 199 Lugoj 244 Zerind 374 3 地图数据表 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 140 1000 118 1000 1000 1000 1000 1000 75 1000 0 1000 1000 1000 1000 75 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 70 1000 人工智能课程设计报告 3 1000 1000 0 1000 1000 1000 1000 101 1000 1000 211 1000 90 1000 1000 85 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 87 1000 1000 1000 1000 1000 1000 1000 0 1000 120 138 1000 146 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 151 1000 1000 1000 1000 1000 1000 1000 71 1000 75 1000 1000 120 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 101 1000 138 1000 1000 0 1000 97 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 1000 1000 1000 1000 1000 146 1000 1000 97 1000 0 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 211 1000 1000 1000 1000 1000 1000 1000 0 99 1000 1000 1000 1000 1000 1000 1000 1000 140 1000 1000 1000 1000 151 1000 1000 1000 80 99 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 90 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 118 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 111 1000 1000 1000 1000 1000 1000 1000 1000 1000 86 1000 1000 1000 1000 1000 0 98 1000 1000 1000 1000 1000 1000 85 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 98 0 1000 1000 1000 1000 1000 1000 1000 87 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 92 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 92 0 1000 1000 1000 70 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 111 1000 1000 1000 1000 0 1000 75 1000 1000 1000 1000 71 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 人工智能课程设计报告 4 二二 设计分析设计分析 1 1 算法分析算法分析 1 1 宽度优先搜索算法宽度优先搜索算法 广度优先搜索使用队列 queue 来实现 1 把根节点放到队列的末尾 2 每次从队列的头部取出一个元素 查看这个元素所有的下一级元素 把它们放到队列的末尾 并把这 个元素记为它下一级元素的前驱 3 找到所要找的元素时结束程序 4 如果遍历整个图还没有找到 结束程序 2 深度优先搜索算法深度优先搜索算法 深度优先搜索用栈 stack 来实现 整个过程可以想象成一个倒立的树形 1 把根节点压入栈中 2 每次从栈中弹出一个元素 搜索所有在它下一级的元素 把这些元素压入栈中 并把这个元素记为它 下一级元素的前驱 3 找到所要找的元素时结束程序 4 如果遍历整个树还没有找到 结束程序 3 贪婪算法贪婪算法 1 建立数学模型来描述问题 把求解的问题分成若干个子问题 对每一子问题求解 得到子问题的局部最优解 把子问题的解局部最优解合成原来解问题的一个解 实现该算法的过程 从问题的某一初始解出发 while 能朝给定总目标前进一步 do 求出可行解的一个解元素 由所有解元素组合成问题的一个可行解 4 A 算法算法 人工智能课程设计报告 5 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 图结构 图结构 实现存储 罗马尼亚度假问题 的图空间 抽象图结构的实现 抽象图结构的实现 typedef struct 图节点类型 char cityname 20 int value int cost Ver class Graph 图结构 public Graph 人工智能课程设计报告 6 Graph Ver V MaxV int edge MaxV MaxV int numofedges 注意这个变量的引用位置 读取地图节点信息 void ReadVertex 读取地图边关系信息 void ReadEdge 取与第V个节点的第一个邻接点 int GetFirstVertex int v 找到第V1个节点的V2之后的下一个邻接节点 int GetNextVertex int v1 int v2 int GetVerValue int index 获取V index 的ver 的value值 int GetVerCost int index 获取V index 的ver 的cost 值 int GetEdge int row int col 获取edge row col 的值 void SetVerCost int index int cost 2 队列结构队列结构 宽度优先算法以及 A 算法 使用到 抽象队列结构实现 抽象队列结构实现 class SeqQueue public SeqQueue SeqQueue 人工智能课程设计报告 7 void QueueInitiate int QueueNotEmpty int QueueAppend int x int QueueDelete int d int QueueOrderAppend int x Graph A 算法使用 int Queue A OrderAppend int x Graph private int queue MaxSize int rear int front int count 3 栈结构栈结构 深度优先算法使用 栈结构的抽象类型实现 栈结构的抽象类型实现 class Stack public Stack Stack bool StackNotFull bool StakNotEmpty void StackPop Graph 人工智能课程设计报告 8 void StackPush int x Graph void PrintStack Graph int GetWeight private int a 100 int top1 int weight 三三 算法设计算法设计 1 1 宽度优先搜索算法宽度优先搜索算法 宽度优先算法 void Romania Trip BroadFirstSearch Graph i 0 SeqCQuene queue visited v 1 访问节点 count if v end return queue QueueAppend v 入队列 while queue QueueNotEmpty 队列非空 queue QueueDelete 取队列节点 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 节点压入队列 人工智能课程设计报告 9 w graph GetNextVertex u w 2 深度优先搜索算法深度优先搜索算法 深度优先算法 bool isOK false int level 0 const int Level 8 预设的搜索层次 void Romania Trip DepthFirstSearch Graph 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 cout 路径长度为 stack GetWeight endl 访问节点数为 count endl 搜索层次 level endl isOK true else w graph GetFirstVertex v 取当前节点的第一个子节点 while w 1 人工智能课程设计报告 10 if visited w DepthFirstSearch graph w stack 递归访问 w graph GetNextVertex v w 取当前节点的下一个子节点 visited v 0 返回时置该节点为未访问 stack StackPop graph 将该节点弹出栈 并根据graph 中weight 的值更改当前栈值 level 3 贪婪算法贪婪算法 贪婪算法 void Romania Trip Greedy Algorithms Graph SeqCQuene queue 队列存储图节点在图中的索引值 优先队列 value小的在队头 visited v 1 if v end return queue QueueOrderAppend v graph 图节点按优先顺序入队列 count 访问节点数 1 while queue QueueNotEmpty 宽度优先 循环 queue QueueDelete 删除队列头元素并返回删除的数值 cout u u w graph GetFirstVertex u while w 1 if visited w Visit w u 访问w节点 将way b 的指向更新 if w end cout w end count return queue QueueOrderAppend w graph 图节点按优先顺序入队列 count w graph GetNextVertex u w 人工智能课程设计报告 11 4 A 算法算法 A 算法 void Romania Trip AStar Algorithms Graph count 0 int u w SeqCQuene queue if v end return 到达终点 queue Queue A OrderAppend v graph count while queue QueueNotEmpty queue QueueDelete if u end cout 路径长度为 graph GetVerCost u 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 四四 运行结果及分析运行结果及分析 分析 节点数路径长度耗时 ms Optimality Completeness BFS 1145016NoYES DFS 1260531NoNO Greedy 845016NONO A 算法164180 YESYES 人工智能课程设计报告 13 通过比较 Greedy 搜索生成的结点数目最少 为 8 个 效率最高 A 算法生成的结点数目最多 为 30 个 效率最低 DFS 一般 BFS 和 Greedy 搜索找到的都不一定最优解 A 算法具有完备性且始终找 到的是最优解 宽度优先虽然是完备的 如果分支因子有限的话 在任何情况下宽度优先都能找到一个解 但是 它找到的第一个解并非最优的 此外 最坏的情况是 当目标结点是第 d 层的最后一个被扩展的结点 时 它将耗费大量的时间 宽度优先时间复杂度 b 为分支因子 d 为深度 空间复杂度为所存储的节点的个数 DFS 不是完备的 除非查找空间是有限的 同时 它也不 能找到最优解 深度优先的时间复杂度 空间复杂度 b 为分支因子 m 为深度 仅 有一枝需要存储 贪婪算法不是完备的 同时 它找到的解也不一定是最优解 其时间复杂度 b 代表分支数 m 为深度 空间复杂度为 所以只有 A 算法和 DFS 回溯 剪枝 是完 备的 且能够找到最优解 其时间复杂度 扩展节点的数目 空间复杂度 所有生成的结点 综合来看 BFS 和贪婪算法的效率较高 但解并非最优 而 A 算法的效率稍逊色 但解为最优 DFS 回溯 剪枝 搜索虽 能找到最优解但效率最低 人工智能课程设计报告 14 源代码 Graph h pragma once using namespace std define MaxV 20 ifndef MY DEBUG define MY DEBUG endif typedef struct char cityname 20 城市名 int value 权值 int cost A 算法中从当前节点移动到目标节点的预估费用 Ver class Graph public Graph Graph Ver V MaxV int edge MaxV MaxV int numofedges 注意这个变量的引用位置 读取地图节点信息 void ReadVertex 读取地图边关系信息 void ReadEdge 取与第V个节点的第一个邻接点 int GetFirstVertex int v 找到第V1个节点的V2之后的下一个邻接节点 人工智能课程设计报告 15 int GetNextVertex int v1 int v2 int GetVerValue int index 获取V index 的ver 的value值 int GetVerCost int index 获取V index 的ver 的cost 值 int GetEdge int row int col 获取edge row col 的值 void SetVerCost int index int cost private Queue h pragma once include include Stack h define MaxSize 30 ifndef MY DEBUG define MY DEBUG endif class SeqQueue public SeqQueue SeqQueue void QueueInitiate int QueueNotEmpty int QueueAppend int x int QueueDelete int d int QueueOrderAppend int x Graph A 算法使用 int Queue A OrderAppend int x Graph private int queue MaxSize int rear int front 人工智能课程设计报告 16 int count typedef SeqQueue SeqCQuene Romania Trip h pragma once include Queue h typedef struct int father int me way class Romania Trip public Romania Trip Romania Trip void Visit int v int u void Print Graph void BroadFirstSearch Graph void DepthFirstSearch Graph void Greedy Algorithms Graph void AStar Algorithms Graph void ReSet int GetCount int GetMaxWeight int GetEnd way GetB private way b int i int end int count 人工智能课程设计报告 17 int visitedCity 20 int MaxWeight int visited 20 Stack h pragma once include Graph h include using namespace std ifndef MY DEBUG define MY DEBUG endif class Stack public Stack Stack bool StackNotFull bool StakNotEmpty void StackPop Graph void StackPush int x Graph void PrintStack Graph int GetWeight private int a 100 int top1 int weight Graph cpp include Graph h include include include include using namespace std Graph Graph numofedges 0 人工智能课程设计报告 18 Graph Graph void Graph ReadVertex int i 0 v char ch 20 fstream infile 启发式数值 txt ios in while infile ch endif V i value v V i cost 0 strcpy V i cityname ch i void Graph ReadEdge int valu i fstream infile 地图数据表 txt ios in i 0 while infile valu edge i 20 i 20 valu ifdef MY DEBUG if i 20 0 cout endl cout edge i 20 i 20 t endif i 取与第V个节点的第一个邻接点 int Graph GetFirstVertex int v 人工智能课程设计报告 19 if v 20 return 1 for int col 0 col0 return 1 找到第V1个节点的V2之后的下一个邻接节点 int Graph GetNextVertex int v1 int v2 if v1 20 v2 20 return 1 for int col v2 1 col0 return 1 int Graph GetVerValue int index 获取V index 的ver 的values值 return V index value int Graph GetVerCost int index 获取V index 的ver 的cost 值 return V index cost int Graph GetEdge int row int col 获取edge row col 的值 return edge row col 人工智能课程设计报告 20 void Graph SetVerCost int index int cost V index cost cost Queue cpp include Queue h include include Stack h SeqQueue SeqQueue rear 0 front 0 count 0 SeqQueue SeqQueue int SeqQueue QueueNotEmpty if count 0 return 1 else return 0 int SeqQueue QueueAppend int x if count 0 return 0 else 人工智能课程设计报告 21 queue rear x rear rear 1 MaxSize count return 1 int SeqQueue QueueDelete int d if count 0 cout 队列已空 0 rear rear 1 MaxSize count return 1 人工智能课程设计报告 22 else if G V x value G V queue position value position int i for i front i0 rear rear 1 MaxSize count return 1 else 队头插入 if G V x value G V x cost G V queue position MaxSize value G V queue position MaxSize cost position int i 人工智能课程设计报告 24 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 return 1 return 0 Romania Trip cpp include Romania Trip h include include include using namespace std Romania Trip Romania Trip b new way 100 i 0 end 2 count 0 MaxWeight 10000 for size t i 0 i 20 i visited i 0 void Romania Trip ReSet if NULL b delete b b new way 20 i 0 人工智能课程设计报告 25 end 2 count 0 for size t i 0 i 20 i visited i 0 Romania Trip Romania Trip if NULL b delete b void Romania Trip Visit int v int u b i father u b i me v i void Romania Trip Print Graph vector CityName string name graph V end cityname CityName push back name while 1 for int j 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 0 i cout CityName i cout Bucharest endl cout 路径长度为 Bway endl 访问节点数为 count Level return 大于搜索层次时不再深入 level visited v 1 访问该节点 count stack StackPush v graph if v end stack GetWeight MaxWeight w 1 if v end cout 路径长度为 stack GetWeight endl 访问节点数为 count endl 搜索层次 level endl isOK true 人工智能课程设计报告 28 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 贪婪算法 void Romania Trip Greedy Algorithms Graph SeqCQuene queue 队列存储图节点在图中的索引值 优先队列 value小的在队头 visited v 1 if v end return queue QueueOrderAppend v graph 图节点按优先顺序入队列 count 访问节点数 1 while queue QueueNotEmpty 宽度优先 循环 queue QueueDelete 删除队列头元素并返回删除的数值 人工智能课程设计报告 29 cout u u w graph GetFirstVertex u while w 1 if visited w Visit w u 访问w节点 将way b 的指向更新 if w end cout w end count return queue QueueOrderAppend w graph 图节点按优先顺序入队列 count w graph GetNextVertex u w A 算法 void Romania Trip AStar Algorithms Graph count 0 int u w SeqCQuene queue if v end return 到达终点 queue Queue A OrderAppend v graph count while queue QueueNotEmpty queue QueueDelete if u end cout 路径长度为 graph GetVerCost u 人工智能课程设计报告 30 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 int Romania Trip GetCount return count int Romania Trip GetMaxWeight return MaxWeight int Romania Trip GetEnd return end way Romania Trip GetB return b 人工智能课程设计报告 31 Source cpp On holiday in Romania currently in Arad Flight leaves tomorrow from Bucharest Formulate goal Be in Bucharest Formulate problem States various cities Actions drive between cities Find solution Sequence of cities e g Arad Sibiu Fagaras Bucharest include Graph h include Queue h include Stack h include Romania