A* und Dijkstra-Algos in PHP

[Slava]

wenn es einfach um die kürzeste strecke über die schienen handelt, dann wird Algorithmus wohl ganz anderes sein als wenn wir über die reale Linien Bahnverbindungen uns bewegen.
Und wenn wir die Kunden nicht zu fuss über die schienen laufen lassen, dann müssen einfach alle Linien von DB(am bestens mit Zeitplan) erfasst werden und zwar mit allen Zwischenpunkten, die bei einer Linie vorkommen. Dann wird auch schnell klar,
1)dass die kürzeste Strecke nicht unbedingt die schnellste ist und die schnellste nicht unbedingt wegen Ankunftszeiten die passende.
2)dass die Hauptbahnhöfen von den Großstädten Hauptrolle bei unserer Suche spielen.
3) dass wenn wir von Bergisch Gladbach nach München wollen und alle DB-Züge und Ihre Linien, die über Bergisch Gladbach laufen nehmen, und dann dasselbe mit dem München machen, dann besteht sehr grosse Wahrscheinlichkeit, dass wir direkt mehrere Linien finden, die bei beiden Städten über die gleiche Zwischenpunkte Laufen.
Je mehr gemeinsamen Zwischenpunkten, desto mehr Wahrscheinlichkeit, dass es sich um die kürzeste strecke handelt aber ohne Garantie(zusätzliche Untersuchungen sind natürlich benötigt).

Also ich habe irgendwie ein Gefühl( kann auch subjektiv sein), dass die Erfassung von allen DB-Zügen mit Ihren Strecken und Zeitplan nicht nur wichtig ist, sondern wird auch für die Datenhaltung voll ausreichen, da alle Informationen aus diesen Strecken entnommen werden können.

[TobWen]

Ich habe die Kursbücher hier, da steht das alles genau drin: Strecke, Knoten, Abfahrtzeiten, Ankuftzeiten. Die Fahrtzeiten lassen sich ja so zwischen zwei Punkten einfach ausrechnen.

"Kürzeste" Strecke war auch nicht auf Distanz, sondern auf Zeit bezogen. Zwar habe ich Infos zu den Tarifkilometern, aber ich kenne z.B. nicht alle "Langsamfahrpunkte". Von der Zeit auszugehen ist daher in meinen Augen sinnvoller.

[Shurakai]

Definitiv, denn es interessiert niemand wieviel km er im Zug verbringt, sondern nur wieviele Stunden.

Und genau das leisten die oben genannten Algorithmen ganz hervorragend. (Über die Kantengewichte)

Slavas Posting bzw. die Intention habe ich leider nicht ganz verstanden... Was meinst du?

[TobWen]

Original geschrieben von Shurakai
Definitiv, denn es interessiert niemand wieviel km er im Zug verbringt, sondern nur wieviele Stunden.

Klar interessiert das jemanden und zwar die Kunden, die die Trassen zum Transport verwenden. Dafür bietet die Bahn ebenfalls Software an, die mir freundlicherweise von der DB bereitgestellt wurde.

Daher sollte man die Option mit den Tkm offenhalten. Den Fahrgast ansich interessiert es heute nicht mehr ... nur dann, wenn er an Anschlussticket bei der Bahn kaufen kann. In NRW ist das jedoch nicht mehr möglich, da es seit einiger Zeit den NRW-Tarif gibt.

[Lennie]

Original geschrieben von Shurakai
Mal unter uns @Lennie:

Wenn du versuchst alle möglichen Kombinationen auszuprobieren und zu durchlaufen, ist das einfach nur schwachsinnig. Die Laufzeit des Scriptes ist da wahrschl. mit ner Fakultät nach oben begrenzt (das ist noch schlechter als Exp., und das ist schon absolut mies).
Mal abgesehen davon, dass du schon ne Ewigkeit brauchst um überhaupt alle Wege von a nach b zu finden und zu testen, geht es z.B. mit dem Dijkstra-Algorithmus (sofern es keine negativen Kanten / negativen Kreise gibt) ziemlich gut.

Ansonsten gibt es für das single-source-shortest path Problem noch andere Algorithmen wie zB. Ford-Bellmann oder KWP-DAG.

Der Ansatz "lass einfach mal testen" ist aber ziemlich naiv und ineffektiv.


Ob für so eine Bahnplanung aber vllt. auch das APSP (All pairs shortest path) Problem zutreffend ist (d.h. alle Wege von jedem Punkt a zu jedem Punkt b), sollte sich der Topicstarter ggf. mal überlegen (ich kenne zuwenig Details von dem Projekt), hier wäre dann der Ansatz über dynamische Programmierung (Algo. von Floyd & Warshall)

ich meine diesen ansatzt nicht erwähnt zu haben. was ich allerdings meine gesagt zu haben ist, dass ich passen muss, da ich keine bessere lösung wüsste, wenn ich keine weiteren einschränkenden bedingungen wie z.b. richung habe.

[Shurakai]

Eine vielleicht einfachere Methode wäre doch einfach alle Möglichkeiten
zu simulierieren dessen gesamtlänge unter einem bestimmten durchschnitt liegt, und von diesen noch die kürzeste auszuwählen.

Hörte sich für mich schon danach an

[TobWen]

Naja, wie gesagt - so ganz dumm ist die Idee nicht.
Es gibt ja zwei Möglichkeiten...

1. Man berechnet alle möglichen Verbindungen im Voraus. Dann braucht man nachher nur noch die Verbindungen aus der Tabelle rauszusuchen. Die Nachteile liegen auf der Hand.

2. Man berechnet in Echtzeit via Algorithmus die eingebene Strecke und wirft die kürzeste der ermittelten Routen raus - oder man wirft alle raus als Alternativroute (wäre von mir gewünscht). Die gefundenen Routen werden dann in der Datenbank gespeichert.

Ich denke, Möglichkeit 2 (On-Demand-Suche) wäre die effizientere Variante.

[closure]

Hi,

oder man kombiniert beide und speichert on demand berechnete routen.
Und damit das kind einen namen bekommt nennen wir
das mal caching

greets

[TobWen]

Hey, das war doch meine 2. Variante ...

[closure]

Huch,

wer lesen kann ist klar im vorteil.
Stimmt das sagtest du schon. Naja dann bleibt mir nur zu sagen:
Das is ne gute idee von dir

greets

[TobWen]

So, ich habe jetzt mal einen kleinen Teil graphisch dargestellt:
http://www.tobwen.de/extern/algorith...n_beispiel.pdf

Das bezieht sich natürlich alles nur auf die reine Fahrtzeit, ohne Beachtung von Umsteigezeiten.
Wenn man von Werl über Soest nach Hamm will, fährt man 26 Minuten.
Wenn man von Werl über Unna nach Hamm will, fährt man 26 Minuten.

In Realität (Gesamtreisezeit):
Werl - Soest - Hamm: 59 Minuten
Werl - Unna - Hamm: 44 Minuten

Man müsste vielleicht die Differenz aus der Abfahrtzeit des Verbindungszuges und der Ankunftszeit des Anreisezuges bilden und das dann zur Teilfahrtzeit addieren. Das wäre logisch und sinnvoll.