Diskussion:Iterative Tiefensuche

nur auf zusammenhängenden Graphen?

Letzter Kommentar: vor 13 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

"Hierdurch wird erreicht, dass Iterative Tiefensuche prinzipiell auf allen Graphen vollständig ist" ist IMHO nicht richtig sonder sollte heißen: "Hierdurch wird erreicht, dass Iterative Tiefensuche prinzipiell auf allen zusammenhängenden Graphen vollständig ist"... (nicht signierter Beitrag von 128.131.198.216 (Diskussion) 16:27, 6. Sep. 2011 (CEST)) Beantworten

Algorithmusbeispiel hinzugefügt

@Regnaron: Der Artikel ist zwar "halbwegs verständlich", aber für mein Dafürhalten etwas zu akademisch und abstrakt. Worauf ich anspiele, ist die Tatsache, daß Wikipedia ja eine Enzyklopädie ist - und Artikel einer Enzyklopädie sollten nicht dermaßen abheben, daß sie nur von versierten Fachleuten verstanden werden können. Um das Ganze ein klein wenig greifbarer zu machen, habe ich das Algorithmusbeispiel eingefügt. Ich finde, zum Verständnis des Ganzen kann das nur positiv beitragen. Der Tiefensuchwald wird ja auch bei Rivest, Cormen, Leiserson, Stein ganz verständlich eingeführt. sevenstar 22:12, 07. Jan 2006 (CEST)

Hi! Klar, kein Problem. Der Artikel ist in meinen Augen auch noch alles andere als Fertig. Irgendwann wenn ich mal Zeit und Muße finde, will ich den Artikel in etwa so ausbauen wie es momtentan der Artikel über den A*-Algorithmus ist. Regnaron 22:25, 7. Jan 2006 (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, und eventuell noch einen Beispielbaum bauen) Aber was fehlt sonst noch? Ist der Artikel halbwegs verständlich? Ach so, außerdem wäre ich noch froh wenn jemand was über die Laufzeit von iterativer Tiefensuche bei Graphen sagen könnte. Bei Bäumen ist es ja -- wenn ich mich richtig erinnere -- $O(b^{n+1})$ im Gegensatz zu $O(b^{n})$ von normaler Tiefensuche (man muss halt alle Level des Baumes mehrmals ablaufen bevor man am letzten ankommt) Aber wie überträgt sich das auf Graphen? Habe momentan noch die selben Daten wie bei Tiefensuche im Artikel drin. Weiterhin wäre ich noch -- genau wie bei Tiefensuche über einen Educated Guess bezüglich des Speicherplatzverbrauches bei Graphen dankbar. Regnaron 18:18, 25. Jul 2005 (CEST)

Vollständigkeit

Das Problem, dass der Algorithmus keine Lösung findet, entsteht ja nur, wenn der Algorithmus mit einer begrenzten Tiefe gestartet wird! Dann ist dieser Algorithmus aber praktisch äquivalent zu der einfachen beschränkten Tiefensuche, ist also mäßig sinnvoll. Ich plädiere daher dafür den Artikel dahingehend zu ändern, dass die maximale Suchtiefe iterativ heraufgesetzt wird, ohne dass es irgendeine "Grenze" gibt. Dies entspricht auch der Darstellung in dem als Literatur angeführten Russell&Norvig-Buch, sowie dem englischen Artikel, wo der Algorithmus auch als vollständig bezeichnet wird. Außerdem ist der Satz

Wählt man zum Beispiel die maximale Suchtiefe zu gering, so findet der Algorithmus eine eventuell weiter entfernt liegende Lösung nicht.

im Abschnitt Vollständigkeit missverständlich, "zum Beispiel" suggeriert ja, dass es noch andere Möglichkeiten gibt. --eo !? 16:32, 8. Okt 2005 (CEST)

