Algorithmus für längsten Weg

[m.sirin]

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

[flashpixx]

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

[m.sirin]

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

[flashpixx]

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

[Micha82]

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...

[Guybrush Threepwood]

Je nach Verbindungen zwischen den Knoten wäre der längste Weg unendlich

[flashpixx]

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