Теория программирования: решить лабиринт

Question

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

Базовая ситуация: У нас есть матрица, и элементы в этой матрице упорядочены таким образом, что она представляет собой лабиринт с одним входом и одним выходом.

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

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

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

Должны быть лучшие решения для отправки бота через лабиринт.

EDIT
Первое: спасибо за хорошие ответы!

Вторая часть моего вопроса: Что делать в случае, если у нас есть многомерный граф? Существуют ли специальные методы для этого, или ответ Джастина Л. можно использовать и для этого?
Я думаю, что это не лучший способ для этого случая.

Третий вопрос:
Какой из этих алгоритмов решения лабиринта является / является самым быстрым? (Чисто гипотетически)

Answer 1

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

Answer 2

Лучший способ решить лабиринт - использовать алгоритм подключения, такой как union-find, который представляет собой квазилинейный алгоритм времени, предполагающий сжатие пути.

Union-Find - это структура данных, которая сообщает, транзитивно ли связаны два элемента в наборе.

Чтобы использовать структуру данных объединения-поиска для решения лабиринта, сначала для соединения структуры поиска объединения используются данные о соседних соединениях. Тогда союзная находка сжимается. Чтобы определить, является ли лабиринт разрешимым, сравниваются входные и выходные значения. Если они имеют одинаковое значение, то они связаны, и лабиринт разрешим. Наконец, чтобы найти решение, вы начинаете со входа и изучаете корень, связанный с каждым из его соседей. Как только вы найдете ранее не посещенного соседа с тем же корнем, что и текущая ячейка, вы посещаете эту ячейку и повторяете процесс.

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

Answer 3

Этот алгоритм азкабана может также помочь вам, http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

Answer 4

Тот же ответ, что и на все вопросы о переполнении стека;)

Используйте vi!

http://www.texteditors.org/cgi-bin/wiki.pl?Vi-Maze

Это действительно увлекательно видеть текстовый редактор, решающий ascii-лабиринт, я уверен, что у ребят из Emacs есть эквивалент ..