Можно ли использовать A * поиск несетевых графов

Question

Я знаю, что A * - наиболее оптимальный алгоритм поиска кратчайшего пути, но я не вижу, как любая эвристика может работать на нерешетном графе? Это заставило меня задуматься, действительно ли A * можно использовать на неориентированном или направленном графе. Если A * способен это сделать, какой эвристический подход можно использовать? Если A * нет, то каков текущий самый быстрый алгоритм для вычисления кратчайшего пути на направленном или неориентированном графике без решетки? Прокомментируйте, если требуется дополнительная информация.

Answer 1

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

Если вы планируете создать кратчайший путь с одним источником (SSSP), где вы пытаетесь найти кратчайший путь от одного узла к другому, а ваш график невзвешен, вы можете использовать Breath-First-Search. Двунаправленная версия этого алгоритма хорошо работает на практике. Если вы выполняете SSSP и ваш график взвешен, алгоритм Дейкстры является общим выбором, и двунаправленная версия может быть использована. Для всех пар кратчайшего пути полезны другие алгоритмы, такие как алгоритм Флойда-Варшалла или Джонсона.

Если вы хотите использовать эвристику и оценить расстояние до начала поиска, вы можете выполнить предварительные вычисления, которые в основном применимы к каждому из описанных выше алгоритмов. Некоторые примеры:

• расчет ярлык (ARC-Flags, SHARC, KFlags)
• идентификации хаб (также Transite узлы): предварительно вычислить расстояния между всеми узлами ступиц (должно быть сделано только один раз в не динамических графиков) , найдите следующий источник источника и приемника, например с дийкстра. увеличить расстояние между концентраторами и источником до следующего концентратора и раковиной до следующего концентратора
• структурированные таблицы поиска, например. расстояние между концентраторами и расстояния между узлом узлов на определенном расстоянии. После предварительного расчета вам больше не нужно переходить на график, вместо этого ваш расчет кратчайшего пути - это ряд поисковых запросов. это приводит к высокому потреблению памяти, но высокой производительности. Вы можете настроить память, используя верхние приближения для расчета расстояния.

Я настоятельно рекомендую вам определить ваш конкретный случай и провести некоторое исследование алгоритмов графа, хорошо подходящих для этого. Много исследований проводится в кратчайшем пути для десятков областей применения.