基于A*算法的最优路径规划系统
需积分: 50 126 浏览量
2018-11-28
22:08:11
上传
评论 6
收藏 188KB DOC 举报
人工智能课程大作业
基于 A*算法的最优路径规划系统
XXXXXXXXX
摘要：人工智能(Artificial Intelligence)是当前科学技术发展的一门前沿学科，同时也是一门新思想，
新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。本文将主要介绍人工智能在搜
索方法上的应用，即基于A*算法的最优路径规划问题的解决方法。A*算法是一种求解最短路径的
有效方法，也是人工智能算法中一种简单的启发式搜索方法。本文介绍了A* 算法的原理及实现机
制， 以及在搜索出的结点解空间集中，用A* 算法如何选择最优结点，最终求解出最短路径的过程。
关键词：人工智能；研究报告；模板
本组成员：xxxxxxx
本人分工：A*算法设计及实现
1 引言
人工智能是在计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基
础发展起来的，因此又可把它看作是一门综合性的边缘学科
[1]
。它的出现及所取得的成就引起了人
们的高度重视,并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为 20 世纪的三
大科学技术成就。人工智能学科研究的主要内容包括：知识表示、自动推理和搜索方法、机器学习
和知识获取、知识处理系统、自然语言理计算机视觉、智能机器人、自动程序设计等方面。
本文主要介绍在路径规划问题上使用 A*搜索算法来找到最优路径的设计与实现。
路径规划是指在旅行前或旅行中为驾驶员提供参考行驶路线的过程，是车辆定位与导航系统的
基本功能之一针对陆地车辆导航的不同要求，在路径规划中可采取多种优化标准，如最短距离、最
少行驶时间或收费。本实验中将使用最短距离来寻找最优路径。
2 算法原理与系统设计
2.1 A*算法的基本思想
A*算法在人工智能中是一种典型的启发式搜索算法，通过选择合适的估价函数，指导搜索朝着
最有希望的方向前进, 以求得最优解
[2]
。A*算法中，关键是求估价函数：f(n)=g(n)+h(n).其中，g(n)
是从起点 u 到当前节点 n 己付出的代价，h(n)是从当前节点 n 到目标节点 v 的代价估计函数，必须
保证h(n) <=h’(n)，其中h’(n)是从当前点到目标点的实际最小代价。
2.2 A*算法的步骤
A*算法的搜索步骤如下：
（1）给起始节点标记，对它的没有标记过的子节点进行扩展；
（2）对每一个子节点计算评价函数值，按评价值的大小进行排列，找出评价值最小的节点，并
给它作标记，如果当前节点就是目标节点，则停止搜索。
（3）否则，对最新被标记的节点进行第（2）步处理，并记录最短路径。
2.3 算法分析
A*算法是利用对问题的了解和对问题求解过程和解的了解，寻求某种有利于问题求解的启发
1
资源评论
