Asymptotische Laufzeit von Breiten- und Tiefensuche

Hi,

eine obere Schranke der Breiten- und Tiefensuche ist ja gegeben durch die Summe der Kanten und Knoten, also wenn n die Anzahl der Knoten und m die Anzahl der Kanten ist, dann ist die Laufzeit nach oben beschränkt durch O(n+m).
Aber ist dies auch eine untere Schranke? Ich glaube schon, da man bei beiden Algorithmen jeden Knoten einmal anschaut und jede von diesem Knoten ausgehende Kanten einmal anschaut.
Aber ich bin mir nicht sicher, auf Wikipedia haben sie sich um die unteren Schranken gedrückt.

MamboKurt

eine untere schranke ist O(1), da der startknoten schon deine suchbedingung erfüllen kann.

MamboKurt schrieb:

eine untere schranke ist O(1), da der startknoten schon deine suchbedingung erfüllen kann.

Reden wir gerade von dem gleichen Algorithmus?

Ich rede von den Versionen der Breiten- und Tiefensuche welche alle Knoten durchlaufen und nicht nach einem bestimmten Knoten suchen.

Jester

Dann ist sicher Ω(n) eine untere Schranke, schließlich willst Du jeden Knoten mal gesehen haben. Während Du Dir die Knoten anschaust triffst Du unterwegs auch die Kanten, und die willst Du natürlich auch alle mal anschaun (evtl. sogar zweimal um beide Richtungen anzuschaun). Also schaust Du auch alle Kanten an, damit ist die Laufzeit in Ω(m).

Insesondere ist die Laufzeit also in Ω(max{m,n}) = Ω(m+n)

Jester schrieb:

Dann ist sicher Ω(n) eine untere Schranke, schließlich willst Du jeden Knoten mal gesehen haben. Während Du Dir die Knoten anschaust triffst Du unterwegs auch die Kanten, und die willst Du natürlich auch alle mal anschaun (evtl. sogar zweimal um beide Richtungen anzuschaun). Also schaust Du auch alle Kanten an, damit ist die Laufzeit in Ω(m).

Insesondere ist die Laufzeit also in Ω(max{m,n}) = Ω(m+n)

Danke

MamboKurt

Wissensdurstiger schrieb:

Ich rede von den Versionen der Breiten- und Tiefensuche welche alle Knoten durchlaufen und nicht nach einem bestimmten Knoten suchen.

ich dachte du wolltest mit deinem suchalgorithmus was suchen. dummer gedanke von mir, ich weiß...

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.