Informatiker Board | Druckvorschau: Breitensuchalgorithmus modifizieren

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Breitensuchalgorithmus modifizieren (http://www.informatikerboard.de/board/thread.php?threadid=1657)

Geschrieben von deppensido am 11.09.2013 um 21:05:

Breitensuchalgorithmus modifizieren

hallo,

bei der Aufgabe vom Anhang, soll man die Breitensuche so modifizieren, dass dieser einen Schichtgraphen ausgibt. Leider habe ich diesmal überhaupt keine Idee, wie man das lösen könnte. Das fängt schon damit an, dass ich gar nicht verstehe, was genau ausgegeben werden soll. Offensichtlich ist ja das Ziel eine Kantenmenge E' zu füllen, aber wann soll überhaupt eine Kante hinzugefügt werden? Hoffe mir kann jemand auf die Sprünge helfen.

Grüße

Geschrieben von Karlito am 12.09.2013 um 12:51:

RE: Breitensuchalgorithmus modifizieren

Hallo deppensido,

bei der Aufgabe geht es darum, aus einem stark zusammenhängendem Graphen einen hierarchischen Graphen zu erstellen. D.h. Du teilst den Graphen in Ebenen auf, wobei zwischen den Ebenen Kanten immer in die selbe Richtung zeigen. Es handelt sich also um einen gerichteten Baum, bei dem die Kinder mehrere Eltern haben können. Weiterhin können sich die Eltern immer nur in der darüberliegenden Ebene befinden. Verbindungen über mehrere Ebenen sind nicht möglich (die Weglänge zwischen s und u muss immer gleich sein).

VG,

Karlito

Geschrieben von deppensido am 12.09.2013 um 14:59:

hallo,

heißt das, dass ich aus einen gerichteten Graphen, einen wie in meinem Beispiel dargestellt erzeugen muss?

Geschrieben von Karlito am 12.09.2013 um 15:42:

Hallo,

ja, das ist eine mögliche Ausgabe. Eine andere habe ich angehängt.

VG,

Karlito

Geschrieben von deppensido am 12.09.2013 um 15:59:

hallo,

aber bei dem Beispiel ist doch die Weglänge von s zu dem untersten Knoten 2 und zu den anderen beiden 1. Damit ist die Bedingung, dass die Weglänge von s zu allen anderen Knoten gleich ist, nicht erfüllt oder?

Geschrieben von Karlito am 12.09.2013 um 16:16:

Ja, es geht ja auch nicht darum, dass die Weglänge zu allen Knoten gleich lang ist. Nur wenn es einen Knoten [latex]u[/latex]

gibt, müssen alle Wege von [latex]s[/latex]

aus die gleiche Länge haben.

Siehe Anhang. Für jedes [latex]u_i[/latex]

sind alle möglichen Weglängen ab [latex]s[/latex]

gleich.

VG,

Karlito

Geschrieben von deppensido am 12.09.2013 um 16:40:

danke für die Erklärung. Ich habe jetzt mal eine Lösung hingeschrieben:

vor "initalisiere BFS" kommt die Zeile "E'<- {}
hinter die Zeile " color[u] <- schwarz" kommt die Zeile "E' <- E' U (s,u)"
und schließlichlich, nach Ablauf der While-Schleife: "return G' <- (V, E').

Wäre das so schon korrekt? Als Voraussetzung, ist G ja stark zushg., womit jeder Knoten von s aus erreicht wird und somit jeder Knoten im Graph schwarz wird. Somit hat nach Terminierung jeder Knoten u die gleiche Distanz von s nach u. Dies wäre meine Begründung für die Korrektheit. Laufzeit bleibt bei O(|V| + |E|), da die zusätzlichen Operationen konstante Laufzeit haben.

Grüße

Geschrieben von Karlito am 17.09.2013 um 08:30:

Hallo,

entschuldige bitte die späte Antwort. Dein Algorithmus ist falsch. Eines der Probleme ist, dass es keine Variable s für den Startknoten gibt und Du so keine Kante (s,u) zu E' hinzufügen kannst. Ganz Grundlegend würdest Du auch nur Kanten vom Startknoten zu allen Nachfolgeknoten hinzufügen. Wege über andere Knoten fallen komplett weg. Das kann nicht richtig sein.

Ich bin der Meinung, dass der Algo schon das richtige liefert, bis auf eine Bedingung: reflexive Kanten auf den ersten Knoten der Ausgewertet wird. Schauen wir uns den Algo an:

Er nimmt sich das Kopfelement einer Warteschlange (Queue) (Z3)
Er schaut sich alle Nachfolger des Kopfelementes an (Z4-9)
Nur wenn der Nachfolger weiß (unbearbeitet) ist, bekommt er die Farbe grau, ein Zähler wird erhöht und er bekommt das aktuelle Kopfelement der Warteschlange als Vorgägner ( $[latex]\pi \left[u\right][/latex]$ )
Nachdem alle Nachfolger bearbeitet sind, wird das aktuelle Kopfelement aus der Warteschlange entfernt (Dequeue, Z10) und schwarz gefärbt (Z11)

Durch die Bedingung in Zeile 5 wird sicher gestellt, dass nie Rückführende Kanten zu bereits bearbeiteten Knoten betrachtet werden. Diese sind ja schließlich schwarz oder grau.

Soweit ich nichts übersehen habe, muss bei deiner Lösung nur der Schrit 2 geändert werden. Dieser wird gestrichen und hinter die Zeile 8 wird zur Menge der Kanten in E' das Element (u,v) hinzugefügt.

Ein Knackpunkt könnte noch sein, dass wenn in "initialisiere BFS" der erste Knoten nicht grau markiert wird, eine Reflexive Kante auf den ersten Knoten mit in die Menge kommt. Deshalb vorsichtshalber noch nach Zeile 2 color(head[Q])<- grau einfügen.

Ich hoffe ich habe nichts übersehen.

Edit: Zu der initialen Farbe: Wenn eine reflexive Kante exisitiert, kann man beliebig verschieden lange Wege zwischen zwei frei gewählten Knoten s und u wählen. Das sollte der Bedingung, dass die Wege immer gleich lang sein müssen widersprechen.

VG,

Karlito

Geschrieben von deppensido am 17.09.2013 um 09:56:

hallo,

erstmal danke für die Antwort. Also, wenn ich das richtig verstanden habe, kann das mit (s,u) zu E' hinzufügen nicht klappen, weil der Algo s nirgendwo speichert (s ist nur ein Übergabeparameter, der im ersten Durchlauf der while-Schleife das Kopfelement der Queue ist). Wenn ich nun einfach hinter Zeile 8 E'-> E' U (u,v) eingebe, dann wird vom Algo doch der Breitensuchbaum berechnet. Ist der Breitensuchbaum der Schichtgraph? Zu der Initialisierung denke ich, braucht man den ersten Knoten nicht grau färben, denn wenn die adjazenten Knoten von diesem aus besucht werden (erster Durchlauf der While-Schleife), wird dieser schwarz gefärbt und aus der Queue entfernt, womit keine Rückwärtskante zu diesem hinzugefügt werden kann. Was heißt übrigens "reflexive Kante"? Im allgemeinen ist das Hauptproblem bei diesen Aufgaben, dass ich erst gar nicht richtig verstehe, was der Algorithmus mir überhaupt ausgeben soll, hätte hier z.B. gestanden, dass ein Breitensuchbaum ausgegeben werden soll, wäre es sofort klar gewesen (falls es so ist). Danke nochmal.

Grüße

Geschrieben von Karlito am 17.09.2013 um 10:11:

Hallo,

ein normaler Breitensuchbaum beinhaltet soweit ich weiß keine zwei Eltern (siehe Schichtgraph im Anhang). Und laut Definition ist auch ein einfacher Baum ein Schichtgraph. Es besteht keine Bedingung, dass alle in Frage kommenden Kanten in den Schichtgraph aufgenommen werden.

Eine reflexive Kante ist eine, welche Von einem Knoten x zum Knoten x zurückführt. Ein Graph kann auch als Relation aufgefasst werden. Dabei ist [latex]V[/latex]

die Menge der Knoten, [latex]E[/latex]

die Menge der Kanten und $[latex]E\subseteq V \times V[/latex]$ repräsentiert den Graphen. Eine Kante für den Knoten [latex]x[/latex]

ist reflexiv, wenn $[latex]x \in V \text{ und } (x,x) \in E[/latex]$ .

Edit: Wenn das Kopfelement also nicht initial grau ist, so wird es ein Nachfolger von sich selbst.

VG,

Karlito

Geschrieben von Karlito am 17.09.2013 um 10:16:

Sorry, anhang vergessen...

Geschrieben von deppensido am 17.09.2013 um 10:29:

also muss s initial grau gefärbt werden, damit die Kante (s,s) nicht in E' aufgenommen wird?

Geschrieben von deppensido am 17.09.2013 um 10:49:

eine Ausgabe wie im letzten Anhang ist mit unserem Algo glaube nicht möglich, weil der Algo nur Kanten hinzufügt (u,v), bei dem v noch nicht besucht wurde. Damit man also so ein Graph erhält, bei dem ein Knoten zwei Elternknoten hat, müsste man auch die Kanten (u,v) in E' aufnehmen, bei denen v bereits grau ist. Eine Rückwärtskante hätte man ja erst, wenn man (u,v) hinzufügt, bei dem v schon schwarz ist, somit wäre die Ausgabe immer noch ein Baum. Um reflexive Kanten zu vermeiden, würde ich dann zusätzlich vorm hinzufügen der Kante testen, ob u ungleich v gilt. Ist diese Überlegung richtig? Eigentlich eine schöne Aufgabe, um die Breitensuche richtig zu verstehen Augenzwinkern

Grüße

Geschrieben von Karlito am 17.09.2013 um 11:03:

Hallo,

das funktioniert glaube nicht, da man so "Seitwärtskanten" innerhalb einer Schicht mit in den Graph aufnimmst. Siehe Anhang

Gruß,

Karlito

Geschrieben von deppensido am 17.09.2013 um 11:31:

ja das stimmt, danke für das Gegenbeispiel. Jetzt habe ich auch endlich die Definition vom Schichtgraphen richtig verstanden. Fälschlicherweise hatte ich zunächst gedacht, dass alle Wege im Graphen, die von s aus gefunden werden, die gleiche Länge haben müssten. Aber gemeint ist ja, dass wenn es z.B. 2 mögliche Wege von s zu einem Knoten u gibt, müssen diese beiden Wege die gleiche Länge haben. Der Algo fügt nur die Kanten (u,v) zu bei denen v noch nicht besucht ist, d.h. der algo berechnet einen Graphen, bei dem es für jedes u nur einen möglichen Weg von s nach u gibt. Eigentlich ist die Aufgabe dann doch ganz einfach.

Grüße