为什么我的A*算法实现比洪水填充算法慢？

Question

我有一个100x100的网格，起点为(0,0)，终点为(99,99)。每个格子有四个相邻格子。

我的泛洪算法可以在30毫秒内找到最短路径，但是我的A*实现要慢大约10倍左右。

注意：无论网格大小或布局如何，A*始终比我的泛洪算法慢（3-10倍）。因为泛洪算法比较简单，所以我怀疑我在A*中缺少某种优化。

以下是函数代码。我使用Python的heapq来维护一个按f值排序的列表。'graph'包含了所有节点、目标、邻居和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

- cyrus

---

你能展示一下 remove_from_heap 吗？那可能是你的瓶颈。 - templatetypedef

你的 set_f 函数是什么？也许你有一个不好的启发式算法？ - templatetypedef

添加了 set_f - 它是一个基本的曼哈顿距离。 - cyrus

你尝试使用过cProfile吗？python -m cProfile myscript.py这将至少告诉你程序花费了多少时间。 - mojo

@mojo 哇，这非常有帮助。看起来它正在检查每个节点 - 不确定为什么会这样做。我猜这是启发式的原因，但不确定为什么 - 这只是一个简单的曼哈顿距离？ - cyrus

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 倍，使其比泛洪算法更快。

- cyrus