首页 > 代码库 > 【启发式搜索】A*与IDA*学习笔记
【启发式搜索】A*与IDA*学习笔记
搞了这么久发现自己到现在还不会启发式搜索ヾ(?｀Д′?)所以今天正好趁着搜索练习题的风去搞了启发式搜索
A*搜索算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或在线游戏的BOT的移动计算上。
该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
在此算法中，如果以 g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离，那么 A*算法的公式为：f(n)=g(n)+h(n)。 这个公式遵循以下特性：
- 如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法
- 如果h(n)<=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。————来自wikipedia
至于IDA*，全称叫迭代加深A*，其实就是迭代加深搜索和A*的一个小小的结合而已0-0由于A*会扩展出很多节点，这时候就需要迭代加深搜索来对A*进行一个小小的优化来减少时间和空间的使用。
看了看介绍，感觉A*的关键就在于估价函数的使用，需要有一个好的估价标准才能正确的进行搜索。
在使用A*搜索时我们通常把问题抽象成图论问题然后进行搜索。
比如接下来这个经典的图片
我们要从图中绿色的点到达红色的点，中间蓝色的是障碍物。
在这个问题中我们扩展时候每一次就扩展出当前节点四周的点。
在图中，左上角是估价函数F的值，左下角是G，右下角是H。
我们以每个点到红色点的曼哈顿距离作为这个题目的估价标准。（在进行估价时候不考虑墙）
然后开始扩展节点。将扩展出的节点存起来，选择其中F最小的点记录进路径中，然后以该节点为起点继续搜。
对于墙，我们不予扩展。
当遇到图中这样周围节点的F相同时，我们通常选择后扩展出的那一个点记录。
原图选择了下面的节点。
重复这些操作，最后就有了
之前觉得启发式搜索挺难的= =现在看了看其实还好啊╮(╯▽╰)╭
在使用A*时候，常用的估价标准就是用曼哈顿距离。
在做其他的启发式搜索时，也可以直接贪心作为标准。
而A*中为了判重通常会占用大量的空间，可以使用hash来简化判断，提高效率。
这里引用别人一段话来讲IDA*（原作者链接http://blog.csdn.net/urecvbnkuhbh_54245df/article/details/5856756）
“归纳一下，IDA*的基本思路是：首先将初始状态结点的H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值maxH，再重复上述搜索，直到找到一个解。在保证H值的计算满足A*算法的要求下，可以证明找到的这个解一定是最优解。在程序实现上，IDA* 要比 A* 方便，因为不需要保存结点，不需要判重复，也不需要根据 H值对结点排序，占用空间小。
在一般的问题中是这样使用IDA*算法的，当前局面的估价函数值+当前的搜索深度 > 预定义的最大搜索深度时，就进行剪枝。
这个估计函数的选取没有统一的标准，找到合适的该函数并不容易，但是可以大致按照这个原则：在一定范围内加大各个状态启发函数值的差别。
”【启发式搜索】A*与IDA*学习笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。