Помогите, пожалуйста, очень нужен алгоритм исследования лабиринта. Суть задачи такова: робот попадает на неизвестную территорию, которая представляет собой замкнутый лабиринт произвольной формы. Робот "видит" только на шаг вперед, ему нужно исследовать все доступные для него ходы в лабиринте и по возможности не возращаться на уже исследованные места. Исследование должно пройти за оптимальное время. Роботов в задаче несколько и желательно было бы и несколько алгоритмов
Очень буду ждать ответа, а то сроки поджимают. Заранее спасибо!
Во-первых, есть самый простой алгоритм —
правило правой (левой) руки. Все время касаясь одной рукой одной стенки, двигаться вперед. Это означает, на каждом повороте сворачивать в одну сторону. У этого алгоритма есть куча недостатков: он исследует только ту связную компоненту лабиринта, к которой прислонили робота перед началом выполнения — но зато просто и методично. Если есть несколько связных компонент, то их можно выделить (на этом форуме уже обсуждалось, как именно) и к каждой в произвольной точке приставить по роботу, чтобы он ее обошел. При этом плюсом алгоритма является и то, что никакой памяти (отметок на стенах и т.д.) не нужно.
Во-вторых, есть универсальный алгоритм — "
правила Тремо", по идее, описанные
здесь. Читать сказки, к сожалению, времени нет, да и книжка, откуда я это почерпнул, уже тоже давно не под рукой, но суть где-то такая:
перед входом в каждый коридор ставить отметку у входа, и после выхода из коридора в перекресток тоже ставить отметку у выхода.
на перекрестке выбирать путь так: если перед каким-либо входом меньше двух отметок — идти туда. Если у каждого входа уже по две отметки — значит, обошли все.
А другие алгоритмы я забыл или не знаю
Здравствуйте, Marina_S, Вы писали:
M_S> Помогите, пожалуйста, очень нужен алгоритм исследования лабиринта. Суть задачи такова: робот попадает на неизвестную территорию, которая представляет собой замкнутый лабиринт произвольной формы. Робот "видит" только на шаг вперед, ему нужно исследовать все доступные для него ходы в лабиринте и по возможности не возращаться на уже исследованные места. Исследование должно пройти за оптимальное время. Роботов в задаче несколько и желательно было бы и несколько алгоритмов Очень буду ждать ответа, а то сроки поджимают. Заранее спасибо!
Можно поиском к ширину идти к ближайшей ниразведанной области.
Здравствуйте, Marina_S, Вы писали:
M_S> Помогите, пожалуйста, очень нужен алгоритм исследования лабиринта.
Предлагается комплект моих лаб. работ по алг.языкам : четыре разных алгоритма решения твоей задачи. Код на паскале и немножко безобразен, но общие идеи проглядываются
Надеюсь поможет
Брать тута :
http://rsdn.ru/File/21356/LABIRINT.ZIP
С уважением Леша
