Diskussion:Breitensuche

Dieser Artikel sollte komplett neu geschrieben werden. So wie er im moment da steht ist er unvollständig bis fehlerhaft. Eigentlich handelt es sich bei der Breitensuche nämlich nicht um eine Suche, sondern erstmal nur um ein Verfahren zum Durchlaufen eines Graphens. Dass man damit dann auch bestimmte Knoten im Graphen "finden" kann ist nur eine sekundäre Funktion der BFS. Außerdem sollte der Artikel über DFS und der über BFS angeglichen werden, weil man sich, wenn man sich damit beschäftigt, meistens beide Artikel parallel anschaut. Der Hinweis, dass die BFS zur "uninformierten Suche" zählt sollte nicht an den Anfang des Artikel, sondern wenn dann an das Ende geschrieben werden, oder ganz herausgenommen werden. Was das "Level" eines Graphen ist (bzw. sein soll, denn sowas gibt es a priori nicht in einem Graphen) wird auch nicht beschrieben.

--Jörg (nicht signierter Beitrag von 80.137.247.110 (Diskussion | Beiträge) 13:59, 27. Dez. 2009 (CET))

"uninformierte Suche" halte ich auch für zu irrelevant für die Einleitung. Im Artikel fehlt eine einfache Erklärung des Verfahrens, d.h. eine Erklärung, die Fachbegriffe vermeidet und anschaulich ist. --84.63.36.159 22:29, 4. Mai 2010 (CEST)

Hi, es ist mir rätzelhaft, wenn man Änderungen auf Wikipedia rückgängig machen. Entweder der Controler hat kein bock auf die Arbeit - was ich als wahrscheinlicher finde - oder hat keine Ahnung warum es geht. Ein breiten Suche soll die eine Lösung (Pfad) liefern und nicht irrgend ein unbrauchbares Ergebniss wie ein Pointer.

Bevor Sie die Lösung entfernen, "denken" Sie mal.

Könnte man vielleicht zum Aufwand der Breitensuche schreiben(bester, mittlerer, Schlechtester Falle)?

Hi, habe gerade den Artikel mal neu geschrieben, und versucht deinen Wunsch nach der Laufzeit einzubeinden. Das Problem bei der Laufzeit der Breitensuche ist dass du eigentlich nur einen Worst Case sinnvoll angeben kannst. (Bester Fall wäre O(1), wie bei eigentlich fast jedem Suchalgorithmus. Und eine garantierte Laufzeit Θ kanst du nicht angeben, da der Best und der Worst Case verschieden sind. Und dann nutzt du ja Breitensuche eigentlich selten als suche an sich, sondern vielmehr als Grundlage vieler anderer Algorithmen auf Graphen... --Regnaron 10:44, 28. Jul 2004 (CEST)

Die Beschreibung des Algorithmus ist meiner Meinung nach die einer Tiefensuche, denn es wird ja gerade nicht für jedes Element die nächstfolgende Stufe komplett untersucht, sondern gleich für das 1. Element der Queue weiter in die Tiefe gegangen (rekursiver Aufruf). --jmagiera

Hi! Danke fürs Feedback. Sowas kommt davon wenn man Breitensuche und Tiefensuche in einem Aufwasch schreibt, und dann bei dem anderen Artikel denkt nur Kleinigkeiten verändern zu müssen ;-) Habe den Pseudocode mal neugeschrieben, und ich glaube inzwischen ist er korrekt. Ist zwar jetzt inkonsistent mit der informalen Beschreibung, aber sorum gefiel es mir besser als ein mysteriöses "forall" einzubauen. Werde dann wohl -- wenn niemand mehr Fehler im aktuellen formalen Teil findet -- die Informale Beschreibung die Tage anpassen. Zwar stören mich die länglichen Kommentare im Code noch ein bisschen, aber sei's drum. Wer besser Vorschläge hat: Immer her damit. Regnaron 19:24, 20. Sep 2005 (CEST)

Platzverbrauch von Breitensuche auf Graphen

Hi, wollte mal fragen ob jemand weiß wie es mit dem Platzverbrauch von Breitensuche auf allgemeinen Graphen (also nicht im Spezialfall von Bäumen) aussieht? Regnaron 22:54, 2. Okt 2005 (CEST)

Hi, ich habe mal den Platzverbrauch $O(|V|+|E|)$ aus dem Artikel in das Bild eingefügt.

Hallo, Die Aussage "Somit ist Breitensuche aufgrund des immensen Platzverbrauches für größere Probleme ungeeignet" halte ich für unzutreffend. Der Graph muss schliesslich irgendwie gespeichert werden, d.h. mit weniger als |V|+|E| Bit geht es ja wohl kaum?!? Gemeint ist wohl hier die Größe des zusätzlichen Stapels bzw. die zusätzliche Speicherung oder Markierung der Menge der erreichbaren Knoten. Diese lässt sich aber mit entsprechenden Datenstrukturen (z.B. BDDs) klein halten, so dass Breitensuche sehr wohl ein geeignetes Verfahren für größere Probleme, z.B. in der Verifikation von Programmen, ist. HS, 24.10.2006

