Поэтому я подумал, что этот (хотя и несколько базовый) вопрос относится к следующему:
Скажем, у меня есть график размером 100 узлов, расположенных в виде шаблона 10x10 (подумайте, шахматная доска). График является ненаправленным и невзвешенным. Перемещение по графику включает перемещение трех пробелов вперед и одного пробела вправо или влево (аналогично тому, как шахматный рыцарь движется по доске).
Учитывая фиксированный начальный узел, как найти кратчайший путь к любому другому узлу на плате?
Я предполагал, что между узлами, которые являются жизнеспособными движениями, будет только ребро. Итак, учитывая эту информацию, я бы хотел найти кратчайший путь от начального узла до конечного узла.
Первоначально я думал, что каждое ребро взвешено с весом 1. Однако график не является ориентированным, поэтому Джикштрас не будет идеально подходить. Поэтому я решил сделать это, используя измененную форму поиска в глубину.
Однако я не мог представить себе, как получить кратчайший путь, используя поиск.
Еще я попробовал поместить граф в древовидную форму с начальным узлом в качестве корня, а затем выбрать самый мелкий (самый низкий номер строки) результат, который дал мне желаемый конечный узел ... это работало, но было невероятно неэффективно, и поэтому не будет работать для большего графика.
У кого-нибудь есть идеи, которые могли бы указать мне правильное направление на этот?
Большое спасибо.
(Я пытался визуализировать график, но не смог из-за своей низкой репутации)
O(|E|)
, в то время как у Дейкстры естьO(|E| + |V|log(|V|)
.O(mn)
то время как BFSO(V + E)
Николай уже дал идеальный ответ. Однако позвольте мне остановиться на вашей первоначальной попытке использовать поиск в глубину.
Во-первых, либо Dijkstra (который отлично работает с невзвешенными узлами, как отметил Николас Манкузо), либо поиск в ширину приводят к экспоненциальной трате вашей памяти. Однако их преимущество заключается в том, что они никогда не расширяют узлы, пока они гарантированно найдут оптимальные решения. К сожалению, их ограничение весьма важно, и не следует ожидать, что они будут разумно расширяться.
Ура,
источник