Algorytmy i struktury danych · Middle · Pytanie 69 z 75
Na czym polega idea „spotkania w środku” w dwustronnym BFS?
- 1Uruchomić BFS z wierzchołka w środku grafu
- ✓Poprawna odpowiedź: Szukać jednocześnie od startu i od celu, aż przeszukiwania się spotkają
- 3Uruchomić BFS na połowie krawędzi, a DFS na drugiej
Wyjaśnienie
Jeśli każdy krok rozgałęzia się na b sposobów, a odległość to d, jeden BFS przegląda około bᵈ stanów, a dwa przeszukiwania około 2 × b^(d/2). Stosuje się to w łamigłówkach typu „word ladder”.