Поиск в ширину

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

Волна прошла все 181 440 позиций, до которых вообще можно дойти, и для каждой знает точное число ходов до сборки. Самым трудным нужен 31 ход, и таких позиций ровно две — кнопка «Самая трудная» показывает обе. Почти две трети позиций лежат в слоях от 20 до 25 ходов, в среднем до сборки 22 хода. Включите подсказки: зелёная плитка приближает к сборке, красная удаляет. Нейтральных плиток не бывает: каждый ход меняет расстояние ровно на единицу. Почему так, станет ясно из доказательства.

Идея

Обходите граф кругами: сначала все вершины в одном шаге от старта, потом в двух, потом в трёх. Для этого хватает очереди: вершину ставят в хвост, когда видят впервые, а обрабатывают из головы. Раз круги идут по порядку, вершину впервые видят по самому короткому пути — с наименьшим числом рёбер.

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

Второй приём сцены — обход идёт не от вашей позиции, а от собранной. Любой ход можно отменить, поэтому путь от позиции к сборке и путь от сборки к позиции — один и тот же путь, прочитанный в разные стороны. Один обход от цели отвечает на вопрос для всех стартов сразу. Обход от вашей позиции ответил бы только про неё.

Как это работает: дуплеты Кэрролла

В марте 1879 года Льюис Кэрролл напечатал в журнале Vanity Fair новую игру — «дуплеты»: превратить одно слово в другое, меняя за ход одну букву, так чтобы каждое промежуточное слово было настоящим. Его собственный пример — HEAD → HEAL → TEAL → TELL → TALL → TAIL. Слова — вершины, ход — ребро, и кратчайшая цепочка — работа для поиска в ширину. Вот он на маленьком словаре из 21 слова, по шагам. Внизу — очередь: голова слева, хвост справа.

Проследите за очередью. В ней никогда не бывает слов больше чем из двух соседних слоёв: в голове заканчивается слой k, а в хвост приходят слова слоя k + 1. Поэтому слова достаются строго по слоям, и к моменту, когда дошла очередь до слоя k + 1, все более близкие слова уже обработаны.

Обратите внимание на шаги «уже найдено — пропускаем». Слово помечают в момент, когда его увидели, а не когда достали из очереди. Если помечать при извлечении, одно слово успеет попасть в очередь несколько раз, по разу от каждого соседа из предыдущего слоя. Ответ останется верным, но в пятнашках очередь приняла бы 241 921 запись вместо 181 440, а её наибольшая длина выросла бы с 24 059 до 32 751.

Когда очередь опустела, каждое слово помнит, откуда в него пришли. Эти ссылки образуют дерево с корнем в начальном слове, и цепочку до TAIL читают по ним задом наперёд. Получилась ровно цепочка Кэрролла. Другие цепочки в словаре есть — например, через HEAT, BEAT и BELT, — но все они длиннее, а из HELD дороги к TAIL нет вовсе. Если бы кратчайших цепочек было несколько, обход взял бы ту, до которой волна дошла раньше.

Почему пути кратчайшие

Назовём слоем L_k множество вершин на расстоянии ровно k от старта s: L₀ = {s}, а L_k+1 — соседи вершин из L_k, которых нет в предыдущих слоях. Поиск в ширину строит именно эти множества, по одному за другим.

Из доказательства выходит полезное следствие. В графе без направлений ребро соединяет вершины одного слоя или соседних слоёв: если бы ребро шло из L_k в L_k+2, дальняя вершина была бы на расстоянии k + 1. Ребро внутри одного слоя замыкает цикл нечётной длины, поэтому граф можно раскрасить в два цвета без одноцветных рёбер тогда и только тогда, когда поиск в ширину не нашёл ни одного ребра внутри слоя. Так проверяют двудольность.

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

Код

Python берёт deque: popleft стоит O(1). В Go очередь — обычный срез: queue = queue[1:] только сдвигает начало среза и ничего не копирует. Словарь dist работает за двоих: хранит ответ и помнит, кого уже видели.

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

Слои растут почти вдвое на каждом шаге — 1, 2, 4, 8, 16, — потом рост замедляется, а после 24-го хода слои худеют: новых позиций почти не осталось, волна упирается в края пространства. Сумма всех слоёв — ровно 9!/2: половина расстановок плиток недостижима из собранной позиции. Что так устроены пятнашки любого размера, доказали ещё в 1879 году Уильям Джонсон и Уильям Стори.

Сколько это стоит

Каждая вершина попадает в очередь один раз — проверка «уже видели» не пустит её второй раз. Список соседей каждой вершины просматривается один раз, когда её достают из очереди, поэтому всего рёбер просмотрено O(E), а в графе без направлений каждое ребро смотрят дважды, с обоих концов. Итого O(V + E) времени и O(V) памяти на метки и очередь. В пятнашках V = 181 440, рёбер 241 920, проверок соседей 483 840.

