Алгоритми та структури даних · Middle · Запитання 69 з 75
У чому ідея «зустрічі посередині» у двосторонньому BFS?
- 1Запускати BFS із вершини посередині графа
- ✓Правильна відповідь: Шукати від старту й від цілі разом, доки не зустрінуться
- 3Запускати BFS на половині ребер, а DFS на іншій половині
Пояснення
Якщо кожен крок розгалужується на b варіантів, а відстань d, один BFS переглядає близько bᵈ станів, а два пошуки - близько 2 × b^(d/2). Це застосовують у головоломках на кшталт «word ladder».