Nein, der Graph muss nicht unbedingt gespeichert werden: Gerade bei KI-Anwendungen hat man oft den Fall, das der Graph implizit gegeben ist und man den Knoten erst beim Besuchen erzeugt. Bei solchen Problemen ist der Speicherbedarf der Breitensuche oft problematisch. Lars 12:29, 8. Mai 2007 (CEST)

Optimalität bei der uniformen Kostensuche

Die Optimalität der uniformen Kostensuche ist nur für Kantengewichtungen mit einem Wert > 0 gewährleistet. Die momentane Definition lässt den Wert 0 zu und gewährleistet diese Optimalität nicht. Beispiel: Ist die Kantenlänge = 0 (zB für ein noOp), würde der Algorithmus in einer Endlosschleife verharren,da er immer wieder den selben Zustand besuchen würde.

Breitensuche und Dijkstra

Wenn die Kantengewichte alle gleich sind ist der Dijkstra-Algorithmus, wenn mich nicht alles täuscht, äquivalent zur Breitensuche. Das sollte vielleicht erwähnt werden, da eben für diesen (ziemlich häufigen) Spezialfall eine Breitensuche völlig ausreicht, viele sich aber trotzdem dazu verleiten lassen, einen Dijkstra (inklusive einer Priority-Queue, die lediglich als normale Queue dient), zu implementieren. Eine Referenz dazu findet sich in "Introduction to Algorithms" von Cormen et al., Seite 600 (Übungen zu Dijkstra)

Klingt logisch und ist auf jeden Fall erwähnenswert! --F GX 17:55, 5. Jun. 2009 (CEST)

"Der Baum, welcher entsteht, wenn man BFS anwendet"

Sollte man den Baum nicht aus dem Artikel nehmen? Das ist ja wohl völlig verwirrend. Was soll einem der Baum denn bitte sagen? Breitensuche ist ein Verfahren, dass einem nacheinander Knoten liefert, natürlich kann man damit einen Baum erzeugen, aber was tut das zur Sache? Und warum ist der Artikel Breitensuche und Tiefensuche so verschieden, wenn man sich dafür interessiert, wird man sich immer über beides informieren. Eine Implementierung zB wie im Tiefensuche Artikel wäre mir lieber als dieser komische Baum. MFG --F GX 17:55, 5. Jun. 2009 (CEST)

Laufzeit

Da im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssen, beträgt die Laufzeit von Breitensuche $O(\vert V\vert +\vert E\vert )$.

Wenn das wahr wäre, dass im schlimmsten Fall alle möglichen Pfade zu allen möglichen Knoten betrachtet werden müssten, wäre die Komplexität aber deutlich höher. Das ist aber nicht wahr. Man sollte also mal eine andere und dafür richtige Begründung angeben. --Jobu0101 13:09, 19. Jul. 2011 (CEST)

Nagut, im Baum stimmt es natürlich, da im Baum jeder Knoten nur genau über einen Pfad erreichbar ist. Sobald ein Knoten aber über mehr als einen Pfad erreichbar ist, betrachtet man ja nur einen Pfad (oder genau genommen so viele Pfade, wie der Knoten Nachbarknoten hat). Also der schlimmste Fall wäre hier quasi der schönste und wünschenswerteste Fall. Bei einem zusammenhängenden Graphen G mit n Knoten läuft BFS am schnellsten, wenn G Baum ist. --Jobu0101 13:14, 19. Jul. 2011 (CEST)

Hallo, wer immer diesen Artikel geschrieben hat, die mittlere Grafik (Darstellung der Deutschlandkarte nach dem Suchsystem) stimmt nicht. Zum einen fehlt ganz links noch ein weiter Punkt "München", zum anderen kommt man von Nürnberg nicht nur nach Stuttgart, sondern auf derselben Ebene nach München, und zum letzten, steht Erfurt eins zu weit rechts.

Alles in allem fehlerhaft umgesetzt in der Grafik und daher nicht zur Veranschaulichung geeignet. (nicht signierter Beitrag von Junxmutter (Diskussion | Beiträge) 08:44, 7. Jul 2013 (CEST))

Hmm, aber München ist doch schon von Kassel aus erreicht worden. Meinst du mit deinem letzten Punkt, dass Nürnberg->Stuttgart mit Erfurt vertauscht werden sollte? Aber auf die Reihenfolge kommt es doch gar nicht an. Also für mich sieht das Ergebnis in der Grafik korrekt aus. -- HilberTraum (Diskussion) 09:39, 7. Jul. 2013 (CEST)