Линейное время держится на одном условии: извлечение из очереди должно стоить O(1). Обычный список Python для этого не годится: pop(0) сдвигает все оставшиеся элементы, и на широкой волне обход становится квадратичным. В Go тот же эффект даёт сдвиг среза через copy. Замер на случайных графах с тремя рёбрами на вершину:

У очереди со сдвигом время растёт почти как квадрат: в правой части графика вдвое больше вершин — вчетверо больше времени. У настоящей очереди наклон около 1,2, а не ровно 1: на больших графах дорожает каждое обращение к памяти, соседи случайной вершины лежат где попало. На 32 тысячах вершин Python со сдвигом уже в два с половиной раза медленнее, и разрыв растёт вместе с графом.

Память тоже стоит считать. Очередь хранит весь фронт волны, и на графах, которые быстро ветвятся, он огромен: в пятнашках в очереди одновременно лежало до 24 059 позиций — каждая восьмая.

Где ломается

Веса рёбер

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

От MEGA Alma-Ata до Центрального стадиона обход в ширину выбирает путь через 44 участка улиц длиной 7,47 км, Дейкстра — через 81 участок, но длиной 5,76 км. Обход в ширину решил другую задачу — с наименьшим числом перекрёстков, — и решил её правильно. Если веса бывают только 0 и 1, обход ещё можно спасти: вершину, найденную по ребру веса 0, кладут в начало дека, а не в хвост. Этот приём, обход 0-1, понадобится во второй задаче. Для произвольных неотрицательных весов нужна куча, то есть Дейкстра.

Взрыв пространства

Пятнашки 3×3 — 181 440 позиций, это мгновенно. У пятнашек 4×4 позиций 16!/2 ≈ 1,05 · 10¹³: по одному биту на позицию — больше терабайта. Полный обход в ширину всех этих позиций впервые сделали Ричард Корф и Петер Шульце в 2005 году. Оказалось, что самым трудным позициям нужно 80 ходов и таких позиций 17. У кубика Рубика позиций 43 252 003 274 489 856 000, и обходить их волной нереально. То, что любую позицию можно собрать за 20 ходов, в 2010 году доказали другими методами, с помощью около 35 процессоро-лет машинного времени.

Когда нужен путь от одной позиции до другой, а не карта всего пространства, волну сужают. Встречный поиск пускает две волны навстречу: если каждая ветвится в b раз, две волны радиуса d/2 обходят около 2b^d/2 вершин вместо b^d. A* тянет волну к цели подсказкой о расстоянии.

Где работает

Лабиринты и платы. В 1959 году Эдвард Мур из Bell Labs описал волну для поиска кратчайшего пути через лабиринт. В 1961 году Ч. Ли приспособил её для разводки проводов на печатных платах: клетки платы — вершины, занятые клетки — стены. Отсюда русское название — волновой алгоритм. Ещё раньше, в 1945 году, тот же обход описал Конрад Цузе в диссертации о языке Plankalkül, но напечатали её только в 1972 году.

Сборка мусора. Копирующий сборщик переносит живые объекты в новую область памяти. В 1970 году Ч. Дж. Чейни заметил, что очередь для этого заводить не нужно: скопированные, но ещё не просмотренные объекты сами лежат подряд в новой области, между указателем «просмотрено» и указателем «свободно». Это поиск в ширину, где очередью служит сама память, и ни стека, ни рекурсии ему не нужно.

Суперкомпьютеры. С 2010 года рейтинг Graph 500 сравнивает машины по скорости обхода в ширину огромного случайного графа, в рёбрах в секунду. Для таких графов придумали обход в обе стороны: пока фронт маленький, вершины фронта смотрят на соседей, а когда фронт разросся, наоборот, каждая ещё не найденная вершина ищет среди своих соседей хоть одну из фронта и останавливается на первой. Скотт Бимер, Крсте Асанович и Дэвид Паттерсон показали в 2012 году, что на графах соцсетей это сокращает число просмотренных рёбер и ускоряет обход в несколько раз.

Кратчайшее по числу шагов. Пересадки, рукопожатия, переходы по ссылкам, ходы коня, ходы в любой головоломке — везде, где все шаги стоят одинаково. Здесь поиск в ширину проще и быстрее Дейкстры, и ответ у него тот же.

Его брат — поиск в глубину: тот же обход, но со стеком вместо очереди. Кратчайших путей он не ищет, зато знает о структуре графа то, чего не видит волна, — циклы, порядок, мосты.

Задачи

В первой задаче граф нужно построить: соседей у слова много не бывает, но если сравнивать каждую пару слов, словарь «Войны и мира» не уложится во время. Во второй веса рёбер — 0 и 1, и очередь придётся заменить деком.