Почему моя реализация A * медленнее, чем наводнение?

У меня есть пустая сетка из 100, 100 плиток. Начальная точка (0,0), цель (99,99). Плитки - это 4-сторонние соединения.

Мой алгоритм наводнения находит самый короткий путь в 30 мс, но моя реализация A * примерно в 10 раз медленнее.

Примечание. A * последовательно медленнее (3 - 10x), чем моя заливка, независимо от размера сетки или макета. Поскольку наводнение простое, я подозреваю, что в * отсутствует какая-то оптимизация.

Здесь функция. Я использую 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

Ответ 1