Algorithmen und Datenstrukturen · Senior · Frage 62 von 75
Warum bevorzugt man bei manchen Rätseln DFS gegenüber BFS, obwohl BFS kürzeste Lösungen findet?
- 1BFS kommt mit Graphen mit Zyklen nicht zurecht
- 2DFS speichert einen Pfad; BFS eine ganze Front
- 3DFS findet die Lösung immer in weniger Schritten
Antwort zeigen
Richtige Antwort: DFS speichert einen Pfad; BFS eine ganze Front
Erklärung
Bei Verzweigungsfaktor b und Tiefe d hält BFS bis zu bᵈ Zustände in seiner Queue. Iterative Deepening DFS vereint das Beste: kürzeste Lösungen mit O(d) Speicher, auf Kosten wiederholter flacher Ebenen.