| 【算法】A*算法与启发函数 | 您所在的位置：网站首页 › a*算法与dijkstra › 【算法】A*算法与启发函数 |
【算法】A*算法与启发函数
|
写这篇是因为看到国外一篇讲的巨好的关于A*算法的文章——Introduction to A*。图文并茂，而且讲了一些A*算法的来龙去脉，有些观点也醍醐灌顶啊，所以赶紧来总结一下。 A*算法为什么叫这个名这个从wiki上看来的，一开始是57年提出的Dijkstra算法，然后64年Nils Nilsson提出了A1算法，是一个启发式搜索算法，而后又被改进成为A2算法，直到68年，被Peter E. Hart改进成为A*算法，为什么叫A*呢，因为原作者借鉴了统计学方面的一个*上标，在统计学中，一个变量加上 * 表示这个变量的最优解，所以作者认为他们是最优解，是前人（A算法）的集大成者，所以叫A*。 BFS和Dijkstra算法要讲A*算法就必须去讲Dijkstra算法，因为Dijkstra算法可以看成A*算法的特例。而BFS又可以看成Dijkstra的特例， 对于BFS算法，python代码如下： frontier = Queue() frontier.put(start) came_from = {} came_from[start] = None while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): if next not in came_from: frontier.put(next) came_from[next] = current对于Dijkstra算法，python代码如下： frontier = PriorityQueue() #这个地方用优先队列了 frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost frontier.put(next, priority) came_from[next] = currentDijkstra算法是一个贪心算法/也可以看成动规。其是每次都找离起点最近的点 Dijkstra算法保证能得到最优解，但是扫描的区域会比较的大。 Dijkstra算法搜索的空间太大了，能不能利用网格图的一些特点来简化搜索呢？想到了贪心算法。 贪心搜索算法，是每次找离终点距离最近的点。 另外如何定义这个距离呢，一般网格图是用曼哈顿距离来定义的。即两个点之间坐标差的绝对值之和。 def heuristic(a, b): # Manhattan distance on a square grid return abs(a.x - b.x) + abs(a.y - b.y) frontier = PriorityQueue() frontier.put(start, 0) came_from = {} came_from[start] = None while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): if next not in came_from: priority = heuristic(goal, next) frontier.put(next, priority) came_from[next] = current
那么能不能综合上面Dijkstra算法得到最优解和贪心算法速度快的特点，有更好的办法呢？ 【注意一下这个地方，Dijkstra算法是适用于任何图算法找最短距离均可的，但是用到启发式算法的话，大部分情况下会是一个方格图，因为只有方格图才能比较好的估算从当前点到终点的距离】 那么我们可以先定义一个估算函数 f(n)=g(n)+h(n) 其中 g(n) 表示起点到当前点 n 实际走的代价，h(n)表示当前点 n 到终点的估算代价。 所以上面两个合起来就是其走当前点到终点的总代价函数f(n) 而 h(n) 这个估计函数不同的估计情况，结果也不会相同。 先考虑极端情况， 如果 h(n)=0 的情况下，只有 g(n) 起作用，那么A*算法就是Dijkstra算法。如果 h(n) 始终小于等于实际 n 点到终点的距离，那么必然能够保证A*算法找的解就是最优解。而且h(n)越小，则A*扩展的节点也就越多，A*算法运行的也就越慢。如果 h(n) 始终都等于实际 n 点到终点的距离，那么A*算法只会严格走从起点到终点的最短路径。虽然这种情况一般不可能发生，当然一些特殊情况下会发生【比如没有障碍物的情况】。 如果h(n)有时候大于实际 n 点到终点的距离，那么不能保证A*算法能够找到最短路径 另外一种极端情况，就是如果只有h(n)发挥作用，则A*算法就相当于贪心算法。 A*算法一般选择曼哈顿距离的A*算法被称为simply A算法，不过因为这种方法被用的最广泛，所以一般不加以区分了。实际上还有很多别的变种的。 A*算法的python代码，可以看到跟Dijkstra算法非常像啦，只不过加到队列里的优先级是 f(n) 值，而不是 g(n) frontier = PriorityQueue() frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost < cost_so_far[next]: cost_so_far[next] = new_cost priority = new_cost + heuristic(goal, next) frontier.put(next, priority) came_from[next] = currentA*算法跑的时间要小于Dijkstra，同时能够保证找的路径是最短路径。 关于这些路径搜索算法的程序详见：http://www.redblobgames.com/pathfinding/a-star/implementation.html 上面的PriorityQueue()详见下面的实现： import heapq class PriorityQueue: def __init__(self): self.elements = [] def empty(self): return len(self.elements) == 0 def put(self, item, priority): heapq.heappush(self.elements, (priority, item)) def get(self): return heapq.heappop(self.elements)[1] 参考资料以下两个资料写的都非常的好，第一个 Introduction to A*介绍的那个A*算法，里面各种动画非常丰富。Pathfinding这个资料非常的长，是1资料的加长版，里面详细讲了各种路径搜索算法，和改进。 |
【本文地址】