Asymptotische Laufzeit von Breiten- und Tiefensuche
-
1.) Offenbar hast du noch nie einen Suchalgorithmus wie die Tiefensuche (Backtracking)/Breitensuche/A* Algorithmus, Best-First-Search, Least-Cost-Search, beschränkte Breitensuche mit k-stufigem Lookahead, ... auf einem Entscheidungsbaum durchgeführt.
Nimm mal ruhig das Problem des Handelsreisenden http://en.wikipedia.org/wiki/Travelling_salesman_problem, welches ich in dem ersten Beitrag von mir angesprochen habe und generiere dir selbst ein Beispiel mit 10 Städten. Baue darauf dann deinen Entscheidungsbaum auf und lasse dann die Tiefensuche darüber laufen. Wenn du das getan hast, bin ich mir sicher dass du Sprüche wieSowieso ist bei Bäumen eigentlich fast nie was exponentiell, weil die nämlich so einfach sind.
nicht mehr so einfach dahersagst. Einen Tip möchte ich dir hier geben: Sage solche Sprüche nie einen Professor für theoretische Informatik. Er könnte es nicht gut auffassen.
2.) Die Zeitkomplexität hast du in Bezug auf die Anzahl der Eingabeknoten und Anzahl der Eingabekanten gewählt. Ich aber, habe die Zeitkomplexität in Bezug auf die Größe des Problems gewählt. Denn es macht meines Erachtens mehr Sinn, jemanden der vielleicht keine große Ahnung von Komplexität hat, die zu erwartende Komplexität des kompletten Algorithmus zu sagen als die des allgemeinen Tiefensuche-Algorithmus. Wenn er dann nämlich mal einen Algorithmus zum Lösen eine N²xN² Sudokus schreibt, würde sich dieser wundern warum die Tiefensuche so lange benötigt obwohl diese doch eine lineare Komplexität hat.
Nehmen wir mal das Beispiel des Handelsreisenden für k-Städte. Baut man einen Entscheidungsbaum auf, so entspricht ein Pfad von der Wurzel bis zu einem Blatt eine mögliche Lösung. Das bedeutet dass der Baum exakt die Höhe k hat. Mittels einer Formel aus der Wiki http://en.wikipedia.org/wiki/Binary_tree lässt sich die Anzahl der Knoten brutalst nach unten mit n = 2^(k - 1) + 1 abschätzen. Setzt man diese in die Komplexität der Tiefensuche ein, erhält man eine Kompleität von O(2^(k - 1) + 1). Und dies war meiner Aussage.
-
@BitteEinBit: blablabla, lern mal was eine Breiten/Tiefensuche auf einem Graphen ist und danach darfste wieder ankommen.
Kleiner Tip: Dein Entscheidungsbaum hat exponentiell viele Knoten und Kanten, da wundert es dann auch nicht, dass die Suche darin so lange braucht, die ist zwar linear, aber halt in der Anzahl der Knoten und Kanten und die ist in dem Entscheidungsbaum dann halt exponentiell. Ich hoffe aber, dass sich keiner über exponentielle Laufzeiten wundert, wenn schon der Graph, der durchsucht wird exponentiell groß ist (auch wenn er halt implizit beschrieben ist).
Btw sage ich solche Sätze gerne, auch vor Informatik-Professoren und auch in den Übungen, die ich halte, schließlich weiß ich wovon ich spreche. Aber danke für den Tipp auch.
-
Jester schrieb:
Ben04 schrieb:
Nun kann man die Tiefensuche allerdings auch implementieren ohne immer jede Kante anzuschauen zu müssen und trotzdem jeden Knoten zu erwischen. Im besten Fall schaust du genau eine Kante pro Knoten an. Das ist dann Ω(n).
Dann erzähl mal, das interessiert mich genauer. Insbesondere zeig doch bitte, wie Dein Algorithmus vorgeht, wenn ich ihm einen K_n gebe, wo ich an einen Knoten (nennen wir ihn v) noch ein zusätzliches Blatt angehängt habe. Sagen wir, der Algorithmus fängt mit der Tiefensuche bei v an und findet zufällig als erstes nicht die Kante, die zu dem Blatt führt, sondern irgendeine andere aus dem K_n.
Das war ein Missverständnis. Gefragt war eine unterte Schranke für die Laufzeit im schlechtesten Fall. Ich hab eine für den besten Fall geliefert (und in dem hat man Glück und findet halt die richtige). Im besten Fall (also auch günstige Struktur) stimmt meine Beh. Für eine ungünstige Struktur muss man anders argumentieren kommt aber trotzdem auf etwas lineares raus.
-
Hallo,
im besten Fall findest du bei der Breitensuche aber direkt im ersten Schritt (erste Kante vom Startknoten aus) deinen Zielknoten. Oder du musst sogar gar nicht den Startknoten verlassen und kannst direkt abbrechen.
Beispiel: Im Djikstra-Algo kannst du abbrechen, sobald der Knoten, von dem du die Entfernung zum Startknoten suchst, erreicht wurde (dessen Wert verändert sich danach nicht mehr, sobald du alle Knoten mit niedrigerer Entfernung ausgewählt hast). Im besten Fall ist das direkt am Anfang der Fall, nämlich, wenn z.B. die Entfernung zum Startknoten (vom Startknoten) oder eben zu dem Nachbarn des Startknotens mit der am geringsten gewichteten Kante gesucht wird.
Also untere Laufzeit IMHO Omega(1).
Viele Grüße
Chris
-
Naja, das kommt ein bißchen drauf an. Oft macht man eine Tiefen/Breitensuche nicht um einen bestimmten Knoten zu finden, sondern weil man eben an dem jeweiligen Suchbaum interessiert ist, bzw. während der Suche irgendetwas miterledigt, zum Beispiel weil man die Zusammenhangskomponenten eines Graphen finden möchte oder ähnliches. Da ist dann nichts mit vorzeitigem Abbruch.
-
Hallo,
klar, das hängt natürlich auch vom Algorithmus ab. Die klassische Breiten-/Tiefensuche hat ja auch erstmal gar keine Abbruchbedinung (zumindest im Buch von Cormen & co).
Chris
-
ChrisM schrieb:
Hallo,
klar, das hängt natürlich auch vom Algorithmus ab. Die klassische Breiten-/Tiefensuche hat ja auch erstmal gar keine Abbruchbedinung (zumindest im Buch von Cormen & co).
Chris
Eben, und genau um diese Varianten ging es mir auch. Genaugenommen habe ich sogar die Algorithmen im Cormen gelesen und das war auch der Grund für den Thread. Dass jemand an eine andere Vorgehensweise, als diese, denken könnte bin ich gar nicht drauf gekommen, als ich den Thread erstellt habe.
Ich denke auch, dass jedem hier klar ist, dass man für andere Varianten des Algorithmus andere Komplexitäten erreichen kann, aber mir ging es hier um die Variante die den Breitensuchbaum bzw. den Tiefensuchwald erstellt.
-
ChrisM schrieb:
klar, das hängt natürlich auch vom Algorithmus ab. Die klassische Breiten-/Tiefensuche hat ja auch erstmal gar keine Abbruchbedinung (zumindest im Buch von Cormen & co).
Ja, so ist das üblicherweise gemacht. Die "anderen Varianten" durchsuchen meist in Wirklichkeit einen anderen Graphen als den gegebenen, der implizit konstruiert wird. Dieser ist dann oftmals deutlich größer. Das ändert aber nichts an der Komplexität.
Die englische Wikipedia hat zur Tiefensuche auch einen relativ brauchbaren Artikel, während die deutsche sich mit dem Einleitungssatz "Tiefensuche (Depth-First Search) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen." direkt ins aus katapultiert.
