Молодежь и наука - третье тысячелетие: Материалы студенческой научно-практической конференции с международным участием

284 А. О. Янтиков Факультет математики, физики и информатики, IV курс (очная форма обучения) Научный руководитель – Е. Г. Торина О НЕКОТОРЫХ ПОДХОДАХ К РАЗРАБОТКЕ ПРОГРАММЫ ГЕНЕРАЦИИ ЛАБИРИНТОВ Происхождение задачи о лабиринтах относится к глубокой древности и до сих пор не раскрыта тайна появления лабиринтов. Возможно, этот образ был подсказан самой природой – спиралевидные и лабиринтные формы характерны для раковин некоторых моллюсков, они различимы в колонии кораллов, в под- земных ходах муравейников. В русском языке слово появилось в начале XVIII века. Латинский вариант заимствован из греческого, предполагается, что «лабиринт» происходит от таких слов и словосочетаний, как «узкая улица», «ущелье», «переулок». В переносном смысле слово «лабиринт» означает «сложное и запутанное положение, из кото- рого трудно найти выход». Существует теория, согласно которой термин «лаби- ринт» первоначально обозначал танец. Движения в этом танце подчинялись строгой графической схеме. Лабиринты во все времена были загадочными и за- манчивыми объектами, привлекали внимание ученых. В настоящее время лаби- ринты – это не только самостоятельный класс игр, они являются основой для со- здания локаций не только в других играх, но и в практических задачах, связанных, например, с навигацией, моделированием движения роботов и т. п. Каждый лабиринт представляет общий план с заданной схемой движения округ- лой или прямоугольной формы или же формы многоугольника. В лабиринте только один вход, он же выход. Должны соблюдаться следующие обязательные условия: — дорожка постоянно изменяет направление движения; — дорожка заполняет все внутреннее пространство лабиринта; — неизбежно выводит к центру, где и заканчивается; — вернуться к месту входа можно только по этой же самой дорожке. Лабиринт в математике это граф. Графом называют фигуру, состоящую из точек и линий. Точки называют вершинами, а линии – ребрами графа. Исследо- вать лабиринт, значит найти путь в этом графе. Все тупики и перекрестки счи- таются вершинами графа, а коридоры лабиринта – это ребра графа. Как пред- ставить лабиринт в памяти компьютера? Достаточно просто создать двумерный массив (рис.1). Рис. 1. Простое представление лабиринта в памяти компьютера