我使用的是A星算法，如下所示(取自http://code.activestate.com/recipes/578919-python-a-pathfinding-with-binary-heap/)，但我有个问题不明白。
这里给出的启发法是两点之间距离的平方。我发现，如果我取它的平方根，我的结果会更准确，但函数的运行时间会急剧增加(也就是说，它比以前经历了更多的循环)。
为什么启发式的变化会使它更准确，运行时间更长？
# 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))
为什么启发式的变化会使它更准确，运行时间更长？
第一个启发式方法，距离平方法，高估了实际距离(根据情况，高估了很多)，尽管实际距离是以相同的方式计算的，因为实际距离是按单步的和计算的(平方和小于和的平方)。A*往往会因为没有进行足够的探索来保证找到最佳路线而对此做出回应，它更喜欢继续遵循它正在尝试的任何路线，因为离目标更近一步会使它的预期距离减少很多(比步骤本身要大得多，因为启发式高估了太多)。它通常不会备份(即从队列中取一些以前打开的节点，而不是最近的节点)并尝试其他方法，因为返回意味着H值的上升大于G值的下降。
所以这有两个效果：
- 它通常要快得多(除了在某些迷宫中，你可以"欺骗"算法使其走错路的时间比其他情况下要长)
- 它不一定能找到最佳路线
你的连通性是8-邻域，对于它有比欧几里得距离更好的启发式方法。请注意，一条路径不能有任意的角度，它必须是直线或45度角，因此即使在没有障碍物的情况下，欧几里得距离也会低估距离。这对正确性来说是可以的，但你可以使用"对角线距离"启发式：(从这里开始，很容易适应Python——该网站还讨论了高估启发式的影响)
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)来匹配您的欧几里得距离度量。
如果多个路径共享一个源或目标，则可以使用一些技术来重用某些工作(不管是哪一个，因为它是对称的)。例如，当您从A到B搜索时，G分数可以存储在网格中(甚至可以将它们排除在节点之外)。然后，在搜索通往a的路径时，这些保存的G分数表示到a的真实距离。显然，这些分数可以用来进行完美的启发式，但还有一个更快的使用：如果使用这种完美启发式来计算其F的节点是从队列中提取的，那么通过该节点的最短路径肯定是(因为它的F是路径的实际长度，而且它显然是从优先级队列中出来后最短的)，而且，你知道不需要进一步搜索的路径(贪婪地按照保存的G分返回A)。
这导致了每次对路径的搜索都会积累信息，这些信息可以用于其他方向的其他搜索。然后，在另一个方向上的搜索再次为在该其他方向上的检索建立信息，依此类推。应该小心——很容易让内存使用爆炸。可能并非所有信息都可以保存。
这可能也可以与跳转点搜索相结合，尽管要保存的G会更少，所以它可能不是很有效，主要是浪费了大量空间。