алгоритм обратного отслеживания для решения кратчайшего пути?

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

Так может ли кто-нибудь дать некоторые интернет-ссылки, которые укажут мне на некоторые ресурсы? Я это очень ценю.

* UPDATE: Любопытно, может ли алгоритм обратного отслеживания решить проблему самого короткого пути?

источник

2012-01-14 braindead

Это проводное устройство, которое вы указали для использования алгоритма backtracking algoritm, ведь алгоритм dijkstra SPFA или bellman-ford идеально подходит для решения вашей проблемы. Если вам нужно использовать backtracking, я боюсь, что вам удастся достичь плохой временной сложности. Просто попробуйте следующий сегмент дороги, и когда сумма ваших выбранных сегментов превысит «текущий самый короткий путь», начните обратный отсчет.

источник

2012-01-14 06:50:38 lai

Это отчет, назначенный мне специально для использования backtracking, поэтому у меня нет выбора. Не могли бы вы подробнее рассказать? Как я могу выбрать свой первый сегмент дороги? Просто случайно? затем попытайтесь отступить от стартового узла и попробовать другой путь? – braindead

Я думаю, что получил свою точку зрения на возвращение. Благодарю. – braindead

-1

Backtracking может решить его. Но это очень медленно ... Я думаю, вам нужен Dijkstra O (n^2), Dijkstra с кучей O (nlogn), Bellman-ford O (ne) или SPFA O (ke) (k≈2). Как для меня, я предпочитаю SPFA ...

источник

2016-01-25 11:29:07 ljt12138

алгоритм обратного отслеживания для решения кратчайшего пути?

ответ

Смежные вопросы