Алгоритм выхода из лабиринта.
Доброго времени суток.
Есть следующая задача, требуется найти выход из лабиринта. Структура лабиринта и его размер не известны. В данной ситуации могут быть применимы алгоритмы Тремо и Правой(Левой) руки. Алгоритм Правой(Левой) руки не устраивает, так как не всегда гарантирует выход из лабиринта, мои старания для его модификации не обеспечили 100% гарантии выхода. Алгоритм Тремо не очень нравиться, так как не известен размер лабиринта.
Есть ли еще алгоритмы обеспечивающие 100% выход из лабиринта, при условии, что его структура не известна?(разумеется в случае, если выход существует) так же буду благодарен за ссылки на литературу, статьи, исходники и прочую информацию.
Есть следующая задача, требуется найти выход из лабиринта. Структура лабиринта и его размер не известны. В данной ситуации могут быть применимы алгоритмы Тремо и Правой(Левой) руки. Алгоритм Правой(Левой) руки не устраивает, так как не всегда гарантирует выход из лабиринта, мои старания для его модификации не обеспечили 100% гарантии выхода. Алгоритм Тремо не очень нравиться, так как не известен размер лабиринта.
Есть ли еще алгоритмы обеспечивающие 100% выход из лабиринта, при условии, что его структура не известна?(разумеется в случае, если выход существует) так же буду благодарен за ссылки на литературу, статьи, исходники и прочую информацию.
Цитата: Artem_3A
Есть ли еще алгоритмы обеспечивающие 100% выход из лабиринта, при условии, что его структура не известна?
Первое что пришло на ум - это поиск с возвратом, по аналогии с задачей обхода конем шахматной доски.
Можно модифицировать алгоритм руки таким образом, что если обнаруживаем зацикленность в действиях, то возвращаемся на один перекресток назад.
Цитата: Artem_3A
Есть ли еще алгоритмы обеспечивающие 100% выход из лабиринта, при условии, что его структура не известна?(разумеется в случае, если выход существует) так же буду благодарен за ссылки на литературу, статьи, исходники и прочую информацию.
Есть, например, рекурсивный обход и алгоритм волновой трассировки. Оба алгоритма описаны в книге Мозговой М. Занимательное программирование.
Я давным давно кодил. Вот исходники: labyrinth.zip
P.S. Да простит меня уважаемый kot_ за то, что слил исходники на фолдер тчк ру.