Hi, das Problem ist halt was wir als "im allgemeinen" nehmen. Wenn du solange iterierst bis du eine Lösung hast, dann divergierst du halt im zweifelsfall bist aber auf jeden Fall vollständig. So, habe gerade mal in Russel/Norvig Nachgesehen, und stimmt, da wird der Algorithmus in der Tat mit von 0 bin oo gemacht. Ok, dann werde ich mal gucken ob ich den Text nicht noch ein bisschen Anpassen kann damit die Suche notfalls in die Divergenz läuft. Wollte den Algorithmus damals halt mit einer maximalen Suchtiefe bedenken (frag' mich aber bitte nicht warum *g*) --Regnaron 17:23, 8. Okt 2005 (CEST)

Das mit dem unendlich lange laufen falls keine Lösung existiert halte ich für kein Problem (ist ja bei der normalen Tiefensuche auch so), Vollständigkeit ist ja auch nur definiert (also so weit ich weiß) als "Findet eine Lösung falls eine existiert" und nicht als "Findet eine Lösung falls eine existiert oder meldet, dass keine existiert". Gruß --eo !? 17:36, 8. Okt 2005 (CEST)

Hi! So, habe den Artikel mal entsprechend umgeschrieben. Ich hoffe ich habe nichts vergessen... Außerdem habe gerade nochmal nachgesehen, und nun auch den Grund dafür gefunden dass ich Iterative Tiefesuche mit einer festen maximalen Suchtiefe aufgebaut habe: Der Algorithmus entspricht dem der Tiefensuche, nur wird die Suche auf eine maximale Tiefe begrenzt und diese maximale Tiefe beginnend bei 0 bei jeder Iteration um eins erhöht. (eine alte Version des Artikels auf der ich damals aufgebaut hatte). Aber stimmt, Vollständigkeit lässt so weit ich weiß die Divergenz auf jeden Fall zu. Im allgemeinen zu melden dass eine Lösung nicht existiert ist dann nochmal ein paar Stufen schwerer ;-) --Regnaron 17:42, 8. Okt 2005 (CEST)

Eine andere kurze Variante der DFS

Solange noch weiße knoten in G 
   push(weißer Knoten)
   
   Solange Stack != 0
      v = pop
      wenn col[v] = weiß
            push(v)
            col[v] = grau
            für alle weißen Nachbarn u von v 
                push(u)
      sonst wenn col[v] = grau
            col[v] = schwarz
   ende
ende

Effizienz

Letzter Kommentar: vor 17 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Eine Sache verstehe ich bei dem Algorithmus nicht ganz und diese Frage in dem Artikel auch (für mich) nicht deutlich geklärt wird, ist da vielleicht Verbesserungsbedarf: Wenn ich das richtig verstehe, macht der Algorithmus Folgendes:

Durchlaufe den kompletten Teilbaum der Tiefe 0
Durchlaufe den kompletten Teilbaum der Tiefe 1
Durchlaufe den kompletten Teilbaum der Tiefe 2
Durchlaufe den kompletten Teilbaum der Tiefe 3
usw, jeweils mit Tiefensuche.

Ich frage mich nur, warum das so umständlich gemacht wird. Da muss der Algorithmus ja jedesmal den ganzen Baum neu aufbauen. Ist das nicht mächtig umständlich? Ich würde vermuten, dass folgende Lösung wesentlich effizienter ist, mag mich aber irren:

Definiere ein festes k > 0
Durchlaufe den kompletten Teilbaum der Tiefe k mit Tiefensuche
Speichere alle Blätter
Betrachte alle Blätter als Wurzeln eines Unterbaums
Durchlaufe alle Unterbäume bis zur Tiefe k mit Tiefensuche
Nach dem letzten Schritt ist also der ursprüngliche Suchbaum bis zur Tiefe 2*k durchlaufen
Speichere alle Blätter der Unterbäume und betrachte sie wiederum als Wurzeln von Unterbäumen
usw.

Dieses Verfahren hat den Vorteil, dass es nicht jedesmal wieder den kompletten Tiefensuchebaum durchlaufen muss.

Bitte diskutieren. Mir kam die Idee gerade und ich wüsste gern, ob ich da einen Denkfehler gemacht habe. Die einzige Sache, die mir dabei etwas spanisch vorkommt, ist die Speicherung der ganzen Blätter, das werden ja bei breiten Bäumen doch recht viele. Und das dürfte wohl bei der Originalversion des Algorithmus kein Problem sein. Man tauscht dort also Speicher- gegen Zeitkomplexität ein? --Cerno 23:54, 9. Nov. 2006 (CET)Beantworten

Dann hast du die Speicherkomplexität von (nee, eigentlich *hast* du dann) Breitensuche, und die zu vermeiden ist ja einer der Gründe, warum man Tiefensuche macht. Wir haben das gerade in "Grundlagen der KI", und da hieß es, die zusätzliche Zeitkomplexität beläuft sich bei einem Verzweigungsgrad von 10 auf gerade mal 11%, das ist nicht halb so schlimm wie zum Beispiel an einer schnellen Lösung vorbeizulaufen, weil man zuerst zu tief sucht; oder aber den ganzen Arbeitsspeicher vollzumüllen mit Knoten, weil man alles abspeichert.