Здравствуйте читатели, сегодня я покажу свою реализацию лабиринта и пяти алгоритмов поиска на языке Python.
Первые шаги
Первое что необходимо сделать - сгенерировать лабиринт. Как вы можете видеть генерация происходит по простому алгоритму.
Но это не все, нужно еще и отобразить наш алгоритм, для этого подключим необходимую библиотеку - "matplotlib.pyplot" и напишем функцию для отображения нашего лабиринта в красивой цветной форме. Ниже представлен код отображения и подключенных библиотек.
Заканчивая первый шаг, сделаю вам красивый скриншот полученного лабиринта, и соответственно, код использования, что бы вы мои дорогие, могли легко его применить на практике! Уточняю зеленый квадрат - точка старта лабиринта, а серый - это его конец.
Алгоритмы поиска
Теперь когда у нас есть лабиринт, есть его отображение и есть большое желание его пройти, напишем алгоритмы поиска для нашего лабиринта. Как вы могли заметить в кодах, которые написаны выше имеется некий параметр path, обозначающий путь. Он представляет собой массив координат, которые собственно представляют путь от точки старта, до точки конца. Теперь нам нужно как то выяснить этот путь. Для этого используем алгоритмы поиска.
В этой статье будет представлено 5 алгоритмов поиска: поиск в ширину, поиск в глубину, случайный поиск, A* и поиск лучшего варианта. Сразу скажу что объяснять алгоритмы эти, я не буду. Вся информация о них есть в интернете, я представляю только свою реализацию. Демонстрация работы поиска будет представлена на статическом лабиринте. Это сделано что бы наглядно продемонстрировать работоспособность и время их выполнения. Так же для этого будет использована функция, которая поможет нам выяснить время выполнения алгоритма. Данная функция представлена ниже.
Поиск в ширину
Поиск в глубину
Случайный поиск
Для случайного поиска необходимы 2 дополнительные функции, они помогают выбрать случайное значение на основе предыдущего и не попасть на преграду. И так как скриншот в данном случае будет слишком нечитаемым - так как путь слишком большой, напишу только время выполнение = 0.0016473000000001292 сек
Поиск A*
В этом поиске используется дополнительный класс Node_for_a, если вы прочитаете что это за поиск, вам станет ясно для чего этот узел нужен. Прошу заметить, путь в этом поиске - такой же как и в поиске в ширину, оптимальный. На других примерах пути могут отличаться!
Поиск лучшего варианта
Прошу заметить, тут тоже путь такой же как в поиске в ширину - оптимальный. В других лабиринтах путь может быть другим!
Заключение
Мы реализовали лабиринт, его отображение и алгоритмы поиска на языке программирования Python. Если у кого то остались вопросы по этой работе, спрашивайте в комментариях. Желаю успехов в учебе!