"Информатика (базовый и углублённый уровень)", Гейн А.Г., Сенокосов А.И.
Волновой алгоритм находит кратчайший путь по клетчатому полю с препятствиями. От начальной клетки он по шагам распространяется на доступных соседей и присваивает клеткам метки расстояния. Клетки с одинаковой меткой образуют волну: число показывает, сколько переходов нужно сделать от старта. Когда цель размечена, маршрут восстанавливают в обратном направлении, переходя к соседям с меньшими метками. Если волна не достигла цели, пройти к ней нельзя.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Волновой алгоритм — способ найти кратчайший путь по клетчатому полю, последовательно распространяясь от начальной клетки. Он нужен, когда важно не просто добраться до цели, а сделать это за минимальное число ходов. Для этого поле обходят слоями, не перескакивая через клетки с меньшим расстоянием.
Волна — множество клеток, до которых можно добраться за одинаковое число шагов от начала. Например, первая волна содержит клетки, соседние со стартом, если они свободны. Такое деление помогает обрабатывать поле по порядку: сначала ближайшие клетки, затем более удалённые.
Метка расстояния — число шагов от начальной клетки до клетки; недоступным клеткам метка не присваивается. Метка позволяет сравнить маршруты и понять, сколько переходов нужно до выбранного места. Если все переходы имеют одинаковую стоимость, первая найденная метка является минимальным расстоянием.
Восстановление пути — обратный проход от цели к началу по соседним клеткам с последовательно уменьшающимися метками. Поиск сначала сообщает расстояния, но сам маршрут ещё нужно собрать. Уменьшение меток на единицу гарантирует, что каждый выбранный переход ведёт ближе к началу по кратчайшему пути.
Поле представляют как клетки-состояния: свободные клетки доступны для движения, а препятствия исключаются из поиска. Это похоже на граф, где клетка является вершиной, а разрешённый переход между соседями — ребром. Препятствие не может быть частью маршрута, поэтому его не включают в обход и не размечают.
Начальной клетке присваивают метку 0, потому что до неё самой нужно сделать ноль ходов. Затем рассматривают её доступных соседей и присваивают им метку 1. Так алгоритм задаёт точку отсчёта и показывает, что каждый переход от стартовой клетки увеличивает расстояние ровно на один.
На каждом следующем шаге очередная волна охватывает ещё не размеченных свободных соседей клеток предыдущей волны. Им присваивают метку, на единицу большую, чем у клеток, откуда пришло распространение. Уже размеченные клетки пропускают: иначе поиск повторял бы работу, а расстояние могло бы быть заменено неуместным значением. Поскольку сначала обработаны все клетки с меньшими метками, новая метка показывает минимальное число ходов.
Распространение завершают, когда размечена целевая клетка или больше нет клеток, куда можно распространиться. В первом случае минимальное расстояние до цели уже известно, поэтому продолжать обход не требуется. Во втором случае волна исчерпала все доступные клетки, а неразмеченная цель означает, что путь отсутствует.
Чтобы получить маршрут, от цели переходят к допустимому соседу с меткой на единицу меньше и повторяют это до начальной клетки. Каждый такой переход отменяет один шаг расстояния и ведёт в предыдущую волну. Полученную последовательность обычно записывают в обратном порядке, от старта к цели. Так восстанавливается кратчайший путь, хотя при нескольких равных вариантах можно получить один из них.
| Этап | Что выполняется | Результат |
|---|---|---|
| Инициализация поля | Отмечают свободные клетки, препятствия, начало и цель | Подготовлено поле для поиска |
| Запуск первой волны | Началу присваивают 0, его свободным соседям — 1 | Задано начало отсчёта расстояний |
| Распространение волн | Размечают ещё не посещённых свободных соседей текущей волны | Клетки получают минимальные расстояния |
| Проверка достижения цели | Проверяют метку цели или отсутствие новых клеток | Понятно, достигнута ли цель |
| Восстановление маршрута | От цели переходят к соседям с метками на единицу меньше | Получена последовательность клеток пути |
Пользуйтесь таблицей как порядком действий: сначала подготовьте поле, затем распространяйте волны и только после проверки достижимости восстанавливайте маршрут. Если цель не получила метку, последний этап пропускают. Расстояние до цели читают по её метке.
Задача 1. На поле без препятствий найдите кратчайший путь от клетки (1, 1) до клетки (3, 4). Координаты записаны как (строка, столбец), а ходить разрешено только вверх, вниз, влево и вправо. Нужно определить не только расстояние, но и последовательность клеток, по которой можно пройти.
Ответ: кратчайший путь содержит 5 переходов. Подойдут и другие маршруты длины 5, если на каждом шаге двигаться к соседней клетке с меткой на единицу меньше при восстановлении.
Задача 2. На поле 4 × 5 нужно найти длину кратчайшего пути от (1, 1) до (4, 5). Препятствия занимают клетки (2,2), (2,3), (2,4), (3,2) и (3,4). Поскольку нельзя проходить сквозь препятствия, расстояние следует определить по волновой разметке, а не только по прямой линии.
Ответ: длина кратчайшего пути равна 7 переходам. Если вывести все клетки маршрута, в последовательности будет 8 клеток, потому что в неё входят и начало, и цель.
Задача 3. На поле 3 × 4 начальная клетка находится в (2, 1), а цель — в (2, 4). Все клетки второго столбца заняты препятствиями: (1,2), (2,2) и (3,2). Требуется установить, можно ли пройти, и при возможности вывести маршрут.
Ответ: пройти к цели нельзя. Если бы цель получила метку, маршрут можно было бы восстановить обратным проходом к началу.
Если разрешить волне проходить через препятствия, метки будут описывать маршруты, по которым в действительности нельзя пройти. Так происходит, когда препятствие считают обычной клеткой или не проверяют тип соседа. Проверьте себя: ни одна клетка маршрута не должна быть препятствием, а соседние клетки должны соединяться разрешённым переходом.
Повторное присваивание меток уже посещённым клеткам приводит к лишним обходам и может нарушить порядок поиска. Эту ошибку допускают, если при расширении волны не отмечают, что клетка уже обработана. Проверка простая: каждой доступной клетке достаточно присвоить метку один раз, при первом обнаружении.
Число клеток в маршруте иногда принимают за его длину. Но длина — это количество переходов между клетками, а не количество записанных координат. Если в списке N клеток, убедитесь, что ответ равен N − 1: первый пункт списка обозначает старт, а не совершённый ход.
При восстановлении пути нельзя переходить к соседу с такой же или большей меткой. Такое движение не приближает к началу и не соответствует обратному проходу по волнам. Проверяйте каждую пару соседних клеток: метка следующей при движении к старту должна быть ровно на единицу меньше.
Для работы с полем пригодится представление прямоугольной сетки в виде двумерного массива: координаты клетки задаются номером строки и столбца. Нужно также уметь перечислять соседние клетки и проверять, не выходят ли их координаты за границы массива. Эти навыки позволяют правильно подготовить поле и исключить препятствия.
Волновой алгоритм связан с обходом графа в ширину. Клетки здесь выступают вершинами, а разрешённые переходы между соседями — рёбрами; обработка по слоям соответствует обходу вершин по расстоянию от старта. Алгоритм полезен для поиска кратчайших маршрутов в лабиринтах, сетках и задачах на перемещение объектов.
Почему волновой алгоритм находит именно кратчайший путь?
Клетки обрабатываются по расстоянию от начала: сначала все достижимые за один шаг, затем за два и так далее. Поэтому первая метка клетки соответствует минимальному числу переходов до неё.
Можно ли использовать алгоритм, если между клетками разрешены диагональные переходы?
Да, если диагональный переход разрешён правилами задачи, его учитывают как ещё один тип соседства. Нужно одинаково учитывать такие переходы и при распространении волн, и при восстановлении маршрута.
Что делать, если целевая клетка осталась без метки?
Если поиск завершён и цель не получила метку, из начальной клетки до неё нельзя добраться. Проверьте, что препятствия и правила соседства заданы правильно, прежде чем делать вывод.
Зачем при восстановлении пути идти от цели к началу?
Метка каждой клетки показывает расстояние от начальной клетки, поэтому у соседней клетки на кратчайшем маршруте метка на единицу меньше. Следуя таким меткам от цели, можно шаг за шагом дойти до старта.
Как определить длину найденного маршрута?
Длина пути — это число переходов между соседними клетками. Если в восстановленном маршруте перечислено N клеток, его длина равна N − 1.
Лабораторная работа № 24 (к § 53) Волновой алгоритм
