Как можно эффективно изменить алгоритм A*, чтобы обеспечить n-й кратчайший путь?
Как можно эффективно изменить алгоритм A*, чтобы обеспечить, например, 2-й или 8-й кратчайший путь, а не первый?
2 ответа
Если это вообще возможно, я предлагаю вам сделать так, чтобы ваша программа выглядела как проблема кратчайшего пути, к которой относится Dijkstra, а затем использовать один из ответов, на которые вы уже указали, чтобы найти k-й кратчайший путь в этой ситуации, такой как Алгоритм Эппштейна и алгоритм Йена для k кратчайших путей.
Но есть и другой подход. Существует общий метод нахождения K-го лучшего ответа на комбинаторные задачи путем добавления дополнительных ограничений, которые позволяют разбить дерево решений. Он известен как Lawler-Murty и описан, например, в разделе 2 http://www.vldb.org/pvldb/vol4/p1028-golenberg.pdf
Вы должны проверить алгоритм K *. Он был опубликован в статье под названием: "K *: Эвристический алгоритм поиска для нахождения k кратчайших путей". Эта статья была опубликована в исследовательском журнале "Искусственный интеллект" в 2011 году (один из самых престижных в данной области), поэтому, насколько я знаю, она является своего рода современным для того, что вы ищете.
Если вы использовали алгоритм с согласованной эвристикой, то он имеет асимптотическую сложность в худшем случае O(m + n log(n) + k) во время выполнения и в пространстве (где n - количество вершин, а m - количество ребер в графе).).