Informatiker Board | Algorithmen | Breitensuchalgorithmus modifizieren

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Breitensuchalgorithmus modifizieren » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 10 Beiträge
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
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
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
Karlito	Hallo, das funktioniert glaube nicht, da man so "Seitwärtskanten" innerhalb einer Schicht mit in den Graph aufnimmst. Siehe Anhang Gruß, Karlito Karlito hat dieses Bild (verkleinerte Version) angehängt:
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 Grüße
deppensido	also muss s initial grau gefärbt werden, damit die Kante (s,s) nicht in E' aufgenommen wird?
Karlito	Sorry, anhang vergessen... Karlito hat dieses Bild (verkleinerte Version) angehängt:
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 die Menge der Knoten, die Menge der Kanten und $[latex]E\subseteq V \times V[/latex]$ repräsentiert den Graphen. Eine Kante für den Knoten 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
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
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
Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen.