Учимся использовать и реализовывать на Python алгоритм поиска в ширину (BFS) для решения реальных задач.

Давайте поговорим о популярном алгоритме, который называется «Поиск в ширину» (BFS). Затем реализуем этот алгоритм, чтобы найти решение для реальной задачи: как выбраться из лабиринта.

Алгоритмы поиска применяются для решения таких задач, которые можно смоделировать как графы. Каждый узел графа – это экземпляр задачи. Каждый поисковый алгоритм начинается с узла (исходный экземпляр – состояние) и наращивает вслед за этим узлом новые (то есть, новые экземпляры задачи), решая задачу допустимыми способами. Этот процесс останавливается, как только алгоритм находит решение (успех – конечное состояние) или не может создать ни одного нового узла (провал). Среди самых популярных алгоритмов поиска – поиск в глубину (DFS), поиск в ширину (BFS), жадный алгоритм, поиск по критерию стоимости (UCS), A*-поиск, т.д. В этой статье речь пойдет о поиске в ширину.

Читать далее

https://habr.com/ru/post/679020/?utm_source=habrahabr&utm_medium=rss&utm_campaign=679020