明星算法：距离启发式

Question

我正在使用这里看到的 A 星算法（取自 http://code.activestate.com/recipes/578919-python-a-pathfinding-with-binary-heap/），但我有一个问题我不明白。

这里给出的启发式是两点之间距离的平方。我发现如果我取它的平方根，我的结果会更准确，但是函数的运行ning 时间会显着增加（即它比以前经历了很多很多的循环）。

为什么启发式的变化会导致它更准确，并且需要更长的时间才能运行？

# 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))

Answer 1

Why does the change in heuristics cause it to be more accurate, and take longer to run?

第一个启发式算法，距离平方，高估了实际距离（根据情况高估了很多），即使实际距离的计算方式相同，因为实际距离计算为单个步骤的总和（平方和小于和的平方）。 A* 倾向于通过探索不足以保证找到最佳路线来对此做出回应，它更愿意继续沿着它尝试的任何路线前进，因为离目标更近一步会使到它的预期距离减少 lot（比步骤本身多得多，因为启发式高估了太多）。它通常不会备份（即从队列中取出一些先前打开的节点而不是最近的节点）并尝试其他东西，因为返回意味着 H 值上升超过 G 值下降。

所以这具有您看到的两种效果：

它通常要快得多（除了在某些迷宫中，您可以 "trick" 算法在错误的方向上运行的时间比其他情况下更长）
不一定找到最佳路线

您的连通性是 8 邻域，对此有比欧氏距离更好的启发式方法。请注意，路径不能有任意角度，它必须笔直或呈 45 度角，因此即使没有障碍物，欧氏距离也会低估距离。这对于正确性来说是可以的，但是你可以使用 "diagonal distance" 启发式：（取自 here 并且很容易适应 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 分数可以存储在网格中（它们甚至可以被排除在节点之外）。然后在搜索 towards A 的路径时，那些保存的 G 分数代表到 A 的真实距离。显然，这些可以用来获得完美的启发式算法，但还有更快的使用：如果从队列中抽取使用这种完美启发式计算其 F 的节点，则通过该节点的最短路径肯定是（因为其 F 是 actual 路径的长度，而且它显然是最短的，因为它离开了优先级队列），而且，你知道没有进一步搜索的路径（贪婪地按照保存的 G 分数回到 A） .

这导致的是，每次搜索路径都会建立可用于另一个方向上的其他搜索的信息。另一个方向的搜索然后再次为 that 另一个方向的搜索建立信息，依此类推。应该小心一些——很容易让内存使用爆炸。可能并非所有信息都可以保留。

这可能也可以与跳跃点搜索结合使用，尽管要保存的 G 会更少，所以它可能不是很有效，主要是浪费了一堆 space。

明星算法：距离启发式

A star algorithm: Distance heuristics

python

algorithm

a-star