A星算法：距离启发式

Question

A星算法：距离启发式

6

我正在使用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))

- johannes

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

改变启发式函数为什么会使A*算法更准确但花费更长时间运行？

第一个启发式函数——距离平方，在计算实际距离时会高估真正的距离（取决于具体情况），尽管实际距离的计算方式相同，因为实际距离是通过单步累加得出的（平方和小于总和的平方）。A*算法往往不会探索足够的节点来保证找到最佳路径，而是偏向于沿着它正在寻找的路径前进，因为朝着目标迈出一步会使预期距离缩短很多（由于启发式函数高估得很多，比预计的多得多）。它通常不会回溯（例如从队列中取出先前打开的节点而不是最近的节点）并尝试其他方法，因为返回意味着H值上升的程度大于G值下降的程度。

因此，这样做会产生两个效果：

1.通常速度快得多（除了在某些迷宫中，你可以“欺骗”算法走错的路线比它本来要多）。 2.不一定能找到最佳路径。

对于连接性是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）。

这导致每次搜索路径都会积累可用于在另一个方向上搜索的信息。那个反方向的搜索再次为在那个反向的搜索积累信息，以此类推。应该注意一些关键问题 - 让内存使用爆炸非常容易。可能不能保留所有信息。

这可能也可以与Jump Point Search结合使用，但要保存的G更少，因此可能并不是非常有效，大多数情况下会浪费很多空间。