Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Алгоритм обхода лабиринта на языке Python. Поиск всех путей
Сегодня интересный рекурсивный алгоритм. Часто встречающаяся задача обхода лабиринта. При этом могут быть разные конечные цели: найти нужное место в лабиринте, найти кратчайший (или все кратчайшие) путь до указанного места, найти все пути до указанного места в лабиринте, произвести обход лабиринта. Могут быть дополнительные условия, например, разный вес разных шагов в лабиринте. Также могут быть варианты движения: север, юг, запад, восток или с добавлением юго-востока, юго-запада, северо-востока, севера-запада. И т.д. Конечно, это всё задачи на графах, чаще всего решаемые рекурсивно.
Обычно при формализации задачи лабиринт изображается прямоугольником, разделённом на клетки. Каждая клетка может иметь своё содержание: свободное место, куда можно встать, фрагмент препятствия. Могут также самые разные дополнительные варианты. Например, для одной из олимпиад я придумал, что там могут быть мины. Тот кто двигался по лабиринту при вставании на мину, терял часть своей жизни. Но и при вставании на свободное место он также терял часть своей жизни, но скажем так, много меньше, чем при взрыве мины. Нужно было найти выход из лабиринта потеряв наименьшее количество жизни.
Сам лабиринт можно изобразить в виде матрицы, например
0 0 0 0 0 1
0 1 0 1 0 0
0 1 0 1 1 0
0 0 0 0 0 0
1 1 1 1 1 0
Где ноликами обозначено свободные места, единицами стенки. Задача состоит в нахождении всех путей из левого верхнего угла в правый нижний угол.
Программа, реализующая поиск всех путей в лабиринте показана ниже. Сделаем ряд пояснений
- Список ls2 содержит карту лабиринта.
- Функция next() основная рекурсивная функция, делающая шаг вперед. Новая координата является последней записью в списке pt2.
- Функция prev() это рекурсивный шаг назад.
- Функция check() определяет, можно ли сделать шаг на место с указанной координатой.
- Сделав шаг, на карте лабиринта помечается клетка, куда произошёл переход (цифрой 2). Это делается, чтобы предотвратить петли. При рекурсивном шаге назад клетка снова помечается нулём.
Если программа называется p.py, то
./p.py < in
где in содержит описание лабиринта
Например для лабиринта
0 0 0 0 0 1
0 1 1 1 0 0
0 1 1 1 1 0
0 0 0 0 0 0
1 1 1 1 1 0
Имеем
( 0 0 )
( 1 0 )
( 2 0 )
( 3 0 )
( 3 1 )
( 3 2 )
( 3 3 )
( 3 4 )
( 3 5 )
( 4 5 )
( 0 0 )
( 0 1 )
( 0 2 )
( 0 3 )
( 0 4 )
( 1 4 )
( 1 5 )
( 2 5 )
( 3 5 )
( 4 5 )
Замечание. В представленном выше алгоритме ищется клетка с заданными координатами. Но искать можно ведь и по другому принципу. Скажем вы ищете в лабиринте клад, который неизвестно где лежит. Соответственно проверяете не координаты, а содержимое ячейки.
Ну, пока всё!
Пишите свои предложения и замечания и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.
