Algorithmus zur Ermittlung der schnellsten Route?

17

Nehmen wir an, wir gehen von 1 auf 5. Die kürzeste Route ist 1-4-3-5 (insgesamt 60 km).

Graph

Dazu können wir den Dijkstra-Algorithmus verwenden.

Das Problem ist nun, dass die kürzeste Route aufgrund von Staus oder anderen Faktoren nicht immer die schnellste ist.

Beispielsweise:

  • 1-2 hat bekanntermaßen häufige Staus, daher sollte dies vermieden werden.
  • Plötzlich passiert ein Autounfall entlang 4-3, also sollte es auch vermieden werden.
  • Etc...

Wir können also wahrscheinlich auf der Route 1-4-5 beschleunigen, da es keine Staus / Unfälle gibt, und kommen um 5 schneller an.

Nun, das ist die allgemeine Idee, und ich habe noch nicht über weitere Details nachgedacht.

Gibt es einen Algorithmus, um dieses Problem zu lösen?

graph dijkstra anta40
quelle
3
Ist das Hausaufgabe? Ist das nicht nur ein en.wikipedia.org/wiki/Travelling_salesman_problem für das Durchlaufen eines gewichteten Graphen?
StuperUser
9
@StuperUser: Nein, TSP ist eine Schaltung aller Knoten ohne Duplikate. Im Beispielfall ist es beispielsweise nicht erforderlich, Knoten 2 zu treffen.
David Thornley
2
@ DavidThornley Ich verstehe. Dijkstra ist also die kürzeste Route in einer gewichteten Grafik? Und TSP ist auf jedem Knoten unterwegs?
StuperUser
1
@Stuper: Kürzeste Überquerung, ja
BlueRaja - Danny Pflughoeft
2
@StuperUser, nur FYI, TSP ist ein starkes NP-vollständiges Problem ohne Lösung, das in polynomieller Zeit ausgeführt werden kann. ... Jetzt weißt du es.
Riwalk

Antworten:

5

Achten Sie darauf, dass Sie sich nicht von Braess 'Paradoxon überraschen lassen, da Sie eine Überlastung verursacht haben . Wenn jeder den optimalen Weg wählt, hat dies eine schlechtere Reisezeit für alle zur Folge.

Michael Brown
quelle
49

Ja, Dijkstra

Dijkstra funktioniert in dieser Situation genauso gut.
Sie verwenden nur die Zeit und nicht die Distanz als Gewicht jedes Bogens.

Martin York
quelle
9
Typischerweise wird die Distanz in Dijkstra für alle möglichen Dinge gewichtet, Kosten / Maut, Autobahnpräferenzen, Geschwindigkeitsbegrenzungen - nur die Distanz zu verwenden, ist nur der einfachste Niave-Ansatz. Das macht den Algorithmus so clever
Martin Beckett
6
Obwohl Dijsktra dies tun wird, würde ich im Allgemeinen A * für jede ernsthafte Pfadfindungsarbeit wählen. Heuristiken werden viel helfen.
Mircea Chirea
6
Link: Ein * Suchalgorithmus . Es ist eine Erweiterung der Dijkstra-Methode.
mgkrebbs
Solange es eine anwendbare Heuristik gibt, wird A * der von Dijkstra (in Bezug auf die Leistung) überlegen sein.
Bummzack
Eine zulässige Heuristik wäre hier etwas schwierig zu finden, wenn man bedenkt, dass wir offenbar viele Faktoren berücksichtigen (z. B. Staus).
pwny
16

Ja. Der Dijkstra-Algorithmus löst dieses Problem.

Das Problem in Ihrem Fall ist, dass Sie automatisch davon ausgehen, dass der kürzeste Weg der zurückgelegten Strecke entspricht, obwohl er den KOSTEN einer Route angemessener entspricht.

Wenn ein Pfad eine Straßensperre aufweist, sollte sein COST höher sein, und der Algorithmus gilt weiterhin.

maple_shaft
quelle
Ja, tut mir leid, wenn ich nicht die richtige Formulierung verwendet habe. Was ich
meine
11

Sie sollten nur in der Lage sein, Ihre Entfernung durch die Zeit zwischen den Knoten zu ersetzen und auf die gleiche Weise zu lösen.

DKnight
quelle
10

Dijkstra

Wie gesagt, es wird nicht nur für kürzeste Strecken verwendet. Ich glaube, diese Animation gibt ein gutes Verständnis für die "Macht" (mangels eines besseren Wortes) von Dijkstra:

Dijkstra

Dynamisch
quelle