Algorithmen und Datenstrukturen · Middle · Frage 69 von 75
Was ist die Idee „Meet in the Middle“ bei der zweiseitigen BFS?
- 1BFS vom Knoten in der Mitte des Graphen starten
- 2Gleichzeitig vom Start und vom Ziel suchen, bis sie sich treffen
- 3BFS auf der Hälfte der Kanten und DFS auf der anderen laufen lassen
Antwort zeigen
Richtige Antwort: Gleichzeitig vom Start und vom Ziel suchen, bis sie sich treffen
Erklärung
Verzweigt jeder Schritt b-fach und ist der Abstand d, erkundet eine BFS etwa bᵈ Zustände, zwei Suchen etwa 2 × b^(d/2). Man nutzt das bei Rätseln wie „Word Ladder“.