Tiefensuche: Unterschied zwischen den Versionen
Lyr (Diskussion | Beiträge) (→Algorithmus) |
K (Kategorisierung hinzugefügt.) |
||
| (Eine dazwischenliegende Version von einem anderen Benutzer wird nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | Die Tiefensuche (Depth | + | = Tiefensuche = |
| + | Die '''Tiefensuche''' (Depth First Search, DFS) 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= | + | ==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: | 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. | * Ein Pfad wo man zwischen 2 Orten hin und zurück gehen kann. | ||
| Zeile 7: | Zeile 8: | ||
Wenn jedoch bereits besuchte Knotenpunkte aus dem Graphen entfernt werden, so läuft dieser Algorithmus mit einer Geschwindigkeit von [[O-Notation|O]](n), wobei n die Anzahl der Knoten ist; und einem Speicherbedarf von [[O-Notation|O]](m) wobei m der längste Ast ist. | Wenn jedoch bereits besuchte Knotenpunkte aus dem Graphen entfernt werden, so läuft dieser Algorithmus mit einer Geschwindigkeit von [[O-Notation|O]](n), wobei n die Anzahl der Knoten ist; und einem Speicherbedarf von [[O-Notation|O]](m) wobei m der längste Ast ist. | ||
| − | =Algorithmus= | + | ==Algorithmus== |
Suche_Weg( Knoten Ziel, Knoten Aktuell ) | Suche_Weg( Knoten Ziel, Knoten Aktuell ) | ||
Wenn Aktuell = Ziel | Wenn Aktuell = Ziel | ||
| Zeile 15: | Zeile 16: | ||
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. | ||
| + | |||
| + | [[Kategorie:Technik_oder_Algorithmus]] | ||
Aktuelle Version vom 1. Mai 2008, 18:17 Uhr
Inhaltsverzeichnis
Tiefensuche
Die Tiefensuche (Depth First Search, DFS) 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.
