Breitensuche - Versionsgeschichte

Thoronador am 1. Mai 2008 um 16:00 Uhr

2008-05-01T16:00:31Z

Flash: Ich kenns als BFS -> Breadth First Search

2005-11-28T22:48:48Z

Ich kenns als BFS -> Breadth First Search

Lyr: /* Algorithmus */

2005-11-25T02:23:40Z

‎Algorithmus

Lyr am 25. November 2005 um 01:10 Uhr

2005-11-25T01:10:05Z

Neue Seite

Die Breitensuche (Breadth-First Traversal) sucht nach dem kürzesten (Kostengünstigsten) Weg in einem Baum, sie liefert also immer den idealen Weg.

=Vorgehensweise=
Hierbei werden zuerst alle Nachbarknoten des Startknoten (Alle Knoten mit der Tiefe 1) durchsucht und erst danach alle Nachbarknoten der Nachbarknoten (Alle Knoten mit der Tiefe 2) usw. Dies hat den Vorteil, dass der kürzeste Weg mit Sicherheit als erstes gefunden wird. Zyklen im Suchgraph sind zwar etwas lästig (sollten somit bei praktischer Verwendung vermieden werden) jedoch sind diese für diesen Algorithmus nicht notwendigerweise auszuschließen.

Im Gegensatz zur Tiefensuche löst sie trivialere Probleme sehr schnell. Trivialere Probleme sind hier beispielsweise:
* Ziel ist nur wenige Schritte entfernt
* Schachmatt in wenigen Zügen

=Algorithmus=
Suche_Weg( Knoten Ziel, Knoten Start )
Knoten_Queue KQueue
KQueue.Push( Start )

Für alle Knoten aus KQueue
Aktuell = KQueue.Pop

Wenn Aktuell = Ziel
Ziel gefunde

Für alle nicht besuchten Nachbarknoten von Aktuell
KQueue.Push
Dieser Algorithmus benötigt eine Laufzeit von [[O-Notation|O]](n) wobei n die Anzahl der Knoten ist. Oder anders ausgedrückt: eine Laufzeit von [[O-Notation|O]](t^v) wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Der Speicherbedarf ist [[O-Notation|O]](n) bzw. wiederum [[O-Notation|O]](t^v).

In der Praxis wird häufig auch eine Variante dieses Algorithmus verwendet, wo die Tiefe iterativ erhöht wird, und in dieser Tiefe ein [[Tiefensuche|Tiefensuch-]]Algorithmus verwendet wird. Dies sieht als Algorithmus folgendermaßen aus:
Suche_Weg( Knoten Ziel )
Tiefe = 1

Solange Ziel nicht gefunden
Tiefensuche( Ziel, Startknoten, Tiefe )
Tiefe = Tiefe + 1

und die [[Tiefensuche]] wiederum sehr ähnlich (jedoch mit einer maximalen Tiefe):

Tiefensuche( Knoten Ziel, Knoten Aktuell, Integer Tiefe )
Wenn Aktuell bereits besucht
Return

Wenn Aktuell = Ziel
Ziel gefunden

Wenn Tiefe = 0
Return

Für jeden verfügbaren Knoten
Suche_Weg( Ziel, Aktuell->verfügbarer_Knoten, Tiefe - 1 )

