РусҚаз

Обход в ширину

Информатика · 10 класс · Графы и поиск пути · Урок 2 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

Брось камешек в пруд — от него разойдутся круги: сначала маленький, потом побольше, потом ещё больше. Обход в ширину исследует граф точно так же, волнами: сначала старт, потом все его соседи, потом соседи соседей. Так он находит кратчайший путь, если все шаги одинаковые.

Мальчик стоит на деревянных мостках у тихого пруда и смотрит, как от брошенного камешка расходятся ровные круги по воде.

Зачем это нужно

Волновой поиск работает внутри роботов-пылесосов и складских роботов, которые ищут проход между стеллажами, и в компьютерных играх, где персонажи обходят препятствия. Тем же приёмом соцсети находят друзей ваших друзей, а программы, которые раскладывают дорожки на печатных платах и чипах, ищут короткую трассу для провода. ИИ легко напишет код обхода за секунду, но решить, что в задаче считать клеткой, где стены и почему путь вдруг получился не тот, должен человек. Тот, кто понимает, как идёт волна, умеет проверить машину и найти ошибку.

Небольшой складской робот едет по узкому проходу между высокими стеллажами с коробками, вокруг мягкий свет ламп.

Как это работает

Лабиринт — это тоже граф: свободные клетки — вершины, а соседние по стороне клетки соединены рёбрами. Алгоритм держит очередь: берёт клетку из её начала, пишет соседям число на единицу больше и ставит их в конец очереди. Поэтому все клетки, до которых три шага, обработаются раньше тех, до которых четыре. Когда волна докатится до финиша, число на нём и есть длина кратчайшего пути, а сам путь находят назад: от финиша к соседу, у которого число на единицу меньше, и так до старта. Работает это только тогда, когда все рёбра равноценны, то есть в графе без весов.

Дети стоят в очереди к окошку школьной столовой: кто пришёл раньше, получает обед первым, новые ученики встают в конец.

Немного истории

В конце пятидесятых годов прошлого века американский математик Эдвард Мур описал волновой способ находить кратчайший путь в лабиринте. Почти одновременно инженеры применили ту же идею, чтобы прокладывать соединения на электронных платах. Сегодня этот приём входит в любой учебник программирования и в программы для проектирования микросхем.

Учёный в рубашке с закатанными рукавами в лаборатории середины двадцатого века склонился над большим листом с нарисованным лабиринтом и карандашом отмечает клетки.

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. Перед тобой лабиринт тринадцать на восемь клеток со стенами, старт в левом верхнем углу, а финиш в правом нижнем. Сначала запусти волну и посмотри, как числа расползаются от старта по свободным клеткам, пока не дойдут до финиша. Потом восстанови кратчайший путь сам: начни с финиша и нажимай соседнюю клетку, у которой число ровно на единицу меньше, и так шаг за шагом до старта. Если у клетки два подходящих соседа — годится любой, оба пути одинаково короткие. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.

Задание в опыте

Запустите волну от старта до финиша. Затем восстановите кратчайший путь сами: нажимайте клетки от финиша к старту, каждый раз соседнюю клетку с числом на 1 меньше.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Графы и поиск пути

  1. Что такое граф
  2. Обход в ширину
  3. Алгоритм Дейкстры
  4. Графы вокруг нас