Diskussion:Tiefensuche

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

Speicherplatzkomplexität und Zeitkomplexität

Die beiden Angaben sind in dem Artikel schlecht bzw. falsch dargestellt. Die Aussage zur Speicherplatzkomplexität, im worst case müssten alle Knoten(und Kanten) im Speicher gehalten werden, ist falsch. Der Vorteil der Tiefensuche ist ja gerade, dass nur die Knoten im Zweig, der gerade untersucht wird, im Speicher gehalten werden(im Gegensatz zur Breitensuche). Allgemein finde ich die Notation(ebenso wie bei der Breitensuche) schlecht, da der exponentielle Charakter der Laufzeiten nicht deutlich herausragt. Besser wäre es, die Notationen von Russel/Norvig zu übernehmen, der für die Tiefensuche beispielsweise folgende Laufzeit/Speicherplatzklassen angibt(b=Anzahl Nachfolger pro Knoten, m = maximale Tiefe eines Knotens):

Speicherplatzkomplexität: $O(bm)$

Zeitkomplexität: $O(b^{m})$

Dazu noch eine kleine Anmerkung im Text (vl im Vergleich zu anderen uninformierten Suchverfahren) oder noch besser eine Herleitung dieser Komplexitäten und der Artikel gewinnt deutlich an Qualität.

--Docterx 14:58, 11. Feb. 2007 (CET)

Ich bin deinem Wunsch nach der Herleitung der Speicherkomplexität nachgekommen, habe hierfür aber leider keine Literaturquelle gefunden. Über ein kurzes Feedback würde ich mich freuen.--Tfr.didi (Diskussion) 18:44, 29. Aug. 2013 (CEST)

Dafür terminiert die Tiefensuche nicht, falls mindestens ein Pfad des Baumes unendliche Länge hat.

und die Breitensuche? die terminiert dann doch auch nciht, oder? DWay 14:13, 5. Sep 2004 (CEST)

Ui, die Frage ist alt, aber egal :)

Nein, bei Breitensuche darf der Baum nur nicht unendlich Breit sein (wovon man normalerweise -- keine Ahnung warum --) ausgeht. Breitensuche sucht erst alle Knoten auf einem Level ab, und geht dann aufs nächste Level. Breitensuche terminiert also auch wenn es in dem Baum eine Lösung auf endlicher Tiefe gibt. Ein nendlich großer Baum ohne Lösung lässt natürlich auch die Breitensuche divergieren. Aber wenn es eine Lösung gibt, dann terminiert Breitensuche, bei Tiefensuche kann man dies jedoch nicht garantieren (eben weil du ewig lang in die Tiefe rennst) Regnaron 17:32, 15. Jul 2005 (CEST)

ein unendlich breiter Baum würde IMHO bedeuten, dass der Baum an zumindest einem Knoten uendlich viele Nachfolger hat. Die Breitensuche terminiert garantiert, wenn a) ein Weg existiert und b) eben jeder Knoten im Baum nur endlich viele Nachfolger hat. --Wirthi 23:35, 3. Dez 2005 (CET)

Die Breitensuche terminiert, wenn die Loesung nicht auf einer tieferen Ebene liegt als der Knoten mit den unendlich vielen Nachfolgern. Wenn die Breitensuche nach einer gewissen Ordnung vorgeht terminiert sie auch, wenn die Loesung in der Ordnung auf dem Level der unendlich vielen Knoten an endlicher Stelle erscheint, Ein Problem ist aber, dass die meisten gaengigen Algorithem bei Bearbeitung eines Knotens seine Nachfolger in irgendeiner Art in einer to-do Liste speichern. Dieser Vorgang terminiert bei dem Knoten mit unendlich vielen Nachfolgern nicht, die Loesung muesste also vor diesem Knoten aufgesucht werden. Theoretisch ist es jedoch denkbar, auf diese Liste zu verzichten, womit man dann zu dem von mir beschriebenen Terminierungs-Verhalten kommt. Micge 13:56, 9. Dez 2005 (CET)

Artikel neu geschrieben

Hi, nachdem ich mich eben mal rangesetzt habe und den Artikel neu geschriebe habe wollte ich mal etwas Feedback einholen was man noch besser machen könnte. Habe noch vor -- sobald ich mal ein Programm finde mit dem man so etwas schön machen kann -- ein Beispiele dafür das Tiefensuche nicht Optimal ist einzubauen. Weiterhin sollte evtl noch ein formaler Algorithmus (pseudocode) rein. Aber was fehlt sonst noch? Ist der Artikel halbwegs verständlich? Ach so, außerdem wäre ich noch froh wenn jemand was über den Platzverbrauch von DFS auf Graphen sagen könnte. Finde gerade auf die schnelle nix passendes. Bei Bäumen ist es klar, aber wie sieht es bei Graphen aus? Regnaron 13:47, 25. Jul 2005 (CEST)

