Двунаправленный BFS: поиск с двух концов, Word Ladder и Open the Lock
Двунаправленный BFS простыми словами: почему b^(d/2) вместо b^d, зачем расширять меньший фронт, разбор Word Ladder и Open the Lock на Python и случаи, когда приём не помогает.
Коротко
| Обычный BFS | Двунаправленный BFS | |
|---|---|---|
| Откуда ищем | от старта | от старта и от цели одновременно |
| Посещённых вершин (ветвление , расстояние ) | ||
| Что нужно знать | старт | старт и конкретную цель |
| Ориентированный граф | как есть | нужны обратные рёбра |
| Типичные задачи | любые кратчайшие пути | Word Ladder, Open the Lock, головоломки с состояниями |
- Два поиска в ширину идут навстречу друг другу, и как только фронты касаются, ответ найден.
- Каждый раз расширяем меньший фронт — это главный практический трюк.
- Выигрыш огромен, когда граф быстро ветвится (слова, комбинации, состояния головоломки), и почти нулевой на сетке или когда цель на краю пространства состояний.
Откуда берётся ускорение
Обычный BFS обходит граф слоями: сначала все вершины на расстоянии 1, потом 2 и так далее. Если у каждой вершины в среднем новых соседей, на слое лежит примерно вершин. Чтобы дойти до цели на расстоянии , придётся посетить
Теперь запустим два поиска: один от старта, другой от цели. Кратчайший путь длины где-то посередине проходит через вершину, до которой от каждого конца примерно шагов. Каждому поиску достаточно дойти до своей половины:
Числа для ощущения масштаба: при и это миллион против двух тысяч. Показатель степени делится пополам, а не просто константа уменьшается вдвое.
Картинка, которая помогает запомнить: круг радиуса против двух кругов радиуса . В пространстве, где «площадь» растёт экспоненциально от радиуса, два маленьких круга несопоставимо меньше одного большого.
Тот же принцип «встретиться посередине» используется в Meet in the Middle для перебора подмножеств: превращается в .
Как устроен алгоритм
Держим два множества — фронты:
front— вершины текущего слоя одного поиска;back— вершины текущего слоя другого поиска;visited— всё, что уже посещено любым из поисков.
На каждой итерации берём меньший из фронтов и расширяем его на один слой целиком. Если при генерации соседа он оказался во фронте другого поиска — пути сошлись, ответ: количество сделанных шагов плюс один.
Почему фронты — множества, а не очереди? Потому что расширяем мы слой целиком, порядок внутри слоя не важен, а проверка «сосед лежит в другом фронте» должна работать за .
Шаблон
def bidirectional_bfs(start, target, neighbors): """Длина кратчайшего пути в неориентированном графе или -1.""" if start == target: return 0 front, back = {start}, {target} visited = {start, target} steps = 0 while front and back: if len(front) > len(back): front, back = back, front # расширяем меньший фронт steps += 1 next_front = set() for v in front: for u in neighbors(v): if u in back: return steps # фронты встретились if u not in visited: visited.add(u) next_front.add(u) front = next_front return -1 # один из фронтов опустел — пути нет
Обратите внимание на условие цикла while front and back. Если любой из фронтов опустел, значит, эта сторона обошла всю свою компоненту связности и не встретила другую. Пути нет, и продолжать бессмысленно.
Почему именно меньший фронт
Можно чередовать стороны строго по очереди, и алгоритм останется корректным. Но графы редко симметричны: у старта может быть три соседа, а у цели — триста. Расширять фронт стоит пропорционально его размеру, поэтому выгоднее каждый раз двигать тот, который сейчас дешевле.
Эффект особенно заметен, когда одна из вершин лежит в маленькой «бухте» графа. Поиск с её стороны быстро упирается в узкое горлышко, его фронт остаётся маленьким, и он делает почти всю работу. Если же цель недостижима и лежит в крошечной компоненте, её фронт опустеет за пару шагов — и алгоритм закончит работу, не обходя огромный граф со стороны старта. Обычный BFS в той же ситуации посетил бы всю компоненту старта.
Word Ladder (LeetCode 127)
Условие. Даны слова beginWord, endWord и словарь wordList. За один шаг можно поменять одну букву, и каждое промежуточное слово должно быть в словаре. Нужно вернуть количество слов в самой короткой цепочке от beginWord до endWord (включая оба конца) или 0, если цепочки нет.
beginWord = "hit", endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
hit -> hot -> dot -> dog -> cog ответ: 5
Это поиск кратчайшего пути в невзвешенном графе, где вершины — слова, а рёбра соединяют слова, отличающиеся одной буквой. Граф неявный: строить его заранее не нужно, соседей генерируем на лету — перебираем позицию и букву, кандидатов на слово длины .
Обычный BFS
from collections import deque def ladder_length_bfs(begin_word, end_word, word_list): words = set(word_list) if end_word not in words: return 0 queue = deque([(begin_word, 1)]) visited = {begin_word} while queue: word, steps = queue.popleft() if word == end_word: return steps for i in range(len(word)): for ch in 'abcdefghijklmnopqrstuvwxyz': nxt = word[:i] + ch + word[i + 1:] if nxt in words and nxt not in visited: visited.add(nxt) queue.append((nxt, steps + 1)) return 0
Решение проходит, но в худшем случае посещает весь словарь. На собеседовании его стоит написать первым — оно короткое и очевидно правильное, а потом предложить ускорение.
Двунаправленный BFS
def ladder_length(begin_word, end_word, word_list): words = set(word_list) if end_word not in words: return 0 # иначе back-поиск стартует с несуществующего слова if begin_word == end_word: return 1 front, back = {begin_word}, {end_word} visited = {begin_word, end_word} steps = 1 # слов в цепочке, если фронты встретятся прямо сейчас while front and back: if len(front) > len(back): front, back = back, front # всегда расширяем меньший фронт next_front = set() for word in front: for i in range(len(word)): for ch in 'abcdefghijklmnopqrstuvwxyz': nxt = word[:i] + ch + word[i + 1:] if nxt in back: return steps + 1 if nxt in words and nxt not in visited: visited.add(nxt) next_front.add(nxt) front = next_front steps += 1 return 0
print(ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])) # 5 print(ladder_length('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log'])) # 0
Разбор на примере
| Итерация | Расширяем | front после шага | back | steps |
|---|---|---|---|---|
| старт | — | {hit} | {cog} | 1 |
| 1 | {hit} | {hot} | {cog} | 2 |
| 2 | {hot} (размер 1 = 1, не меняем) | {dot, lot} | {cog} | 3 |
| 3 | меняем местами, расширяем {cog} | {dog, log} | {dot, lot} | 4 |
| 4 | {dog, log}: сосед dot лежит в back | — | — | ответ |
Видно, как работает выбор меньшего фронта: на третьей итерации сторона hit разрослась до двух слов, и ход переходит к стороне cog.
Сколько это экономит
На маленьком примере разницы не видно, поэтому я прогнал оба варианта на синтетическом словаре: около 29 тысяч случайных четырёхбуквенных слов, 200 случайных пар. Обычный BFS посещал в среднем ≈14 200 слов, двунаправленный — ≈500. Почти в 30 раз меньше работы при том же ответе.
Сложность
Пусть — размер словаря, — длина слова. Каждое слово порождает кандидатов, и сборка каждого кандидата стоит из-за среза строки. В худшем случае оба варианта дают по времени и по памяти: двунаправленный поиск не улучшает асимптотику худшего случая, но на реальных данных посещает на порядки меньше вершин.
Вместо перебора 26 букв можно заранее сгруппировать слова по шаблонам: hot попадает в корзины *ot, h*t, ho*. Соседи слова — это объединение его корзин. Это полезно, когда алфавит большой, а словарь маленький. Приём ортогонален двунаправленному поиску, их можно сочетать.
Open the Lock (LeetCode 752)
Условие. Кодовый замок из четырёх колёс, на каждом цифры 0–9, колёса крутятся по кругу (9 → 0 и 0 → 9). Начальное положение 0000. Есть список «тупиков» deadends: если замок встанет в такое положение, он заблокируется. Нужно найти минимальное число поворотов, чтобы открыть target, или вернуть −1.
Граф здесь — состояний, у каждого ровно 8 соседей (4 колеса × 2 направления). Рёбра симметричны: если из 0000 можно попасть в 0001, то и обратно тоже. Значит, обратный поиск может пользоваться той же функцией соседей.
def open_lock(deadends, target): dead = set(deadends) start = '0000' if start in dead or target in dead: return -1 if start == target: return 0 def neighbors(code): for i in range(4): d = int(code[i]) for delta in (1, -1): yield code[:i] + str((d + delta) % 10) + code[i + 1:] front, back = {start}, {target} visited = {start, target} | dead # тупики — как уже посещённые turns = 0 while front and back: if len(front) > len(back): front, back = back, front next_front = set() for code in front: for nxt in neighbors(code): if nxt in back: return turns + 1 if nxt not in visited: visited.add(nxt) next_front.add(nxt) front = next_front turns += 1 return -1
print(open_lock(['0201', '0101', '0102', '1212', '2002'], '0202')) # 6 print(open_lock(['8888'], '0009')) # 1 print(open_lock(['8887', '8889', '8878', '8898', '8788', '8988', '7888', '9888'], '8888')) # -1 print(open_lock(['0000'], '8888')) # -1
Третий пример хорошо показывает пользу условия while front and back. Цель 8888 окружена тупиками со всех восьми сторон. Фронт со стороны цели опустеет на первом же шаге, и функция вернёт −1, не обходя 10 тысяч состояний.
Два граничных случая, на которых часто ошибаются: 0000 сам может быть в тупиках (ответ −1, а не 0), и цель может быть в тупиках.
Когда двунаправленный BFS не помогает
Приём часто подают как бесплатное ускорение, но выигрыш зависит от формы графа. Я посчитал количество посещённых вершин для нескольких случаев:
| Граф | Обычный BFS | Двунаправленный | Выигрыш |
|---|---|---|---|
| Дерево с ветвлением 10, путь длины 6 через корень | 123 000 | 1 344 | ≈90× |
| Синтетический словарь Word Ladder (среднее по 200 парам) | ≈14 200 | ≈500 | ≈29× |
Open the Lock, 0000 → 3333 | 7 194 | 2 023 | ≈3,5× |
Open the Lock, 0000 → 5555 | 10 000 | 10 000 | нет |
| Сетка 1000×1000, две точки в центре на расстоянии 400 | 310 801 | 160 355 | ≈2× |
| Сетка 1000×1000, из угла в угол | 1 000 000 | 1 000 000 | нет |
Из таблицы видны основные случаи.
Граф растёт полиномиально, а не экспоненциально. На сетке количество клеток на расстоянии растёт как , а не как : «площадь» круга радиуса пропорциональна . Два круга радиуса дают — всего вдвое меньше. Для лабиринтов и карт вроде Number of Islands двунаправленный поиск — экономия на константе, а не на порядке.
Цель далеко, и пространство состояний маленькое. 5555 — самая удалённая от 0000 комбинация: 20 поворотов. Чтобы до неё дойти, любой поиск обойдёт весь замок. Экспоненциальная экономия работает, только пока заметно меньше размера графа. Если граф всё равно приходится обойти целиком, считать с двух сторон бессмысленно.
Цель не одна или неизвестна. Нужны расстояния до всех вершин, ближайший выход из лабиринта, любая клетка с сокровищем — второй поиск просто не с чего начинать. Иногда помогает многоисточниковый BFS (положить все цели во второй фронт сразу), но часто проще обычный BFS.
Ориентированный граф без обратных рёбер. Обратный поиск должен идти по рёбрам против направления: от цели к тем вершинам, из которых в неё можно попасть. Если граф задан функцией «куда можно пойти» и обратить её дёшево нельзя, двунаправленный поиск неприменим.
Взвешенный граф. Для весов нужен двунаправленный Дейкстра, а у него другое условие остановки: первая встреча фронтов не гарантирует кратчайший путь. Остановиться можно только когда сумма минимумов в двух кучах стала не меньше лучшего найденного пути. Для весов 0 и 1 обычно хватает 0-1 BFS, а при хорошей эвристике — A*.
Нужны все кратчайшие пути. В Word Ladder II (LeetCode 126) нужно вернуть все цепочки минимальной длины. Двунаправленный поиск там применим, но нельзя выходить на первой встрече: слой надо дорасширить до конца, запомнить родителей и собрать пути. Код становится заметно сложнее, и на собеседовании это стоит проговорить.
Ориентированные графы: обратные рёбра
Если рёбра односторонние, обратный поиск должен ходить по входящим рёбрам. Обобщённый шаблон хранит для каждой стороны тройку «фронт, посещённые, функция соседей» и меняет их местами целиком:
def bidirectional_bfs(start, target, forward, backward=None): """Длина кратчайшего пути start -> target или -1. forward(v) — исходящие соседи, backward(v) — входящие. Для неориентированного графа backward не нужен.""" if start == target: return 0 backward = backward or forward # фронт, его посещённые вершины и функция соседей — тройкой a = ({start}, {start}, forward) b = ({target}, {target}, backward) steps = 0 while a[0] and b[0]: if len(a[0]) > len(b[0]): a, b = b, a front, seen, neighbors = a steps += 1 next_front = set() for v in front: for u in neighbors(v): if u in b[0]: return steps if u not in seen and u not in b[1]: seen.add(u) next_front.add(u) a = (next_front, seen, neighbors) return -1
Что будет, если забыть про backward:
edges = [(0, 1), (0, 4), (0, 5), (1, 2), (2, 3), (3, 1)] out = {v: [] for v in range(6)} inc = {v: [] for v in range(6)} for x, y in edges: out[x].append(y) inc[y].append(x) print(bidirectional_bfs(0, 3, out.get, inc.get)) # 3 — верно print(bidirectional_bfs(0, 3, out.get)) # 2 — неверно: такого пути нет
Поиск от 3 пошёл по ребру 3 → 1 вперёд и «встретил» фронт старта в вершине 1. Но пути 0 → 1 → 3 в графе нет, есть только 0 → 1 → 2 → 3. Ошибка тихая: функция возвращает правдоподобное число.
Типичные ошибки
- Не проверили, что цель есть в словаре. В Word Ladder, если
endWordнет вwordList, ответ 0. Двунаправленный поиск без этой проверки начнёт обратный фронт с несуществующего слова и может найти «путь». - Ошибка на единицу в ответе. Word Ladder считает слова в цепочке, Open the Lock — повороты, то есть рёбра. Отсюда разные начальные значения счётчика:
steps = 1иturns = 0. Сверьте ответ с примером из условия до того, как писать оптимизацию. - Проверка встречи по общему
visited, а не по фронту другой стороны. В общемvisitedлежат и вершины своей стороны, так что «встреча» найдётся там, где её нет. Правильный вопрос: «лежит ли сосед в текущем слое другого поиска?». Тогда длина пути однозначно равна сумме пройденных слоёв. - Расширение по одной вершине вместо целого слоя. Если чередовать стороны после каждой извлечённой вершины, счётчик шагов теряет смысл: слои перемешиваются. Расширяйте слой целиком.
- Обратный поиск по прямым рёбрам в ориентированном графе — пример выше.
- Забыли обновить
visitedпри добавлении во фронт. Вершины начнут возвращаться в уже пройденные слои, фронты будут расти бесконечно, и если пути нет, цикл не закончится.
Как это выглядит на собеседовании
Word Ladder — одна из самых известных задач на BFS, она есть почти во всех подборках для подготовки к алгоритмическому интервью. Двунаправленный поиск там обычно не обязателен: обычный BFS проходит все тесты. Но это любимый вопрос «а можно быстрее?», и хороший ответ звучит примерно так:
- «Это кратчайший путь в невзвешенном графе, поэтому BFS. Граф неявный, соседей генерирую заменой одной буквы».
- Пишете обычный BFS, проверяете на примере, называете сложность.
- «Мы знаем и старт, и цель, граф неориентированный и быстро ветвится. Можно искать с двух сторон: вместо вершин посетим порядка . Чтобы стороны не перекашивало, каждый раз расширяю меньший фронт».
- Переписываете на два множества — это 10–15 строк поверх существующего кода.
- Сами называете ограничения: в худшем случае асимптотика та же, для весов нужен другой алгоритм.
Пункт 5 часто отличает сильного кандидата: он показывает, что вы понимаете, почему приём работает, а не помните его как заклинание.
Задачи, где приём применим напрямую:
- Word Ladder (LeetCode 127) — разобрана выше;
- Open the Lock (LeetCode 752) — разобрана выше;
- Minimum Genetic Mutation (LeetCode 433) — та же Word Ladder с алфавитом
ACGTи строками длины 8; - Sliding Puzzle (LeetCode 773) — состояния доски 2×3, цель известна;
- Word Ladder II (LeetCode 126) — все кратчайшие цепочки, двунаправленный поиск плюс восстановление путей.
Итог
Двунаправленный BFS — это обычный поиск в ширину, запущенный с двух концов. Он превращает в , если граф ветвится экспоненциально, известны и старт, и цель, а рёбра можно пройти в обратную сторону. Главная деталь реализации — фронты-множества и расширение меньшего из них по слою целиком. Если хотя бы одно условие не выполняется — сетка, неизвестная цель, веса, — берите обычный BFS, Дейкстру или A*.