Помогите с выбором алгоритма(найти все ходы на карте лабиринта)

Дана карта вида(задаётся любая в файле)
S ***| нужно найти все всевозможные проходы
**F | от старта(S) до финиша(F) и выдать
* | их на консоль.* - это стены лабиринта.
**|
END

0

карта корява вышла(она должна быть прямоугольная)
yariy

0

Есть такая технология 'Теория конечных графов' достаточно нудная , но дает алгоритм для поиска наикротчайших путей, в принципе алгоритмы одного нет, но есть интересные книги по этой теме....

'Теория конечных графов' изд.Наука М. 1974 год

P.S. только это не программирование в чистом виде это математический пакет для подобных задач

Вот есть описание рекурсивного алгоритма:
http://newasp.omskreg.ru/intellect/f25.htm
А вот варинат исполнения:
http://slava.bip.ru/works/progs/index.htm

0

Поищите в любом поисковике backtracking и 'перебор с возвратом'. Оптимальное решение это даст вряд ли, но алгоритмы вы отыщете. Вообще имеет смысл почитать, например Н.Вирта 'Алгоритмы + Структуры Данных = Программы' (в этой книге нет лабиринтов, но рекурсия вообще и backtracking в частности описаны превосходно). Правда достать эту книгу ну очень сложно.
Есть еще одна (более техническая) книга: Рейнгольд Э. Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. Это вообще кладезь идей и алгоритмов, но тоже редкость.
Блин, печатают всякую дрянь типа 'С++ за 21 день' или 'SQL для чайников'. Лучше бы переиздали то, что действительно нужно (крик души) ((

0

Алгоритмы расчитанные на 'интелектуальный' перебор всех вариантов мне кажутся утопичными, 'ГРАФЫ' позволяют сразу же обнаружить все варианты и выбрать оптимальный. главное воткнуть в сами расчеты АНАЛИТИКУ , и статистику результатов.....

Действительно, книг таких уже не издают. Я такие книге ищу в библиотеках или в БУКИНИСТИЧЕСКИХ отделах. Вот про графы ... искал пять дней, но нашел только в доме Технической книге.

Вышла неплохая книжка

Род Стивенс. Visual Basic. Готовые алгоритмы

То, что изложение ведется на бейсике, совершенно не важно. В книге излагаются алгоритмы. Тут и очереди, и деревья, и сортировка. Ее можно скачать из сети в формате Word. Нужно зайти на страничку:

http://infocity.kiev.ua/

В меню выбрать 'программирование' потом 'бейсик' и искать по слову 'Готовые'

0

Если лаборинт без разомкнутых стен то можно применить правило правой
или левой руки для выхода из лабиринта. Лабиринт задать матрицей и
постоянно проверять чтобы слева или справа была постоянно стена.
Если приходишь на начало лабиринта то точки выхода нету.

Если лаборинт без разомкнутых стен то можно применить правило правой
или левой руки для выхода из лабиринта. Лабиринт задать матрицей и
постоянно проверять чтобы слева или справа была постоянно стена.
Если приходишь на начало лабиринта то точки выхода нету.

Если лаборинт без разомкнутых стен то можно применить правило правой
или левой руки для выхода из лабиринта. Лабиринт задать матрицей и
постоянно проверять чтобы слева или справа была постоянно стена.
Если приходишь на начало лабиринта то точки выхода нету.

Если лаборинт без разомкнутых стен то можно применить правило правой
или левой руки для выхода из лабиринта. Лабиринт задать матрицей и
постоянно проверять чтобы слева или справа была постоянно стена.
Если приходишь на начало лабиринта то точки выхода нету.

Если лаборинт без разомкнутых стен то можно применить правило правой
или левой руки для выхода из лабиринта. Лабиринт задать матрицей и
постоянно проверять чтобы слева или справа была постоянно стена.
Если приходишь на начало лабиринта то точки выхода нету.

Предлагаю следующее (классическое) решение.
Лабиринт можно нехитрым образом представить в виде графа: клетки - вершины, если из одной клетки можно перейти в другую, то соответствующие вершины связаны ребром. После чего на данном графе запискается алгоритм поиска в ширину или в глубину. Если в ширину - получим оптимальный (по длине) путь, если в ширину - в среднем в два раза быстрее, но полученный путь не обязательно оптимальный. В случае более хитрых лабиринтов можно использовать алгоритма Дейкстры, Уоршала-Флойда (для поиска всех путей), А*...
Для информации можно посмотреть любую приличную книжку по теории графов/дискретной математикеке/computer science. К примеру: Ахо, Ульман '...Эффективные алгоритмы', Кормен и др. 'Алгоритмы: пострение и анализ', Липский 'Комбинаторика для программистов', Ф.Новиков 'Дискретная математика для программистов' и т.д.
Backtracking для обхода лабиринта - порядочное извращение для людей, не понимающих графовой природы данной задачи.

0