Hallo. Ich halte es für sehr fragwürdig, ob die pauschale Aussage Tiefensuche sei nicht optimal so richtig ist. Geht es darum mittels einer uninformierten Suche einen Pfad von einem Startknoten $v\in V$ eines Graphen $G=(V,E)$ zu einem gewissen Knoten $w\in V$ zu finden, müssen im schlimmsten Fall alle möglichen Pfade in Betracht gezogen werden. Geschieht das mit einem Aufwand von $O(|V|+|E|)$, wie es bei der Tiefensuche der Fall ist, scheint mir das optimal zu sein. Somit wäre der Aufwand dann auch $\Theta (|V|+|E|)$. Zumindest ist mir asymptotisch nichts besseres bekannt. --Paschelino 02:38, 30. Jan 2006 (CET)

Hi! Optimalität bezieht sich hierbei nicht auf die Laufzeit, sondern auf das gefundene Ergebnis. Asymptotisch ist die Laufzeit von Tiefensuche optimal. Aber falls du zum Beispiel den kürzesten Pfad zu einem Ziel finden willst, so ist Tiefensuche im allgemeinen nicht optimal. Es geht hierbei also um die "produzierte Lösung" der Tiefensuche wenn du nach einem Knoten u suchst. Falls du eine gute Formulierung dafür hast: Immer rein damit in den Artikel um das zu klären :-) Regnaron 06:15, 30. Jan 2006 (CET)

Das wär schon ein nettes Projekt. Schließlich findet Tiefensuche/DFS in so vielen Algorithmen Anwendung. Mal sehen... Wenn ich die Zeit finde (me := Familienpapa + Informatikstudent + Angestellter + freiberuflicher Tontechniker), nehme ich mir das Thema vor, denn Lust hab ich ja dazu... (Wünsch mir Zeit...) Gruß,--Paschelino 00:13, 2. Feb 2006 (CET)

Platzverbrauch von Tiefensuche auf Graphen

Hi, wollte mal fragen ob jemand weiß wie es mit dem Platzverbrauch von Tiefensuche auf allgemeinen Graphen (also nicht im Spezialfall von Bäumen) aussieht. Regnaron 14:21, 13. Sep 2005 (CEST)

Der Platz ist ebenfalls linear in der Eingabe. Quelle: Folien zur Vorlesung Komplexitätstheorie (Sauerhoff). MFG

check --Tfr.didi (Diskussion) 18:45, 29. Aug. 2013 (CEST)

Beschreibungen: Aufruf von visit() fehlt / Besuchsreihenfolge

In dem Compilerbau-Buch von Steven S. Muchnick ([Mu97]) sind bei der Erläuterung der Tiefensuche Aufrufe von "visit_preorder()", "visit_postorder()", usw. enthalten. Könnte man diese Aufrufe nicht auch in diesen Artikel einbauen? - Habe das Buch leider nicht vorliegen und zitiere aus dem Kopf, sonst hätte ich es selbst getan...

[Mu97] Steven S. Muchnick. Advanced Compiler Design and Implementation. Academic Press. ISBN 1-55860-320-4.

--Xflupp 15:18, 5. Jan 2006 (CET)

Wie ich erst jetzt gesehen habe, geht es in diesem Abschnitt um genau das gleiche Thema. Deshalb habe ich meine Frage und meine Anmerkungen, die bisher am Ende standen, hier her verschoben. -- 217.83.12.21 09:57, 23. Aug. 2007 (CEST)

Wie heißt der Algorithmus der die Knoten im Bild in der Reihenfolge 4, 5, 3, 6, 2, 7, 10, 11, 9, 12, 8, 1 besucht? Also immer erst beim Aufstieg und nicht schon beim Abstieg. Das müsste doch eine Variante von Tiefensuche sein, aber wie genau heißt die? Und müsste die nicht auch im Rahmen dieses Artikels behandelt werden? -- 217.83.4.239 22:30, 20. Aug. 2007 (CEST)

