Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Поиск в глубину. Кратчайшие пути в лабиринте
Сегодня продолжения темы поиска в лабиринте, которую я начал вот в этой статье
Прежде, чем читать дальше, познакомьтесь с ней и главное с представленной там программой. В ней, частности ищутся все возможные пути между заданными точками в лабиринте. Поставим другую задачу: найти все самые короткие пути между казанными точками. Ниже представлено два варианта решения задачи.
Пример решения с двумя рекурсивными функциями
Данное решение по идее очень простое. В начале нужно найти длину минимального пути. На втором этапе нужно искать все пути между указанными точками, длина которых равна равна заданной.
Ниже представлена программа, реализующая данный алгоритм. Рекурсивная функция next1() определяет длину самого короткого пути. Рекурсивная функция next2() ищет все пути длина которых равна заданному. В программе это переменная ln. Обращу внимание на проверку if len(pt2) > ln: в начале рекурсивной функции. Эта важный момент оптимизации поиска. Длина во время поиска превзойдёт длину уже найденного пути, то происходит возврат из рекурсивной функции.
Вывод найденных путей осуществляется в функции next2().
Пример решения с одной рекурсивной функцией
Данный вариант решения предполагает одну рекурсивную функцию. Т.е. для большого количества переборов этой вариант должен бы быть более оптимальным. Но требуется дополнительная память.
В массиве lss запоминаются все найденные пути с временной минимальной длиной. Если найден путь длина которого меньше, то массив очищается и туда заносится найденный путь. Если найден путь такой же длины, как путь в массиве lss, то путь добавляется в массив.
Ну, пока всё!
Пишите свои предложения и замечания и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.