http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html
http://www.jianshu.com/p/22dfcca70064
http://blog.csdn.net/yiyikela/article/details/46134339
A*算法
关键点 开启列表【有序列表】 关闭列表。 开启列表是下一个可以访问的点，关闭列表是不会再被访问的点
路径消耗 : 一张地图类似于一个网（加权图），总路径消耗 F = G + H F:总路径 G:当前位置移动到指定位置的消耗 H: 从指定位置到终点的消耗
算法思路 ：围绕着 F = G+H 和 开启列表 关闭列表展开。
1.取F值最小的，加入开启列表，在遍历开启列表中的点，把这个点A的所有周围的点，加入到开启列表。
2.如果这个点A周围的点B已经在开启列表中，计算从开始点经过A 到达B 的G值是不是变小了，变小了就说明从A走，会更近。就把B的父指定为A。并且更新B点的G值和F值。 如果没有更近，就不指定。
3.如果这个点A周围的点B不在开启列表中，就把B的父指定为A。
4.经过步骤2和步骤3，最终B会得到一个到起始点最小的G值。因为每次循环，都会替换成最近父给B点。当循环结束，B点的父就是最近的路径。 【注意】 每次完成一次对B点的循环，就会对开放列表排序一次，下次循环只取第一个，F最小的点
5.循环遍历F值相对低的点，重复2,3步骤，当开启列表中有结束点，就停止循环。 从结束点开始往前找父。最终就得到了最短路径。
拓展点： G值得计算策略 以及H值得计算策略
H值计算 Abs 绝对值
G的算法 Sqrt 平方根
缺点： 启发式的搜索法方法，如果地图格子多，搜索会变慢，成指数级增长。 优化策略，用二叉堆优化A*。
耗时的部分主要是每次重新去点之前，要对开启列表做排序。 二叉堆优化其实就是对开放列表的数据结构优化，用更优的排序方法，其实就是堆排序，快速排序这些基础算法
二叉堆优化A*算法
http://blog.csdn.net/ymiku/article/details/45957107
二叉堆： 完全二叉树+堆（最大堆或者最小堆） 二叉堆的特性： 根的位置*2 和根的位置*2+1 是这个根的子。 子的位置/2 是他的根。
二叉堆并不是完全的顺序排列，但是总是满足根节点是最大或者最小，这就满足了我们的需求
维护二叉堆
为了往堆里添加元素，我们把它放在数组的末尾。然后和它在当前位置/2 处的父节点比较，分数部分被圆整。如果新元素的F值更低，
我们就交换这两个元素。然后我们比较这个元素和它的新父节点，在（当前位置）/2，小数部分圆整，的地方。如果它的F值更低，
我们再次交换。我们重复这个过程直到这个元素不再比它的父节点低，或者这个元素已经到达顶端，处于数组的位置1。
添加元素 ，新元素放到最后，然后不停的跟新元素位置/2的做比较，小了就交换。
元素删除，删除第一个最小的元素，然后把最后一个元素放到第一个，然后不停的跟*2 和*2+1 做比较。 如果大于，就跟较小的交换，直到*2 和*2+1 没有元素位置。表明到底了
网友评论