Ich habe mal in einem alten Script geguckt. Dort wird die Suchreihenfolge für binäre Bäume beschrieben. Es gibt dort drei Arten der Besuchsreihenfolge: preorder, inorder oder postorder, je nachdem, ob der aktuelle Knoten vor, zwischen oder nach den Knoten seiner beiden Teilbäumen besucht wird. inoder ist natürlich nur für binäre Bäume genau definiert, aber pre- und postorder kann man problemlos auf beliebige Bäume übertragen. Vielleicht sollte das in den Artikel aufgenommen werden. Die verwendeten deutschen Worte sind (Prä- oder Vorordnung für preorder, Symmetrische Ordnung für inorder und End- oder Nachordnung für postorder) -- 217.83.0.116 12:13, 22. Aug. 2007 (CEST)

O - Notation für Tiefensuche

Hi. Ich kann mich entsinnen das die O - Notation (hier O(|V| + |E|) ) als Rechenregel u.a. vorschreibt, das additive Konstanten entfernt werden können. ( Rechenregel: O(f) = O(f + d) für d el. M ) Richtig wäre es nach meiner Meinung so: O(|V|) , wobei V die Knotenmenge darstellt, die immer eins größer ist als die Kantenmenge. Sehe ich da was falsch?

Tschau

Hi! Jep, du übersiehst in der Tat etwas, nämlich Hypergraphen. Es muss nicht der Fall sein, dass zwischen zwei Knoten nur eine Kante verläuft, sondern es können beliebig viele Kanten zwischen zwei Knoten verlaufen. Außerdem gibt es noch so etwas wie selbstschleifen. Ein Graph mit nur einem Knoten kann also unendlich viele Kanten haben. (eben jene Kanten die von dem Knoten auf sich selbst zeigen.) In der O-Notation kannst du übrigens nicht nur additive Konstanten, sondern jedwege konstanten wegfallen lassen. (O(an + b) = O(n) falls a und b konstant) Regnaron 20:18, 13. Jan 2006 (CET)

Wenn es sich um einen vollständigen Graph (kein Hypergraph) handelt, kann |E| bis zu 0.5*(n-1)^2 gross werden. Die Aussage, dass die Knotenmenge um eins grösser ist als die Kantenmenge, stimmt nur für Bäume. mfg gnome, 02. Jun 2006 (CET)

Klassifikation von Kanten

Die klassifikation von Kanten in Tree Kanten, Back Kanten, Forwar Kanten und Cross Kanten wäre vielleicht noch ganz interessant. Desweiteren könnte man mal über starke Zusammenhangskomponenten nachdenken. (siehe Cormen, Leiserson, Rivest, Stein: Intorduction to Algorithms S.546)

sehe ich auch so. Nur dass wir sie Baumkante, Rückwärtskante, Vorwärtskante und Querkante/Seitwärtskante nennen. --Agent00 ~ Diskussion 21:27, 29. Apr. 2007 (CEST)

Vorschlag für Überarbeitung der Struktur

Ich würde anstatt der bisherigen ersten drei Kapitel

• Allgemeines
• Algorithmus (informell)
• Algorithmus (formal)
• Algorithmusbeispiel: Erzeugen des Tiefensuchwaldes (rekursiv)

folgende Struktur vorschlagen:

• Beschreibung
  • Pseudocode
  • Beispiel

Den Teil Algorithmus (informell) sollte man in die Beschreibung integrieren, da sonst das Vorgehen 3 mal erklärt wird. Vorschläge, Anregungen, Kritik? --Tfr.didi (Diskussion) 18:47, 29. Aug. 2013 (CEST)

Begrifflichkeit

Es ist nicht einzusehen, dass die Informatik diesen Begriff für sich allein beschlagnahmt. Die Verbindung der Begriffe "Tiefe" und "Suche" sind im Hirn eines Normalsterblichen mindestens oder zu allererst mit den Gebieten Psychologie, Religion oder Meeresforschung verknüpft. (nicht signierter Beitrag von Wiki lofi (Diskussion | Beiträge) 22:56, 17. Okt. 2014 (CEST))

---

Der Link "uniformierten Suchalgorithmen" geht zu einer Seite, die den Begriff nicht enthält und somit auch nicht erläutert.

--Zsolt63 (Diskussion) 21:27, 19. Jun. 2015 (CEST)

Das Wort "Optimalität" existiert nicht!

Das Wort "Optimalität" existiert nicht und sollte durch ein anderes Wort ersetzt werden!

Da sind erstmal viele Fragen

• "uninformiert" ist nicht erklärt
• Warum sind in den Grafiken alle Graphen Bäume?
• Was bedeutet Tiefe, wenn der Graph kein Baum ist?
• Warum behandelt der englische Artikel den Begriff total anders?

–Nomen4Omen (Diskussion) 20:58, 14. Mär. 2021 (CET)