Asymptotische Laufzeit von Breiten- und Tiefensuche

Ben04

Bei der Tiefensuche kommt es meiner Meinung nach auf die genaue Formulierung des Algorithmus' an.

Bei jedem Knoten folgt man der erst besten Kante und geht zurück wenn man in eine Sackgasse geraten ist oder sich im Kreis dreht, zu mindest wenn man Zyklen im Pfad ausschließt. Wenn man zurück geht muss man danach natürlich eine andere Kante wählen. Im Idealfall muss man aber nie zurück gehen und schaut sich deswegen pro Knoten auch nur eine Kante an und dadurch ergibt sich eine Laufzeit von O(n).

Bitte ein Bit

Moin moin,

ich glaube auch dass die untere Schranke von Suchalgorithmen von der Problemstellung abhängt.

Fall 1:
Wenn man beispielsweise schnell eine Zahl in einer Liste finden möchte, kann man die Liste in einem Suchbaum abspeichern. Und dann kann es auch
natürlich sein dass der Suchalgorithmus (Tiefensuche, Breitensuche) mit einem Schlag den entsprechenden Knoten findet. Die entsprechende untere
Schranke ist Ω(1)

Fall 2:
Nehmen wir aber nun das Beispiel der Handelsreisenden an. Das Problem ist relativ schnell erklärt. Eine Person betreibt Handel und möchte 4 Städte
besuchen. Da er ein Geizkranken par Excellence ist, möchte er die Reise mit minimalen Kosten machen. Das Problem kann in einen Suchbaum gepackt
werden. Wenn man ein Knoten als besuchte Stadt ansieht und jede Kanten als Reisekosten um von Stadt A nach Stadt B zu kommen, kommt man auf den folgenden (und unvollständigen) Suchbaum.

0 
					 / |  \
				  /    |    \
				/      |      \
              1        2        3 
 	       /   \    /   \    /   \
           2     3  1     3  1     2		  
		   |     |  |     |  |     |		  
		   3     2  3     1  2     1

Eine mögliche Lösung des Problems benötigt exakt 4 verschiedene Städte. Die Tiefensuche hat hier eine untere Schranke von Ω(n) (n = Anzahl der Städte),
weil dieser zuerst in die Tiefe geht, also erst die Lösung 0-1-2-3 (danach 0-1-3-2, und danach 0-2-1-3, 0-2-3-1) probiert. Breitensuche dagegen hat
eine untere Schranke von mindestens Ω(2^n), denn dieser expandiert alle Knoten bzw. er berechnet alle möglichen Lösungen und davon gibt es
exponentiell viele. Er geht folgendermaßen im Suchbaum vor 0 -> 0-1, 0-2, 0-3 -> 0-1-2, 0-1-3, 0-2-1, 0-2-3, 0-3-1, 0-3-2 -> ...

Noch happiger wird das Problem wenn man alle Reisen unter einer Kostenschranke suchen möchte.

Ich versteh euer Problem nicht, also ersten bin ich von anderen Voraussetzungen ausgegangen wie ich nachträglich klar gestellt habe (also kein Grund hier rumzubitchen Mambo Kurt). Zweitens ist für meine Voraussetzung die Schranke von Jester richtig, diese entspricht ja auch genau meiner Überlegung im ersten Posting.

Aber ich hab natürlich nichts dagegen wenn ihr hier andere Fälle diskutieren wollt.

Ben04

Wissensdurstiger schrieb:

Ich versteh euer Problem nicht, also ersten bin ich von anderen Voraussetzungen ausgegangen wie ich nachträglich klar gestellt habe (also kein Grund hier rumzubitchen Mambo Kurt). Zweitens ist für meine Voraussetzung die Schranke von Jester richtig, diese entspricht ja auch genau meiner Überlegung im ersten Posting.

Wenns du bei der Tiefensuche jede Kante anschaust dann hast du Ω(n+m) wenn du jeden Knoten mindesten einmal besuchen willst. 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).

Ben04 schrieb:

Wissensdurstiger schrieb:

