von: derSammy
Re: BRouter: Route hin und zurück gleiche Strecke - 27.11.22 17:20
In Antwort auf: Uli
Zitat:
Mir ist kein bekannter "optimaler Pfad"-Suchalgorithmus bekannt, der das tun würde.
Darf ich die Aussage etwas schärfen? Man muss nur eine zusätzlich "Regel" in den Algorithmus einbauen: Befahrene Abschnitte werden beim nochmaligen Befahren unabhängig von der Richtung mit maximal hohen Kosten belegt. Ich kenne aber auch keine Software, die dieses Feature hat.
In die Formulierung eines "optimalen Weges" kann man das so natürlich aufnehmen. Nur ist die Problemstellung dann nicht mehr so, dass du den Dijkstra-Algorithmus zum Finden des optimalen Weges verwenden kannst. Grundvoraussetzung für den ist, dass die Kosten eines Wegabschnitts vorher feststehen. Die Kosten von A nach B dürfen dabei andere sein als von B nach A (z.B. bergauf oder bergab).
Bei deiner Variante hängen die Kosten von Wegabschnitten jedoch von dem gewählten Weg selbst ab, stehen also nicht a priori fest. Das Problem ist damit nicht mehr lokal, sprich auf Teilabschnitten ist die gefunde Lösung die mehr zwingenderweise ebenso die optimale Lösung. Numerisch wird das aus vielfältiger Sicht deutlich komplizierter, vor allem ist es nicht mehr so ohne weiteres Parallelisierbar.
Um mal so ein Beispiel aufzuzeigen, was das für Konsequenzen hat: Wir suchen einen Weg von A über B und C nach D. Zwischen A und B finden wir einen vermeintlich optimalen Weg der z.B. eine Hauptroute benutzt. Wir gehen außerdem mal davon aus, dass man naiv auch zwischen B und C und C und D kurz über die Hauptroute fahren würde, wegen der Strafkosten aus dem ersten Wegsegment dies dann aber nicht tut und große Umwege fährt. Die so gefundene Lösung ist dann aber nicht optimal, weil ein günstigerer Weg womöglich zwar zwischen A und B länger wäre, aber nicht die Hauptroute nutzt und so der Wegabschnitt zwischen B über C nach D so wesentlich kürzer hätte ausfallen können (weil da die Strafkosten wegfallen).