Tiefensuche: Unterschied zwischen den Versionen
Lyr (Diskussion | Beiträge) K (→Algorithmus) |
Lyr (Diskussion | Beiträge) (→Algorithmus) |
||
Zeile 12: | Zeile 12: | ||
Ziel gefunden | Ziel gefunden | ||
− | Für K = jeder noch nicht besuchte | + | Für K = jeder noch nicht besuchte Nachbarknoten von Aktuell |
Suche_Weg( Ziel, K ) | Suche_Weg( Ziel, K ) | ||
=Tiefensuche mit Kosten= | =Tiefensuche mit Kosten= | ||
Bei der Tiefensuche sind Kosten für einen Weg ohne Bedeutung, es geht ausschließlich um die Anzahl der Knoten. | Bei der Tiefensuche sind Kosten für einen Weg ohne Bedeutung, es geht ausschließlich um die Anzahl der Knoten. |
Version vom 25. November 2005, 03:23 Uhr
Die Tiefensuche (Depth-First Traversal) ist die einfachste ihrer Art. Man hofft darauf in einem der ersten durchsuchten Zweige auf die Lösung zu stoßen. Die Tiefensuche liefert meistens nicht den idealen Weg.
Vorgehensweise
Man hat einen Graphen, wovon man zuerst einen Ast bis zum letzten Element durchsucht und erst danach andere Äste in Betracht zieht. Wenn dieser Graph Zyklen aufweist, so kann dies sehr leicht zu einer endlosen Suche ausarten. Aus diesem Grund werden bereits besuchte Knoten meist also solche markiert. Beispiele für Graphen mit Zyklen:
- Ein Pfad wo man zwischen 2 Orten hin und zurück gehen kann.
- Eine Schach-Partie in der man mit einer Figur immer hin und her ziehen kann (gleich wie der Gegner)
Wenn jedoch bereits besuchte Knotenpunkte aus dem Graphen entfernt werden, so läuft dieser Algorithmus mit einer Geschwindigkeit von O(n), wobei n die Anzahl der Knoten ist; und einem Speicherbedarf von O(m) wobei m der längste Ast ist.
Algorithmus
Suche_Weg( Knoten Ziel, Knoten Aktuell ) Wenn Aktuell = Ziel Ziel gefunden Für K = jeder noch nicht besuchte Nachbarknoten von Aktuell Suche_Weg( Ziel, K )
Tiefensuche mit Kosten
Bei der Tiefensuche sind Kosten für einen Weg ohne Bedeutung, es geht ausschließlich um die Anzahl der Knoten.