 Breitensuchalgorithmus modifizieren |
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
 |
|
|
11.09.2013 21:05 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| 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
|
|
|
12.09.2013 12:51 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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?
|
|
|
12.09.2013 15:59 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
|
12.09.2013 16:16 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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
|
|
|
12.09.2013 16:40 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?\pi \left[u\right]) )
- 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
|
|
|
17.09.2013 08:30 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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
|
|
|
17.09.2013 09:56 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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]](http://www.matheboard.de/latex2png/latex2png.php?V) die Menge der Knoten, ![[latex]E[/latex]](http://www.matheboard.de/latex2png/latex2png.php?E) die Menge der Kanten und ![[latex]E\subseteq V \times V[/latex]](http://www.matheboard.de/latex2png/latex2png.php?E\subseteq V \times V) repräsentiert den Graphen. Eine Kante für den Knoten ![[latex]x[/latex]](http://www.matheboard.de/latex2png/latex2png.php?x) ist reflexiv, wenn ![[latex]x \in V \text{ und } (x,x) \in E[/latex]](http://www.matheboard.de/latex2png/latex2png.php?x \in V \text{ und } (x,x) \in E) .
Edit: Wenn das Kopfelement also nicht initial grau ist, so wird es ein Nachfolger von sich selbst.
VG,
Karlito
|
|
|
17.09.2013 10:11 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
also muss s initial grau gefärbt werden, damit die Kante (s,s) nicht in E' aufgenommen wird?
|
|
|
17.09.2013 10:29 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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 
Grüße
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von deppensido: 17.09.2013 10:51.
|
|
|
17.09.2013 10:49 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
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
|
|
|
17.09.2013 11:31 |
|
|
|
