m.sirin Geschrieben 4. Oktober 2009 Geschrieben 4. Oktober 2009 Moin , gibt es einen Algorithmus, der mit aus einer Menge von Wegen, die miteinander verbunden sind, den längsten möglichen Pfad ausgibt? Start oder Endpunkt ist dabei nicht bekannt.D.h. die Suche soll bei irgendeinem Teilweg beginnen und zum Schluss den längsten Weg ausgeben. Ich hab schon daran gedacht den Dijkstra-Algorithmus umzufunktionieren, aber bevor ich das tue, frage ich hier, ob es nicht eine dumme Idee ist? Alle möglichen Wege: schwarz. Rot: Gesuchter Weg. Grüße m.sirin Zitieren
flashpixx Geschrieben 4. Oktober 2009 Geschrieben 4. Oktober 2009 (bearbeitet) Das kann so nicht funktionieren, denn wenn Du weder Start noch Endpunkt hast, kannst Du keinen Weg innerhalb Deines Graphen definieren: Weg (Graphentheorie) ? Wikipedia Eine andere Bezeichnung für Weg ist Kantenfolge (vgl. Kantenzug). Den Knoten v1 nennt man Startknoten von W und den Knoten vn Endknoten von W. Einen besonderen Weg stellt der Eulersche Weg dar. Ob ich nun formal die Knoten mit in die Menge der Kanten mitaufnehme ist dabei unerheblich. Generell wäre die Frage, ob es wirklich "der" längste Weg sein muss, denn hierbei wirst Du nur die Möglichkeit haben, alle Wege zu prüfen, was zur NP-Vollständigkeit führt. Zweitens was ist, wenn Du mehrere Wege hast, die gleich lang sind? Wie sehen die Gewichte der Kanten aus, nimmst Du pauschal mit 1 an oder wichtest Du ggf? Was ist mit redundanten Wegen / Kreisen / Zyklen? Ansätze wäre über den Spannbaum ? Wikipedia, der zunächst einmal alle Knoten in einem Graph berührt, damit Du keine redundanten Pfade hast. Weiterhin wäre z.B. eine Möglichkeit nach dem Bellman-Algorithmus ? Wikipedia dem aktuellen Knoten die längsten/kürzesten Kante nimmst. Damit solltest Du z.B. eine gute Näherung erreichen. Letztendlich würde ich das Problem aber in das Problem des Handlungsreisenden ? Wikipedia (TSP) einordnen und entsprechend dort die Algorithmen verwenden Bearbeitet 4. Oktober 2009 von flashpixx Zitieren
m.sirin Geschrieben 5. Oktober 2009 Autor Geschrieben 5. Oktober 2009 hi, Das kann so nicht funktionieren, denn wenn Du weder Start noch Endpunkt hast, kannst Du keinen Weg innerhalb Deines Graphen definieren: Weg (Graphentheorie) ? Wikipedia Achso schade. Die besagten Mengen bestehen nicht aus vielen Teilen.. Da dachte ich, dass ich den Dijsktra umschreibe, d.h. eine Zufallskante auswählen und den "Längsten-Weg-Dijsktra" in zwei Richtungen loslassen (bzw. in alle Richtungen, die von dieser aktuellen Kante ausgehen). Anschließend werden die Ergebnisse von zwei Richtungen addiert. Oder so ähnlich Ob ich nun formal die Knoten mit in die Menge der Kanten mitaufnehme ist dabei unerheblich. Generell wäre die Frage, ob es wirklich "der" längste Weg sein muss, denn hierbei wirst Du nur die Möglichkeit haben, alle Wege zu prüfen, was zur NP-Vollständigkeit führt. Zweitens was ist, wenn Du mehrere Wege hast, die gleich lang sind? Wie sehen die Gewichte der Kanten aus, nimmst Du pauschal mit 1 an oder wichtest Du ggf? Was ist mit redundanten Wegen / Kreisen / Zyklen? Das alles Beschriebene ist kein Problem: Bei mehreren Wegen gleicher Länge wird zufällig eins ausgewählt. Gewichte der Kanten sind immer 1, ja. Ansätze wäre über den Spannbaum ? Wikipedia, der zunächst einmal alle Knoten in einem Graph berührt, damit Du keine redundanten Pfade hast. Weiterhin wäre z.B. eine Möglichkeit nach dem Bellman-Algorithmus ? Wikipedia dem aktuellen Knoten die längsten/kürzesten Kante nimmst. Damit solltest Du z.B. eine gute Näherung erreichen. Letztendlich würde ich das Problem aber in das Problem des Handlungsreisenden ? Wikipedia (TSP) einordnen und entsprechend dort die Algorithmen verwenden Das letzte hatte ich auch im Sinn. Danke, ich werde mir das dann genauer angucken! Grüße m.sirin Zitieren
flashpixx Geschrieben 5. Oktober 2009 Geschrieben 5. Oktober 2009 Achso schade. Die besagten Mengen bestehen nicht aus vielen Teilen.. Da dachte ich, dass ich den Dijsktra umschreibe, d.h. eine Zufallskante auswählen und den "Längsten-Weg-Dijsktra" in zwei Richtungen loslassen (bzw. in alle Richtungen, die von dieser aktuellen Kante ausgehen). Anschließend werden die Ergebnisse von zwei Richtungen addiert. Oder so ähnlich Naja aber wenn Du von 2 willkürlich gewählten Knoten los gehst und vorher nicht sicherstellst, dass es genau einen Weg zu jedem Knoten gibt (siehe Spannbaum), kann es Dir passieren, dass Du aneinander vorbei läufst Was aber so in diese Richtung geht wäre Ameisenalgorithmus ? Wikipedia Aber beachte, dass das eine Heuristik ist. Interessanter Thread, würde mich freuen, wenn es da noch mehr gibt :bimei Zitieren
Micha82 Geschrieben 6. Oktober 2009 Geschrieben 6. Oktober 2009 Wenn man von Optimierungen redet sollte man auch die evolutionären Algorithmen erwähnen... evolutionären Algorithmen ein evolutionäre algorithmus ist auch gut auf den tsp anwendbar... egal ob man min bzw max haben will... dies muss man dann einfach nur in der fitness-funktion richtig angeben... Zitieren
Guybrush Threepwood Geschrieben 6. Oktober 2009 Geschrieben 6. Oktober 2009 Je nach Verbindungen zwischen den Knoten wäre der längste Weg unendlich Zitieren
flashpixx Geschrieben 6. Oktober 2009 Geschrieben 6. Oktober 2009 Je nach Verbindungen zwischen den Knoten wäre der längste Weg unendlich Das kann man, wie schon gesagt, mit einem Spannbaum verhindern. Andernfalls muss man eben Redundanzen berücksichtigen Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.