Routing Algo

[BandGap]

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]

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]

Ok lassen wir das mal so stehn; und was wird jetzt fürs Passagierrouting benutzt?

[pETe!]

Original von BandGap
Ok lassen wir das mal so stehn;

Wie 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.
Bei Dijkstra werden die Kanten gewichtet und der Weg mit dem geringstem Kantengewicht als kürzester angenommen.

[BandGap]

Original von pETe!
Dijkstra ist Breitensuche, nur mit dem Unterschied, dass die "einfache" Breitensuche den kürzesten Weg danach sucht, dass am wenigsten Knoten durchlaufen werden.

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.

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]

Der aktuelle Algorithmus benutzt weder Weg noch GEschwindigkeit (oder Kapazität) sondern alleine die ANzahl der Unterwegshalte.

[BandGap]

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