为什么我的A*实现速度比洪水慢？

Question

我有一个由100,100个瓷砖组成的空白格子。起点是(0,0)，目标是(99,99)。瓷砖是四通连接.

我的洪水填充算法在30毫秒内找到最短路径，但我的A*实现速度大约慢了10倍。

注:无论网格的大小或布局如何，A*总是比我的洪水慢(3-10倍)。因为洪水很简单，所以我怀疑我错过了A*的某种优化。

这是函数。我使用Python的heapq来维护一个f排序列表。“图”保存所有节点、目标、邻居和g/f值。

import heapq

def solve_astar(graph):

    open_q = []

    heapq.heappush(open_q, (0, graph.start_point))

    while open_q:

        current = heapq.heappop(open_q)[1]

        current.seen = True # Equivalent of being in a closed queue

        for n in current.neighbours:
            if n is graph.end_point:
                n.parent = current
                open_q = [] # Clearing the queue stops the process

            # Ignore if previously seen (ie, in the closed queue)
            if n.seen:
                continue

            # Ignore If n already has a parent and the parent is closer
            if n.parent and n.parent.g <= current.g:
                continue

            # Set the parent, or switch parents if it already has one
            if not n.parent:
                n.parent = current
            elif n.parent.g > current.g:
                remove_from_heap(n, n.f, open_q)
                n.parent = current

            # Set the F score (simple, uses Manhattan)
            set_f(n, n.parent, graph.end_point)

            # Push it to queue, prioritised by F score
            heapq.heappush(open_q, (n.f, n))

def set_f(point, parent, goal):
    point.g += parent.g
    h = get_manhattan(point, goal)
    point.f = point.g + h

Answer 1

这是个平局的问题。在空网格上，从(0,0)开始，再到(99,99)，就会产生许多f-得分相同的瓷砖。

通过在启发式中添加一个微小的提示，稍微靠近目的地的瓷砖将首先被选中，这意味着目标的实现更快，需要检查的瓷砖也更少。

def set_f(point, parent, goal):
    point.g += parent.g
    h = get_manhattan(point, goal) * 1.001
    point.f = point.g + h

这导致了大约100倍的改善，使它比洪水要快得多。