A星算法:距离启发式 [英] A star algorithm: Distance heuristics
问题描述
我正在使用这里看到的 A 星算法(取自 http://code.activestate.com/recipes/578919-python-a-pathfinding-with-binary-heap/)，但我有一个我不明白的问题.
I am using the A star algorithm as seen here (taken from http://code.activestate.com/recipes/578919-python-a-pathfinding-with-binary-heap/), but I have a problem I don't understand.
这里给出的启发式是两点之间距离的平方.我发现如果我取它的平方根，我的结果会更准确，但函数的运行时间会急剧增加(即它比以前经历了很多很多的循环).
The heuristics given here is the square of the distance between two points. I found that if I take the square root of it instead, my results are more accurate, but the running time of the function increases dramatically (i.e. it goes over many, many more loops than before).
为什么启发式的变化会导致它更准确，运行时间更长?
Why does the change in heuristics cause it to be more accurate, and take longer to run?
# Author: Christian Careaga (christian.careaga7@gmail.com)
# A* Pathfinding in Python (2.7)
# Please give credit if used
import numpy
from heapq import *
def heuristic(a, b):
return (b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2
def astar(array, start, goal):
neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
close_set = set()
came_from = {}
gscore = {start:0}
fscore = {start:heuristic(start, goal)}
oheap = []
heappush(oheap, (fscore[start], start))
while oheap:
current = heappop(oheap)[1]
if current == goal:
data = []
while current in came_from:
data.append(current)
current = came_from[current]
return data
close_set.add(current)
for i, j in neighbors:
neighbor = current[0] + i, current[1] + j
tentative_g_score = gscore[current] + heuristic(current, neighbor)
if 0 <= neighbor[0] < array.shape[0]:
if 0 <= neighbor[1] < array.shape[1]:
if array[neighbor[0]][neighbor[1]] == 1:
continue
else:
# array bound y walls
continue
else:
# array bound x walls
continue
if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):
continue
if tentative_g_score < gscore.get(neighbor, 0) or neighbor not in [i[1]for i in oheap]:
came_from[neighbor] = current
gscore[neighbor] = tentative_g_score
fscore[neighbor] = tentative_g_score + heuristic(neighbor, goal)
heappush(oheap, (fscore[neighbor], neighbor))
return False
'''Here is an example of using my algo with a numpy array,
astar(array, start, destination)
astar function returns a list of points (shortest path)'''
nmap = numpy.array([
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,1,1,1,1,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[1,0,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,1,1,1,1,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[1,0,1,1,1,1,1,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,1,1,1,1,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0]])
print astar(nmap, (0,0), (10,13))
推荐答案
为什么启发式的变化会导致它更准确，运行时间更长?
Why does the change in heuristics cause it to be more accurate, and take longer to run?
第一个启发式，距离平方，即使实际距离的计算方式相同，也高估了实际距离(很多，取决于情况)，因为实际距离计算为单个步骤的总和(总和的平方小于总和的平方).A* 倾向于通过没有足够的探索来保证找到最佳路线来对此做出回应，它更喜欢继续遵循它正在尝试的任何路线，因为向目标更近一步会减少与目标的预期距离lot(比步骤本身所采取的要多得多，因为启发式高估了太多).它通常不会备份(即从队列中取出一些先前打开的节点而不是最近的节点)并尝试其他操作，因为返回意味着 H 值上升的幅度大于 G 值下降的幅度.
The first heuristic, distance squared, overestimates the real distance (by a lot, depending on the situation) even though the actual distance is computed the same way, because the actual distance is computed as the sum of single steps (the sum of squares is less than the square of the sum). A* tends to respond to that by not exploring enough to guarantee finding the optimal route, it prefers to just keep following whatever route it is trying because taking a step closer to the goal reduces the expected distance to it by a lot (by much more than the step itself takes, because the heuristic overestimates so much). It will often not back up (ie take some previously-opened node from the queue instead of the most-recent node) and try something else, because going back means the H value goes up more than the G value goes down.
所以这有你看到的两个效果:
So this has the two effects you saw:
- 它通常要快得多(除了在某些迷宫中，您可以欺骗"算法使其走错路的时间比其他方式要长得多)
- 它不一定能找到最佳路线
您的连通性是 8 邻域，对此有比欧几里德距离更好的启发式方法.请注意，路径不能有任意角度，它必须直行或成 45 度角，因此即使没有障碍物，欧几里德距离也会低估距离.这是正确的，但您可以使用对角线距离"启发式:(取自 here 并且易于适应 Python - 该站点还讨论了高估启发式算法的影响)
Your connectivity is the 8-neighbourhood, for which there is a better heuristic than Euclidean distance. Note that a path cannot have an arbitrary angle, it has to go straight or at a 45 degree angle, so Euclidean distance underestimates the distance even in the absence of obstacles. That is OK for correctness, but you can use the "diagonal distance" heuristic: (taken from here and easy to adapt to Python - that site also discusses the impact of having an overestimating heuristic)
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
您将有 D = 1, D2 = sqrt(2) 来匹配您的欧几里德距离度量.
You would have D = 1, D2 = sqrt(2) to match your Euclidean distance metric.
如果多条路径共享一个源或目标，则有一些技术可用于重用某些工作(无论哪个都无关紧要，因为它无论如何都是对称的).例如，当您从 A 搜索到 B 时，G 分数可以存储在网格中(它们甚至可以被排除在节点之外).然后在搜索通向 A 的路径时，那些保存的 G 分数代表到 A 的实际距离.显然，可以使用这些来获得完美的启发式方法，但还有更快的用法:如果从队列中抽取使用这种完美启发式计算其 F 的节点，然后最短路径肯定通过该节点(因为它的 F 是实际长度路径，而且它显然是从优先队列中出来以来最短的)，而且，您无需进一步搜索就知道该路径(贪婪地按照保存的 G 分数返回 A).
There are some techniques that can be used to re-use some work if multiple paths share a source or destination (it doesn't matter which since it's symmetric anyway). For example, as you search from A to B, the G scores can be stored in a grid (they can even be left out of the nodes). Then on a search for a path towards A, those saved G scores represent the real distances to A. Obviously these could be used in order to have a perfect heuristic, but there is an even faster use: if a node that used such a perfect heuristic to calculate its F is drawn from the queue, then the shortest path is definitely through that node (since its F is the actual length of the path, and it is apparently the shortest since it came off of the priority queue), and moreover, you know the path with no further search (greedily follow the saved G scores back to A).
这会导致每次搜索路径都会建立信息，这些信息可用于另一个方向的其他搜索.在另一个方向上的搜索然后再次为在那个另一个方向上的搜索建立信息，依此类推.应该小心 - 很容易让内存使用爆炸.可能并非所有信息都可以保留.
What this leads to is that every search for a path builds up information that can be used for an other search in the other direction. That search in the other direction then builds up information again for searches in that other direction and so forth. Some care should be taken - it is very easy to let the memory use explode. Likely not all information can be kept around.
这可能也可以与 Jump Point Search 结合使用，但要保存的 G 会更少，所以它可能不是很有效，主要是浪费了大量空间.
This can probably be combined with Jump Point Search as well though there would be fewer G's to save so it's probably not very effective, mostly wasting a bunch of space.
这篇关于A星算法:距离启发式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
