Цель работы

В этом задании я сделал программу для поиска пути в лабиринте. Лабиринт загружается из текстового файла, после этого для него запускаются три алгоритма: BFS, DFS и A\*. Нужно было сравнить как они проходят разные карты



&#x20; В файле maze.py находится описание лабиринта. Cell отвечает за отдельную клетку, а Maze хранит всю карту, старт, финиш и умеет находить соседние клетки, куда можно идти. Для загрузки карты из файла сделан MazeBuilder. Он читает строки, проверяет их длину и ищет точки S и F. \[тут я столкнулся с ошибкой на hard.txt, потому что одна строка была другой длины]

&#x20; В файле solver.py находится поиск пути.MazeSolver получает стратегию поиска и запускает её. Были сделаны три стратегии: BfsStrategy, DfsStrategy и AstarStrategy. BFS идёт в ширину, DFS идёт в глубину, а A\* использует расстояние до финиша

&#x20; Сначала программа проверялась на simple.txt, потом были добавлены medium.txt и hard.txt. Для каждой карты запускались все три алгоритма. Программа выводила найденный путь, количество посещённых клеток и длину пути

&#x20; Для замеров сделан файл zamery.py. Он запускает алгоритмы по 5 раз и сохраняет результаты в results.csv

&#x20; Результаты

simple.txt; BFS; время 0.00001532; посещено 9; длина пути 5

simple.txt; DFS; время 0.00000710; посещено 5; длина пути 5

simple.txt; A\*; время 0.00001304; посещено 5; длина пути 5



medium.txt; BFS; время 0.00003650; посещено 29; длина пути 29

medium.txt; DFS; время 0.00003346; посещено 29; длина пути 29

medium.txt; A\*; время 0.00004344; посещено 29; длина пути 29



hard.txt; BFS; время 0.00004418; посещено 38; длина пути 19

hard.txt; DFS; время 0.00002262; посещено 19; длина пути 19

hard.txt; A\*; время 0.00003804; посещено 25; длина пути 19



&#x20; По результатам видно, что на простом лабиринте разница почти не важна. На medium.txt все алгоритмы прошли примерно одинаково. На hard.txt разница заметнее: BFS посетил больше всего клеток, DFS меньше всего, а A\* оказался между ними. При этом длина пути на hard.txt у всех получилась одинаковая

&#x20; Заключение

В работе получилось сделать загрузку лабиринта из файла и несколько способов поиска пути. BFS надёжный, но может обходить больше клеток. DFS простой и иногда быстро доходит до финиша, но зависит от формы лабиринта. A\* старается идти ближе к цели, но на маленьких картах его преимущество не всегда видно.В целом задание было понятнее когда появились карты и путь стал выводиться прямо в консоли. Самая заметная проблема была с неправильной строкой в hard.txt, но после исправления все карты начали нормально запускаться

