Алгоритми та структури даних · Senior · Запитання 62 з 75
Чому для деяких головоломок DFS кращий за BFS, хоча BFS знаходить найкоротші розв'язки?
- 1BFS не впорається з графами, що містять цикли
- ✓Правильна відповідь: DFS зберігає один шлях, а BFS - увесь фронт
- 3DFS завжди знаходить розв'язок за менше кроків
Пояснення
З коефіцієнтом розгалуження b і глибиною d BFS тримає в черзі до bᵈ станів. DFS з ітеративним поглибленням бере найкраще від обох: найкоротші розв'язки з O(d) пам'яті, ціною повторення неглибоких рівнів.