Кратчайший путь на неориентированном графе?

19

Поэтому я подумал, что этот (хотя и несколько базовый) вопрос относится к следующему:

Скажем, у меня есть график размером 100 узлов, расположенных в виде шаблона 10x10 (подумайте, шахматная доска). График является ненаправленным и невзвешенным. Перемещение по графику включает перемещение трех пробелов вперед и одного пробела вправо или влево (аналогично тому, как шахматный рыцарь движется по доске).

Учитывая фиксированный начальный узел, как найти кратчайший путь к любому другому узлу на плате?

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

Первоначально я думал, что каждое ребро взвешено с весом 1. Однако график не является ориентированным, поэтому Джикштрас не будет идеально подходить. Поэтому я решил сделать это, используя измененную форму поиска в глубину.

Однако я не мог представить себе, как получить кратчайший путь, используя поиск.

Еще я попробовал поместить граф в древовидную форму с начальным узлом в качестве корня, а затем выбрать самый мелкий (самый низкий номер строки) результат, который дал мне желаемый конечный узел ... это работало, но было невероятно неэффективно, и поэтому не будет работать для большего графика.

У кого-нибудь есть идеи, которые могли бы указать мне правильное направление на этот?

Большое спасибо.

(Я пытался визуализировать график, но не смог из-за своей низкой репутации)

gfppaste
источник

Ответы:

19

Если бы ребра на графике представляли только допустимые движения между определенными позициями, использование Дейкстры сработало бы очень хорошо. Однако, поскольку график невзвешенный, это будет излишним. Простой поиск в ширину даст оптимальный ответ.

Николас Манкузо
источник
оооооо человек, я даже не думал о BFS! благодаря тонну!
gfppaste
Как это излишне? может быть, реализация немного сложнее ничего.
Я также хотел бы добавить, что BFS более эффективен. BFS имеет O(|E|), в то время как у Дейкстры есть O(|E| + |V|log(|V|).
Даг Рэмси
@ user742 BFS быстрее, чем Djikstras. Джикстра в O(mn)то время как BFSO(V + E)
CodyBugstein
13

Николай уже дал идеальный ответ. Однако позвольте мне остановиться на вашей первоначальной попытке использовать поиск в глубину.

Во-первых, либо Dijkstra (который отлично работает с невзвешенными узлами, как отметил Николас Манкузо), либо поиск в ширину приводят к экспоненциальной трате вашей памяти. Однако их преимущество заключается в том, что они никогда не расширяют узлы, пока они гарантированно найдут оптимальные решения. К сожалению, их ограничение весьма важно, и не следует ожидать, что они будут разумно расширяться.

dмaИксКяdмaИкс+я×КdмaИксзнак равноКзнак равно1 тогда вы гарантированно найдете оптимальное решение при использовании линейной памяти по глубине решения.

бб-1б

Ура,

Карлос Линарес Лопес
источник