как найти три лучших маршрута, используя алгоритм A *

Question

В A * обычно получаемый результат - только один путь. Возможно ли, однако, для данного источника и пункта назначения иметь 3 рекомендуемых пути в соответствии с A *? Таким образом, второй возвращаемый путь - второй лучший путь, а третий - третий лучший путь.

Я думал о том, чтобы как-то изменить эвристику, чтобы отразить этот второй и третий лучший путь. Что вы, ребята, думаете?

UPDATE: Моя реализация на PHP, и я использую закрытый набор. Так что, если есть способ сделать это, дайте мне знать.

Answer 1

Это можно сделать довольно легко, если на вашем языке есть поддержка возврата / генераторы / итераторы / сопрограммы.

# Python code
def astar(start):
    q = [start]    # priority queue
    while len(q) > 0:
        node = heappop(q)
        if isGoal(node):
            yield node
        for x in successors(node):
            heappush(q, x)

Ключевое слово yield похоже на return, за исключением того, что функция может бытьповторно введен после yield, чтобы получить следующее решение.Чтобы получить лучшие три:

solutions = []
i = 0
for sol in astar(start):
    solutions.append(sol)
    if i == 3:
        break
    i += 1

Однако , это не будет работать, если вы используете закрытый набор (то есть, Russell & Norvig ' график поиска алгоритм), поскольку с тех пор часть неоптимальных решений может быть "обрезана" при поиске оптимального.