Ich versteh euer Problem nicht, also ersten bin ich von anderen Voraussetzungen ausgegangen wie ich nachträglich klar gestellt habe (also kein Grund hier rumzubitchen Mambo Kurt). Zweitens ist für meine Voraussetzung die Schranke von Jester richtig, diese entspricht ja auch genau meiner Überlegung im ersten Posting.

Wenn du bei der Tiefensuche jede Kante anschaust dann hast du Ω(n+m) wenn du jeden Knoten mindesten einmal besuchen willst. 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).

Woher will ich wissen ob der Knoten eine Kante zu einem noch nicht besuchten Knoten hat, ohne die Kante vorher anzuschauen? Ich kann auch nicht sagen ich schau immer nur eine Kante pro Knoten an, da es ja sein kann, dass mehrere Knoten durch mit einem Knoten im Graphen verbunden sind.

Bitte ein Bit

An Wissensdurstiger:

Worauf willst du denn deine Tiefensuche/Breitensuche anwenden ? Was ist deine Problemstellung ?

Denn die Laufzeiten oder Komplexität der Tiefensuche / Breitensuche (Algorithmen) hängt immer (!!!) von dem Problemstellung ab. Und genau das wollte ich mit meinem Beitrag ausdrücken. Insofern macht es hier überhaupt keinen Sinn über mögliche untere Schranken zu sprechen, denn sie kann ohne Angabe eines Problems bei Ω(1), Ω(n), Ω(2^n) oder bei Ω(n!) liegen.

Willst du beispielsweise einen gerichteten Graphen mit einer Schleife mittels Tiefensuche durchlaufen, so kann es passieren, dass die Suche in der Schleife steckenbleibt. Und blub terminiert die Suche schon nicht, untere Schranken gibt es keine.

Ich will mit der Breitensuche ein Breitensuchbaum und mit der Tiefensuche ein Tiefensuchwald erstellen.

Bitte ein Bit

Das hört sich schon ein wenig besser an.

Aber bei einer solch allgemeinen Aussage musst du damit rechnen dass beide Algorithmen eine exponentielle Zeitkomplexität besitzen, weil die Eingabe bzw. der Suchraum bzw. der Suchbaum gerne auch eine exponentielle Größe zu einer gewissen Problemstellung besitzt. Denn die Anzahl der Knoten pro Stufe wächst bei Bäumen gerne um einen Faktor 2 (3, 4, oder was auch immer) bezogen auf die vorherige Stufe.

Und da du ja den kompletten Suchbaum erzeugen willst, ist in diesem Fall der Worst Case gleich dem Best Case und der ist bei Bäumen fast immer exponentiell.

Jester

Na so ein quatsch aber auch.

Jester

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.

@Bitte ein Bit:
sowohl Tiefen-, als auch Breitensuchbäume besitzen lineare Komplexität und lassen sich in O(n+m) bestimmen. Sowieso ist bei Bäumen eigentlich fast nie was exponentiell, weil die nämlich so einfach sind.

Wissensdurstiger schrieb:

Ich will mit der Breitensuche ein Breitensuchbaum und mit der Tiefensuche ein Tiefensuchwald erstellen.

imba noob

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.

@Bitte ein Bit:
sowohl Tiefen-, als auch Breitensuchbäume besitzen lineare Komplexität und lassen sich in O(n+m) bestimmen. Sowieso ist bei Bäumen eigentlich fast nie was exponentiell, weil die nämlich so einfach sind.

Ich schätze mal er meinte einfach den Spezialfall in dem jeder Knoten maximal eine eingehende Kante hat und nur eine konstante Anzahl von Knoten keine eingehende Kante besitzen. Dann hängt die Anzahl der Kanten von n ab und dann hat er recht mit seiner unteren Schranke.

Jester

Stimmt, aber dann ist O(m+n) = O(n) und wir sagen dasselbe.

Jester schrieb:

Stimmt, aber dann ist O(m+n) = O(n) und wir sagen dasselbe.

Schon klar

Mal abwarten was er genau meinte, vielleicht meldet er sich ja nochmal.

Bitte ein Bit

@Jester

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 wie

Sowieso 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.

Jester

@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.

Ben04

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.

ChrisM

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

Jester

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.

ChrisM

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