Breitensuchalgorithmus modifizieren

Neue Frage »

Auf diesen Beitrag antworten »
deppensido 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
 
Auf diesen Beitrag antworten »
Karlito 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
Auf diesen Beitrag antworten »
deppensido

hallo,

heißt das, dass ich aus einen gerichteten Graphen, einen wie in meinem Beispiel dargestellt erzeugen muss?
Auf diesen Beitrag antworten »
Karlito

Hallo,

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

VG,

Karlito
 
Auf diesen Beitrag antworten »
deppensido

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?
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
deppensido

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
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
deppensido

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
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
Karlito

Sorry, anhang vergessen...
Auf diesen Beitrag antworten »
deppensido

also muss s initial grau gefärbt werden, damit die Kante (s,s) nicht in E' aufgenommen wird?
Auf diesen Beitrag antworten »
deppensido

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
Auf diesen Beitrag antworten »
Karlito

Hallo,

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

Gruß,

Karlito
Auf diesen Beitrag antworten »
deppensido

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
Auf diesen Beitrag antworten »
Karlito

Naja, ganz einfach finde ich die Aufgabe nicht. Vor allem ist ja bisher noch nicht gezeigt, dass ein Schichtgraph entsteht. Ich tu mich mit Beweisen auch immer schwer und bin deshalb froh, dass ich die betreffenden Klausuren bisher alle bestanden habe.

VG,

Karlito
Auf diesen Beitrag antworten »
deppensido

hallo,

zur Übung hab ich mich noch an einer ähnlichen Aufgabe versucht (ist die letzte, die ich habe). Bei der Aufgabe hat man ein Straßennetz als gewichteter gerichteter Graph gegeben. Die Kantengewichte geben dabei die Steigung der Straßen an (soll ein Straßennetz der Alpen sein), negative Kantengewichte sind Gefälle. Die Aufgabe lautet nun: Modifizieren Sie Dijkstras Algo., so dass dieser alle Wege mit kleinster maximaler Steigung von einem Startort s zu allen anderen Orten in den Alpen berechnet. Zusätzlich soll man begründen, warum in diesem Fall negative Kantengewichte kein Problem sind.

Was heißt hier: "mit kleinster maximaler Steigung"? Müssen alle berechneten Distanzen positiv sein oder dürfen Kanten mit negativen Kantengewichten nicht betrachtet werden? Der Dijkstra Algo. berechnet ja für einen gewichteten Graphen (ohne negativen Kantengewichte) kürzeste Wege von s zu allen anderen Knoten. Meine Idee wär deshalb: statt
d[v]<-d[u]+w(u,v) berechne d[v]<- |d[u] | + |w(u,v)|. Also einfach d[u] und w(u,v) in Betragsstriche setzen.

Grüße
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »