Что это
Брось камешек в пруд — от него разойдутся круги: сначала маленький, потом побольше, потом ещё больше. Обход в ширину исследует граф точно так же, волнами: сначала старт, потом все его соседи, потом соседи соседей. Так он находит кратчайший путь, если все шаги одинаковые.
Зачем это нужно
Волновой поиск работает внутри роботов-пылесосов и складских роботов, которые ищут проход между стеллажами, и в компьютерных играх, где персонажи обходят препятствия. Тем же приёмом соцсети находят друзей ваших друзей, а программы, которые раскладывают дорожки на печатных платах и чипах, ищут короткую трассу для провода. ИИ легко напишет код обхода за секунду, но решить, что в задаче считать клеткой, где стены и почему путь вдруг получился не тот, должен человек. Тот, кто понимает, как идёт волна, умеет проверить машину и найти ошибку.
Как это работает
Лабиринт — это тоже граф: свободные клетки — вершины, а соседние по стороне клетки соединены рёбрами. Алгоритм держит очередь: берёт клетку из её начала, пишет соседям число на единицу больше и ставит их в конец очереди. Поэтому все клетки, до которых три шага, обработаются раньше тех, до которых четыре. Когда волна докатится до финиша, число на нём и есть длина кратчайшего пути, а сам путь находят назад: от финиша к соседу, у которого число на единицу меньше, и так до старта. Работает это только тогда, когда все рёбра равноценны, то есть в графе без весов.
Немного истории
В конце пятидесятых годов прошлого века американский математик Эдвард Мур описал волновой способ находить кратчайший путь в лабиринте. Почти одновременно инженеры применили ту же идею, чтобы прокладывать соединения на электронных платах. Сегодня этот приём входит в любой учебник программирования и в программы для проектирования микросхем.
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. Перед тобой лабиринт тринадцать на восемь клеток со стенами, старт в левом верхнем углу, а финиш в правом нижнем. Сначала запусти волну и посмотри, как числа расползаются от старта по свободным клеткам, пока не дойдут до финиша. Потом восстанови кратчайший путь сам: начни с финиша и нажимай соседнюю клетку, у которой число ровно на единицу меньше, и так шаг за шагом до старта. Если у клетки два подходящих соседа — годится любой, оба пути одинаково короткие. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.