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

Question

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

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

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

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

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

Тем не менее, я не смог на всю жизнь визуализировать, как получить самый короткий путь, используя поиск.

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

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

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

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

Answer 1

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

Answer 2

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

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

Если вы хотите решить большие случаи использования вашей проблемы Итеративная глубина-в первую очередь Поиск (IDFS). Просто внесите поиск по глубине из своего начального состояния с максимальной глубиной, установленной на определенный порог, $ d_ {max} $. Если вы не нашли решение, то увеличьте глубину последней итерации фиксированной постоянной $ k $. Таким образом, в итерации $ i $ -6, поиск по глубине запускается по глубине $ d_ {max} + i times k $ (с первой итерацией пронумерована 0). Если $ d_ {max} = k = 1 $, вы гарантированно найдете оптимальное решение при использовании линейного памяти по глубине решения.

Ну, вы можете подумать, что повторная эксплуатация узлов-довольно плохая идея. Нисколько! Это то, что гарантирует линейное потребление памяти, в то время как итерация, доминирующая общее время работы, является лишь последним, так что можно доказать, что этот алгоритм попадает в накладные расходы $ frac {b} {b-1} $ с $ B $ является эффективным фактором ветвления, и это, безусловно, очень маленький штраф, который стоит учитывать при столкновении с тяжелыми проблемами.

Ваше здоровье,