Генерация лабиринтов с помощью алгоритмов поиска в глубину и Краскала

Суть задачи сводится к построению остовного дерева на плоской сетке ячеек. Ты разберешь два математических подхода, напишешь программный код для генерации, измеришь скорость вычислений на разных масштабах и визуализируешь результат.

Математическая модель лабиринта как графа

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

Реализация двух принципиально разных алгоритмов

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

• Рандомизированный поиск в глубину (DFS) с использованием явного стека для отслеживания пути и возврата назад при попадании в тупик.
• Рандомизированный алгоритм Краскала с массивом всех возможных внутренних стен и последовательным их удалением.
• Структура данных Disjoint Set Union (DSU) с эвристиками сжатия путей и объединения по рангу, которая предотвращает появление циклов в методе Краскала.
• Блок фиксации времени выполнения с помощью функции time.perf_counter() для сбора точных метрик.

Сравнительный анализ геометрии и производительности

Алгоритмы создают структуры с кардинально разным характером коридоров. Метод DFS дает длинные извилистые маршруты с глубоким затягиванием и редкими развилками. Алгоритм Краскала создает древовидную структуру с высокой плотностью коротких тупиков, равномерно распределенных по площади. Сравни их по трем параметрам на размерах сеток 20 на 20, 50 на 50 и 100 на 100 ячеек. Оцени время работы, среднюю длину тупика и процент площади, занимаемый тупиковыми ветвями.

Что оценивает преподаватель в этом проекте

Преподаватель информатики оценивает корректность математической базы и чистоту программной архитектуры. Важно продемонстрировать понимание асимптотической сложности O(V + E) для DFS и почти линейной O(E log* V) для Краскала с DSU. В проекте смотрят на отсутствие утечек памяти, отделение алгоритмической логики от графики и статистическую достоверность замеров, сделанных минимум по 10-20 прогонам для каждого размера поля.

Источники для теоретической и практической базы

Для теории остовных деревьев и структур непересекающихся множеств опирайся на профильные разделы книги Томаса Кормена «Алгоритмы: построение и анализ». Для понимания практической специфики генерации лабиринтов изучи книгу Джамиса Бака «Mazes for Programmers». Исходные спецификации и документацию по работе со стеком и структурами данных бери на официальном портале python.org.