+- Deutsches Simutransforum (https://simutrans-forum.de/mybb)
+-- Forum: Simutrans (https://simutrans-forum.de/mybb/forumdisplay.php?fid=3)
+--- Forum: Programmierung und Patches (https://simutrans-forum.de/mybb/forumdisplay.php?fid=38)
+--- Thema: Routing Algo (/showthread.php?tid=6423)
Routing Algo - BandGap - 25-01-2012
In nem anderen thread wurde mir das als OT vorgeworfen deshalb hier die Frage
Das Passagierrouting ist wohl Breitensuche. Auf meine Frage warum nicht Dijkstra was eine Antwort, das wäre ja Breitensuche. Es kann aber nicht beides gleichzeitig Breitensuche sein (zumindest soweit ich das aus Internetquellen verstanden habe. Bin aber kein Informatiker). Welches wird denn nun in Simutrans benutzt?
- prissi - 26-01-2012
Klar kann das beides gleich sein, dann wenn die Kosten pro Knotenschritte konstant sind. Auch A* ist mit 'ner konstanten Heuristik eine Breitensuche.
Zusammenhang ist ungefähr so:
A* spezialisierung von Dijkstra spezialisierung von Breitensuche
A* hat Abstände und Heuristik
Dijkstra hat Abstande
Breitensuche: Nur die Tatsache einer Verbindung
- BandGap - 26-01-2012
Ok lassen wir das mal so stehn; und was wird jetzt fürs Passagierrouting benutzt?
- pETe! - 26-01-2012
Zitat:Original von BandGapWie lassen wir das mal so stehen? Dijkstra ist Breitensuche, nur mit dem Unterschied, dass die "einfache" Breitensuche den kürzesten Weg danach sucht, dass am wenigsten Knoten durchlaufen werden.
Ok lassen wir das mal so stehn;
Bei Dijkstra werden die Kanten gewichtet und der Weg mit dem geringstem Kantengewicht als kürzester angenommen.
- BandGap - 26-01-2012
Zitat:Original von pETe!Aber dennoch kommen andere Ergebnisse für das eine als für das andere raus. Deshalb ist es unspezifisch zu sagen, dass Breitensuche benutzt wird, wenn es aber eigentlich Dijkstra ist.
Dijkstra ist Breitensuche, nur mit dem Unterschied, dass die "einfache" Breitensuche den kürzesten Weg danach sucht, dass am wenigsten Knoten durchlaufen werden.
Genauso kann ich die klassische Mechanik als Grenzfall der Quantenmechanik ansehen, obwohl andere Ergebnisse rauskommen (können).
Im vorliegenden Fall interessiert mich halt v.a. ob ein Passagier eher den Zug nimmt, obwohl der Weg länger sein mag, die Geschwindigkeit aber höher...
- prissi - 26-01-2012
Der aktuelle Algorithmus benutzt weder Weg noch GEschwindigkeit (oder Kapazität) sondern alleine die ANzahl der Unterwegshalte.
- BandGap - 28-01-2012
Aaaahh jetzt wird mir auch klar warum die direkt fahrenden Pferdefuhrwerke völlig überfüllt und die schönen Züge mit Zwischenhalt total leer waren...