[算法]算法实战 -- 搜索

Author Avatar
与狼同行 11月 28, 2016

拼图游戏 - A*算法

定义

二叉堆是完全二元树或者是近似完全二元树,它分为两种: 最大堆 和 最小堆 。
最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。示意图如下:


如上图所示,当向最大堆中添加数据时:先将数据加入到最大堆的最后,然后尽可能把这个元素往上挪,直到挪不动为止!

如上图所示,当从最大堆中删除数据时:先删除该数据,然后用最大堆中最后一个的元素插入这个空位;接着,把这个“空位”尽量往上挪,直到剩余的数据变成一个最大堆

优先队列

优先队列就是作业调度类的ADT,可以用二叉堆来实现。 优先队列最少有两个操作:插入(Insert)和删除最小者(DeleteMin)。

在拼图游戏中,3阶以下可以使用广度优先算法找出最优解,但是速率上远远不如A算法。A算法可以应对5阶的拼图游戏。
A[1] (A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法,也是许多其他问题的常用启发式算法。
注意是最有效的直接搜索算法。之后涌现了很多预处理算法(ALT,CH,HL等等),在线查询效率是A
算法的数千甚至上万倍。
公式表示为: f(n)=g(n)+h(n),
其中 f(n) 是从初始状态经由状态n到目标状态的代价估计,
g(n) 是在状态空间中从初始状态到状态n的实际代价,
h(n) 是从状态n到目标状态的最佳路径的估计代价。