Я знаю, что алгоритм A * может найти кратчайший путь. Но проблема в моей работе заключается в том, что мне нужно найти все кратчайшие пути. Точнее, могут существовать несколько кратчайших путей, но мне нужно выбрать кратчайший путь в порядке приоритета по часовой стрелке.Как найти все кратчайшие пути с помощью алгоритма A *?
Если я могу получить все кратчайшие пути, я могу получить одно (по часовой стрелке), которое я хочу.
Алгоритмы Дейкстры дают вам все кратчайшие пути. A * был сделан как улучшенный Dijkstra с дополнительными ограничениями. Улучшение было вам не нужно было посещать все узлы. Если вы хотите изучить все узлы (что обязательно, чтобы убедиться, что вы проверили все кратчайшие пути), тогда нет смысла использовать A *, просто придерживайтесь предка общего назначения
Вещь с A * алгоритмом является то, что он является полным и оптимальным. Это означает, что он найдет путь к решению, если существует путь, но также гарантирует, что он сначала найдет кратчайший путь.
Это происходит потому, что эвристический функция А * использование должно быть admissible heuristic; that is, it must not overestimate the distance to the goal.
Это, в свою очередь, гарантирует, что как только вы найти путь к решению, вы знаете, что нет пути короче что один в остальной части поискового пространства.
Предположим, что расстояние до вашего первого решения было d (проблема). Теперь, мое последнее заявление на самом деле означает, что если вы просто продолжать идти после того, как вы найдете первое решение д (проблема) и найти другое решение, d2 (проблема) Есть две возможности:
Таким образом, чтобы подвести итог: вы просто продолжать идти после того, как вы найдете первые оптимальных решений, и вы принимаете все решения, которые имеют такое же расстояние. Первый путь, который имеет худшее (более длинное) расстояние, отбрасывает и останавливает поиск.
Я только что видел «по часовой стрелке» часть вопроса. Вероятно, вы можете избежать поиска всех оптимальных решений путем как-то вставки по часовой стрелке -ness в эвристику или вашу стоимость. Например. трюк, который я использовал иногда: у вас есть стоимость как целое число, от 0 до inf. И затем вы добавляете компонент часовой стрелки, который может иметь значения реальных значений с интервалом [0, 1). Таким образом, где бы это ни было, a > b раньше, он останется таким, но отношение a == b может быть изменено, если компонент по часовой стрелке отличается.
Другой способ сравнения, если вы явно не хотите работать с числовым значением, должен иметь стоимость пары значений. Если первый компонент пары отличается по двум затратам на путь, вы просто сравниваете их. Если первые компоненты одинаковы, только тогда вы сравниваете второе значение в парах.
Тем не менее, я не уверен, что я посоветую вам изменить стоимость или вашу эвристическую функцию (или и то, и другое). Кроме того, я не уверен, что этот точный трюк будет работать в вашей проблеме, но я считаю, что вы должны быть в состоянии переместить алгоритм в сторону большинства решений по часовой стрелке, просто изменив одну из этих функций, если вы просто немного поиграете.
Большое спасибо, ваш метод поиска других кратчайших путей работает. Тем не менее, мне интересно, может ли ваш способ повернуть по часовой стрелке. Вот ситуация: – teloon
@teloon Похоже, вы ничего не писали после знака ':': D Если это вопрос по расширению, просто отредактируйте его в вопросе ... Если это выглядит как отдельная проблема, откройте новый вопрос и опубликовать ссылку в комментариях, чтобы я мог ее найти. – penelope
Простите, что ... Вот ситуация: расчетное расстояние намного больше, чем фактическое расстояние, тогда по часовой стрелке мало влияет на приоритет. Таким образом, он все еще может найти путь, который не является самым большим по часовой стрелке, но оценка расстояния намного ближе к фактическому значению. – teloon
Чтобы выяснить, что @penelope означает: «... просто продолжать идти после того, как вы найдете оптимальное решение первый ...»
Чтобы получить набор эквивалентных затрат оптимальных путей от A * :
После того, как A * нашел кратчайший путь (cost = C *), вы можете получить другие пути эквивалентной длины, продолжая выходить из списка OPEN, пока вы не столкнетесь с решением, которое стоит больше, чем C *. (есть предостережение, если ваша эвристика не идеальна, вам, возможно, придется выполнить дополнительную работу.) Обратите внимание, что это даст вам набор оптимальных путей, но не обязательно набор всех оптимальных путей - это зависит от как вы настроили дублирующее обнаружение.
Чтобы получить путь по часовой стрелке от А *:
Что касается предпочтения по часовой стрелке пути, рассмотреть возможность использования ничьи в методе сравнения для сортировки открытого списка. Если два кандидата имеют одну и ту же f-стоимость, предпочитайте тот, который больше всего по часовой стрелке. (Я думаю, вы можете получить представление о скорости по часовой стрелке, посмотрев на своих кандидатов относительно узлов старта/цели.) Если вы так перепутаете, по часовой стрелке решения будут выдвинуты в начало списка OPEN, и вы будете получить самое большое по часовой стрелке решение от A *.
Если вы можете измерить, как далеко идет «по часовой стрелке» путь (без сравнения с другими путями), вы можете просто заменить определение длины от * N шагов * до пары * N шагов, M% по часовой стрелке * и использовать одинаковые алгоритм поиска путей, но сравнивая пары вместо длин. – hamstergene
@hamstergene Да, в идеале я могу определить приоритет как сочетание расстояния L2 с приоритетом по часовой стрелке.Но на практике это сложно, потому что они в разных масштабах. – teloon