Die iterative Tiefesuche hat zwar die maximalen Kosten von [[O-Notation|O]](n^2) jedoch anders betrachtet wiederum die maximalen Kosten von [[O-Notation|O]](t^v) wobei t wiederum die Tiefe des Zieles und v der (durchschnittliche Verzweigungsgrad des Baumes ist. Anhand der Laufzeit bedeutet dies natürlich eine verschlechterung, jedoch der Speicherbedarf für diesen Algorithmus wird von [[O-Notation|O]](t^v) auf [[O-Notation|O]](t) gesenkt. Bei großen Suchgraphen ist dies somit (zumindest in gewissen Fällen) ein Fortschritt.

=Breitensuche mit Kosten=
Bei der Breitensuche (welche den optimalen Weg suchen soll) sind die (Weg-)Kosten von einem Knoten zum anderen durchaus relevant. Es ist eine modifizierte Variante des Breitensuch-Algorithmus denkbar, wobei die Wegkosten iteriert werden. Die Wegkosten können jedoch eine sehr hohe Auflösung (beispielsweise 0,1 Meter wo die Knoten Kilometerweit entfernt sind) besitzten. Eine iterative Breitensuche wird somit verhältnismäßig schwer.

Die nicht iterative Breitensuche können wir jedoch verhältnismäßig einfach modifizieren indem wir statt dem Queue einen Heap verwenden, welcher uns die minimalen Werte zurück gibt. Da ein Heap mit n Elementen zum einfügen eines Elementes eine Laufzeit von [[O-Notation|O]](log(n)) besitzt, besitzt dieser leicht abgewandelte Algorithmus eine maximale Laufzeit von [[O-Notation|O]](n*log(n)).

@@ Zeile 1: / Zeile 1: @@
-Die Breitensuche (Breadth First Search, BFS) sucht nach dem kürzesten (Kostengünstigsten) Weg in einem Baum, sie liefert also immer den idealen Weg.
+Die '''Breitensuche''' (Breadth First Search, BFS) sucht nach dem kürzesten (kostengünstigsten) Weg in einem Baum, sie liefert also immer den idealen Weg.
 =Vorgehensweise=
-Hierbei werden zuerst alle Nachbarknoten des Startknoten (Alle Knoten mit der Tiefe 1) durchsucht und erst danach alle Nachbarknoten der Nachbarknoten (Alle Knoten mit der Tiefe 2) usw. Dies hat den Vorteil, dass der kürzeste Weg mit Sicherheit als erstes gefunden wird. Zyklen im Suchgraph sind zwar etwas lästig (sollten somit bei praktischer Verwendung vermieden werden) jedoch sind diese für diesen Algorithmus nicht notwendigerweise auszuschließen.
+Hierbei werden zuerst alle Nachbarknoten des Startknoten (alle Knoten mit der Tiefe 1) durchsucht und erst danach alle Nachbarknoten der Nachbarknoten (alle Knoten mit der Tiefe 2) usw. Dies hat den Vorteil, dass der kürzeste Weg mit Sicherheit als erstes gefunden wird. Zyklen im Suchgraph sind zwar etwas lästig (und sollten somit bei praktischer Verwendung vermieden werden), jedoch sind diese für diesen Algorithmus nicht notwendigerweise auszuschließen.
-Im Gegensatz zur Tiefensuche löst sie trivialere Probleme sehr schnell. Trivialere Probleme sind hier beispielsweise:
+Im Gegensatz zur [[Tiefensuche]] löst sie trivialere Probleme sehr schnell. Trivialere Probleme sind hier beispielsweise:
 * Ziel ist nur wenige Schritte entfernt
 * Schachmatt in wenigen Zügen
@@ Zeile 21: / Zeile 21: @@
       Für K = alle nicht besuchten Nachbarknoten von Aktuell
         KQueue.Push( K )
-Dieser Algorithmus benötigt eine Laufzeit von [[O-Notation|O]](n) wobei n die Anzahl der Knoten ist. Oder anders ausgedrückt: eine Laufzeit von [[O-Notation|O]](t^v) wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Der Speicherbedarf ist [[O-Notation|O]](n) bzw. wiederum [[O-Notation|O]](t^v).
+Dieser Algorithmus benötigt eine Laufzeit von [[O-Notation|O]](n), wobei n die Anzahl der Knoten ist. Oder anders ausgedrückt: eine Laufzeit von [[O-Notation|O]](t^v), wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Der Speicherbedarf ist [[O-Notation|O]](n) bzw. wiederum [[O-Notation|O]](t^v).
 In der Praxis wird häufig auch eine Variante dieses Algorithmus verwendet, wo die Tiefe iterativ erhöht wird, und in dieser Tiefe ein [[Tiefensuche|Tiefensuch-]]Algorithmus verwendet wird. Dies sieht als Algorithmus folgendermaßen aus:
@@ Zeile 43: / Zeile 43: @@
       Suche_Weg( Ziel, K, Tiefe - 1 )
-Die iterative Tiefesuche hat zwar die maximalen Kosten von [[O-Notation|O]](n^2) jedoch anders betrachtet wiederum die maximalen Kosten von [[O-Notation|O]](t^v) wobei t wiederum die Tiefe des Zieles und v der (durchschnittliche Verzweigungsgrad des Baumes ist. Anhand der Laufzeit bedeutet dies natürlich eine verschlechterung, jedoch der Speicherbedarf für diesen Algorithmus wird von [[O-Notation|O]](t^v) auf [[O-Notation|O]](t) gesenkt. Bei großen Suchgraphen ist dies somit (zumindest in gewissen Fällen) ein Fortschritt.
+Die iterative Tiefensuche hat zwar die maximalen Kosten von [[O-Notation|O]](n^2) jedoch anders betrachtet wiederum die maximalen Kosten von [[O-Notation|O]](t^v), wobei t wiederum die Tiefe des Zieles und v der (durchschnittliche) Verzweigungsgrad des Baumes ist. Anhand der Laufzeit bedeutet dies natürlich eine Verschlechterung, jedoch wird der Speicherbedarf für diesen Algorithmus von [[O-Notation|O]](t^v) auf [[O-Notation|O]](t) gesenkt. Bei großen Suchgraphen ist dies somit (zumindest in gewissen Fällen) ein Fortschritt.
 =Breitensuche mit Kosten=
 Bei der Breitensuche (welche den optimalen Weg suchen soll) sind die (Weg-)Kosten von einem Knoten zum anderen durchaus relevant. Es ist eine modifizierte Variante des Breitensuch-Algorithmus denkbar, wobei die Wegkosten iteriert werden. Die Wegkosten können jedoch eine sehr hohe Auflösung (beispielsweise 0,1 Meter wo die Knoten Kilometerweit entfernt sind) besitzten. Eine iterative Breitensuche wird somit verhältnismäßig schwer.
-Die nicht iterative Breitensuche können wir jedoch verhältnismäßig einfach modifizieren indem wir statt dem Queue einen Heap verwenden, welcher uns die minimalen Werte zurück gibt. Da ein Heap mit n Elementen zum einfügen eines Elementes eine Laufzeit von [[O-Notation|O]](log(n)) besitzt, besitzt dieser leicht abgewandelte Algorithmus eine maximale Laufzeit von [[O-Notation|O]](n*log(n)).
+Die nicht iterative Breitensuche können wir jedoch verhältnismäßig einfach modifizieren, indem wir statt dem Queue einen Heap verwenden, welcher uns die minimalen Werte zurück gibt. Da ein Heap mit n Elementen zum Einfügen eines Elementes eine Laufzeit von [[O-Notation|O]](log(n)) besitzt, besitzt dieser leicht abgewandelte Algorithmus eine maximale Laufzeit von [[O-Notation|O]](n*log(n)).

← Nächstältere Version		Version vom 28. November 2005, 22:48 Uhr
Zeile 1:		Zeile 1:
−	Die Breitensuche (Breadth-First ~~Traversal~~) sucht nach dem kürzesten (Kostengünstigsten) Weg in einem Baum, sie liefert also immer den idealen Weg.	+	Die Breitensuche (Breadth First Search, BFS) sucht nach dem kürzesten (Kostengünstigsten) Weg in einem Baum, sie liefert also immer den idealen Weg.

	=Vorgehensweise=		=Vorgehensweise=

@@ Zeile 19: / Zeile 19: @@
         Ziel gefunde
-      Für alle nicht besuchten Nachbarknoten von Aktuell
+      Für K = alle nicht besuchten Nachbarknoten von Aktuell
-        KQueue.Push
+        KQueue.Push( K )
 Dieser Algorithmus benötigt eine Laufzeit von [[O-Notation|O]](n) wobei n die Anzahl der Knoten ist. Oder anders ausgedrückt: eine Laufzeit von [[O-Notation|O]](t^v) wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Der Speicherbedarf ist [[O-Notation|O]](n) bzw. wiederum [[O-Notation|O]](t^v).
@@ Zeile 34: / Zeile 34: @@
   Tiefensuche( Knoten Ziel, Knoten Aktuell, Integer Tiefe )
     Wenn Aktuell = Ziel
       Ziel gefunden
@@ Zeile 43: / Zeile 40: @@
       Return
-    Für jeden verfügbaren Knoten
+    Für K = jeder noch nicht besuchte Nachbarknoten von Aktuell
-      Suche_Weg( Ziel, Aktuell->verfügbarer_Knoten, Tiefe - 1 )
+      Suche_Weg( Ziel, K, Tiefe - 1 )
 Die iterative Tiefesuche hat zwar die maximalen Kosten von [[O-Notation|O]](n^2) jedoch anders betrachtet wiederum die maximalen Kosten von [[O-Notation|O]](t^v) wobei t wiederum die Tiefe des Zieles und v der (durchschnittliche Verzweigungsgrad des Baumes ist. Anhand der Laufzeit bedeutet dies natürlich eine verschlechterung, jedoch der Speicherbedarf für diesen Algorithmus wird von [[O-Notation|O]](t^v) auf [[O-Notation|O]](t) gesenkt. Bei großen Suchgraphen ist dies somit (zumindest in gewissen Fällen) ein Fortschritt.