A*的优化及拓展

我们实现了一个简单版本的A*，当然这里面还有不少值得优化的地方。

min(F)

A*中此公式堪称核心：F = G + H，我们之前已经介绍到了，算法主体是对开启列表的循环遍历，每次都需要从列表中弹出一个F值最小的节点。

是的，我们之前在实现取出最小F值节点的做法是，每次循环末尾将开启列表按照节点的F值进行排序，这是一个"笨"办法，如果开启列表很大，而且我们可以知道，A*的复杂度不是线性的，随着遍历的节点越多，开启列表中的节点数也会越多，如果每次循环都需要对整个列表排序，那么开销会是巨大的。如果想要对1.0版本进行优化的话，这里是很好的一个契入点。

我们可能马上能想到，在将临近节点放入开启列表中时能不能就按照F值排好序，不需要再一次次地对整个列表排序了。这是一个好方法，其实现在一般的A*也是这么实现的，可以到github上搜索下javascript-astar，比如这个bgrins/javascript-astar，它在算法逻辑中维护了一个二叉堆(Binary Heap)，通过这种数据结构来实现将节点快速地插入到列表中。

定向搜索

在A*算法的循环中，开启列表用来保存所有用于寻找路径的被搜索节点。定向搜索是在A*算法基础上，通过对开启列表大小设置约束条件而得到的变体算法。当集合太大的时候，最不可能出现在最优路径上的节点将会被剔除。这样做会带来一个缺点：由于必须得保持这样的筛选，所以可选择的数据结构类型会受到限制。

动态加权

在动态加权算法中，你假定在搜索开始时快速达到(任意)一个位置更为重要，在搜索结束时到达目标位置更为重要。

f(p) = g(p) + w(p) * h(p)
f(p) = g(p) + w(p) * h(p)

有一个权值(w >= 1 )和该启发式关联。当不断接近目标位置的时候，权重值也不断降低。这样降低了启发式函数的重要性，并增加了路径实际代价的相对重要性。

正如之前说过的，寻路总是需要根据实际情况发生变化的，从地图表达到启发式函数的确定，因此上面只介绍了几种最简单的优化方法。

再聊聊启发式函数

启发式函数可以用来控制A*的行为。

1.一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A*算法演变成Dijkstra算法，就能保证找到最短路径。

2.另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，同时A*法演变成贪婪最佳优先搜索算法（Greedy Best-First-Search）。

所以h(n)的选择成了一个有趣的情况，它取决于我们想要A*算法中获得什么结果。h(n)合适的时候，我们会非常快速地得到最短路径。如果h(n)估计的代价太低，我们仍会得到最短路径，但运行速度会减慢。如果估计的代价太高，我们就放弃最短路径，但A*将运行得更快。