В ответе есть две вещи для обсуждения.Первый - это алгоритмическая эффективность.Второй - параллелизм.
Существует исследовательская статья , которая изучает этот случай и создает вариант A *, DEA *.Он использует дешевую допустимую эвристику стоимости ребра, чтобы получить нижнюю границу стоимости преемников, а затем вычисляет фактическую стоимость ребра только тогда, когда показано, что преемник может быть на оптимальном пути.
Обычно A * расширяет узел путем (1) генерации преемников с их новой f-стоимостью и (2) размещения их в открытом состоянии.Алгоритм DEA * (1) генерирует преемников с оценочными (нижними границами) f-затратами и (2) размещает их в открытом состоянии.Если состояние удаляется из открытия только с оценкой f-стоимости, вычисляется точное ребро / f-стоимость, и состояние возвращается в состояние открытия.
Это вариант общей идеи Частичное расширение и другие работы также исследовали проблему дорогостоящих ребер.
В этой модели вы можете избежать вычисления многих дорогих ребер, что полезно.Но было бы полезно вычислить оставшиеся ребра параллельно.В зависимости от точной стоимости, есть много способов сделать это.Если ваш открытый список является многопоточным, он может вычислять крайние затраты каждый раз, когда добавляется состояние для открытия.Но было бы более эффективно иметь по существу две очереди с приоритетами.
Одна очередь с приоритетами будет содержать состояния с вычисленными их граничными затратами, а другая будет содержать те, которые требуют выполнения вычислений.Параллельный код может быть написан так, чтобы он брал состояния из очереди второго приоритета и вычислял их граничные затраты, добавляя их в первую очередь, когда они завершены.Затем обычная программа может обрабатывать состояния из первой очереди в обычном порядке приоритетов.
Ключевым моментом является то, что параллельная часть может сосредоточиться на вычислении граничных затрат для состояний, которые должны быть расширены в следующем, вместо выполнениявсе состояния по мере их добавления в очередь.
Обратите внимание, что такой процесс может привести к исследованию более длинного пути, прежде чем будет обнаружен более короткий путь.Таким образом, вам нужно отслеживать, когда вы найдете более короткий путь к состоянию (при открытом или закрытом), и убедитесь, что вы перемещаете состояния из закрытого спина в открытое, когда обнаруживается более короткий путь.
Относится к этому, вы не можете завершить работу, когда найдете решение - оно не обязательно будет оптимальным.Вам необходимо завершить расширение всех состояний, в которых f-стоимость ниже, чем найденное вами решение.(Вы можете отказаться от любых состояний, стоимость решения которых больше или равна стоимости вашего найденного решения.) [Обратите внимание, что я дал общее руководство по хорошим подходам здесь;если вы застряли на конкретных деталях, вы можете попросить разъяснений.]