nicht angemeldet
Fahrplanauskunft - wie?
Hi,
habe mir gestern mal wieder darüber Gedanken gemacht, wie eigentlich eine automatische Fahrplanauskunft funktioniert. (wie zB unter http://reiseauskunft.bahn.de).
Die Daten zu speichern ist ja wohl nicht das Problem. Ich habe eine Tabelle mit allen Haltestellen und eine mit allen Zügen (Zugläufen) Die sind über eine weitere Tabelle miteinander verknüpft, wo dann zB gespeichert ist, daß der Zug IC 4711 um 12:34 im Bhf Dingenskirchen hält.
So weit, so gut.
Wie kriege ich jetzt aber eine Verbindung zwischen zwei beliebigen Bahnhöfen gesucht? Alle möglichen Verbindungen ausprobieren kann ja nicht das Wahre sein.
Hat da jemand eine Idee, wie sowas funktionieren könnte?
TIA
wunderwarzenschwein
--
Elvis lebt!
-
-
Hi,
sagt außer allgemeinem Werbegelaber nicht wirklich, wie der Algorithmus funktioniert.
Trotzdem danke.wunderwarzenschwein
-
Moin
sagt außer allgemeinem Werbegelaber nicht wirklich, wie der Algorithmus funktioniert.
Wundert mich auch nicht, da HaCon mit den Alghorithmus immerhin Geld verdienen will. Dennoch hat mir der Link ausgereicht um zu erfahren, wie es in etwa funktioniert. Google mal nach Hafas und Alghorithmus oder nach A*-Algorithmus.
Eine paar Anmerkung am Rande.
Die Fahrplansuche ist nicht so trivial, wie es scheint. Für die Auskunft muss der Weg gesucht werden (das gibt schon eine Menge an Wegen) sowie eine "günstige" Verbindungen gefunden werden (dutzende von zu wichtenden Parametern wie Reisezeit, Umsteigehäufigkeit, Streckenlänge (Preis), Fahrzeugarten, Aufenthaltszeiten etc). Und dann noch schnell, bitte :-) Allein die Umsetzung der Angaben des Suchenden in eine Abfrage ist eine hohe Anforderung, für die die Bahnauskunft IIRC ein eigenes Verfahren hat (EVAR oder so ähnlich).Vor einigen Jahren gab es mal ein Diskussion über die Zuverlässigkeit der (Hafas-)Bahnauskunft, in der bemängelt wurde, dass die Auskunft bestimmte, preisgünstige und schnelle Verbindungen nicht fände, dafür aber immer IC-Varianten anbot. Man unterstellte, die Suche sei Abzockerei optimiert. Ich denke, der Fehler lag im Suchalgorithmus begründet. Ich hatte mir damals gedacht, dass HAFAS bei der Suche des Weges zunächst bestimmte, zuvor definierte, nahegelegene Zentralorte/Umsteigeplätze sucht, um zwischen ihnen eine Tangente zu bilden. Ist eine solche Hauptstrecke gefunden, arbeit es sich an beiden Enden zu Ziel und Start durch. Sie wuselsn sich also nicht durch den Dantenstand hindurch sondern hierarchisieren und suchen quasi von oben nach unten. So sollte imo die Menge der zu durchsuchenden Strecken minimiert werden und damit ein klarer Geschwindigkeitsgewinn erzielt werden. Nachteil dieser Methode wäre, dass die (in der damaligen Diskussion) Verbindungen über Nebenstrecken im Zweifel unter den Tische fallen. So habe ich mir das jedenfalls erklärt.
Irgendwie gibt es den Fehler anscheinend noch heute. Ich ärgere mich jedenfalls regelmäßig darüber, dass mein lokaler Verkehrsverbund (KVAG, der örtliche Kieler Busunternehmer) HAFAS verwendet, um seinen örtlichen Busverkehr auf einer Diskette elektronisch zugänglich zu machen. Gerade bei so kleinen, verwinkelten Fährplänen wie bei Bussen, wo es keine Hauptstrecken gibt und nicht jeder Umsteigeplatz als solcher sofort erkennbar ist, ist die Fahrplanauskunft eher der gespielte Witz.
Gruß
Swen
-
-
-
Hallo wunderwarzenschwein,
da mach eine PHP -Abfrage, mit "where zug = 4711 and ort=dingenskirchen" .....probieren über studieren...
lisaHi,
habe mir gestern mal wieder darüber Gedanken gemacht, wie eigentlich eine automatische Fahrplanauskunft funktioniert. (wie zB unter http://reiseauskunft.bahn.de).
Die Daten zu speichern ist ja wohl nicht das Problem. Ich habe eine Tabelle mit allen Haltestellen und eine mit allen Zügen (Zugläufen) Die sind über eine weitere Tabelle miteinander verknüpft, wo dann zB gespeichert ist, daß der Zug IC 4711 um 12:34 im Bhf Dingenskirchen hält.
So weit, so gut.
Wie kriege ich jetzt aber eine Verbindung zwischen zwei beliebigen Bahnhöfen gesucht? Alle möglichen Verbindungen ausprobieren kann ja nicht das Wahre sein.Hat da jemand eine Idee, wie sowas funktionieren könnte?
TIA
wunderwarzenschwein
--
Elvis lebt!-
Hi,
da mach eine PHP -Abfrage, mit "where zug = 4711 and ort=dingenskirchen" .....
Dazu muss ich aber wissen, daß der Zug 4711 nach Dingenskierchen fährt.
Aber stell dir mal vor, du hat nichts weiter als zwei Bahnhofsnamen, zwischen denen du eine Verbindung suchst. Du weisst nicht welche Stationen dazwischen liegen.
Du könntest jetzt an einem Bahnhof anfangen und dich von Station zu Station entlanghangeln, aber die Anzahl der Möglichkeiten steigt hier sehr schnell.wunderwarzenschwein
-
-
Hi,
Wie kriege ich jetzt aber eine Verbindung zwischen zwei beliebigen Bahnhöfen gesucht? Alle möglichen Verbindungen ausprobieren kann ja nicht das Wahre sein.
Hat da jemand eine Idee, wie sowas funktionieren könnte?
naja, es gibt da die möglichkeit in einer (vielleicht etwas grösseren) tabelle alle verbindungen zwischen allen anfangs- und endpunkten einzutragen.
aber eben, das kann's auch nicht wirklich sein. bei mehr als drei bahnhöfen, wird die tabelle schon ziemlich gross.gruss
bjoern--
Elvis lebt!nö, elvis ist tot. seit 25 jahren.
-
Hi,
..Ich habe eine Tabelle mit allen Haltestellen und eine mit allen Zügen (Zugläufen) Die sind über eine weitere Tabelle miteinander verknüpft, wo dann zB gespeichert ist, daß der Zug IC 4711 um 12:34 im Bhf Dingenskirchen hält.
So weit, so gut.Das glaube ich eher nicht. Soweit ich mich an Zeiten erinnere, als ich noch hin und wieder das Kursbuch gelesen habe, gab es für jede Zugnummer noch eine Liniennummer. Das wird der Ansatz sein. Man fängt an: Gibt es zwischen dem Start und dem Ziel eine Linie, auf der beide Orte liegen. Wenn nicht, muß man sich weiterhangeln: Gibt es einen Schnittpunkt (Umsteigepunkt) von Linien, die durch die Orte gehen. Und wenn das nicht reicht, immer so weiter. Dazu kann man durch setzen entsprechender Randbedingungen (z.B. Minimierung der Umsteigemöglichkeiten, Minimierung der Reisezeit oder Reisekosten) kommt man dann irgendwie zu einer Lösung. So zumindest würde ich mir das vorstellen. Vielleicht gibt es auch noch zusätzliche Informationen in der DB für häufig genutzte Verbindungen.
Gruß Frank
-
Hi,
wie die das wirklich machen weiss ich net, eine (vereinfachte) Möglichkeit wäre.
Du hast eine weitere Tabelle, in der zu jedem Ort der vorhergehende Ort und der nachfolgende Ort gespeichert ist (Um den kürzesten Weg zu berechnen brauchst Du noch die Zeitdifferenz zwischen den Orten). Willst Du also von Ort A nach Ort B, dann sucht Du zunächst alle Orte, die du von Ort A in einem Schritt erreichen kannst und von diesen Orten wieder alle Orte, die du von diesen Orten in einem Schritt erreichen kannst, bis Du an Ort B angelangt bist. Es läuft also im Prinzip auf ne rekursive Abfrage hinaus.Grüssle Kerstin
-
hi
vieleicht etwas in der richtung:
- suche nach strecke in der beide bahnhöfe vorkommen
- suche nach 2 strecken die einen identischen bahnhof haben
- suche nach 1 strecke die je 1 bahnhof von 2 strecken enthält die von den einzelnen bahnhöfen abgehen. (sowas wie ne tangente :))
usw.
so long
ole
(8-)> -
Moin!
Wie kriege ich jetzt aber eine Verbindung zwischen zwei beliebigen Bahnhöfen gesucht? Alle möglichen Verbindungen ausprobieren kann ja nicht das Wahre sein.
Um kuerzeste oder "beste" Wege in einem beliebigen Wegenetz zu finden, verwendet man normalerweise den A*-Algorithmus, der heuristisch nach moeglichen Kombinationen von Wegverbindungen sucht und diesen dann eine Zahl zuweist, die die Brauchbarkeit des gefundenen Weges bewertet. Dazu wird jedem moeglichen Streckenabschnitt eine Zahl zugeordnet, die die Schwierigkeit des Streckenabschnitts kennzeichnet. Um z.B. die billigste Verbindung zwischen zwei beliebigen Punkten zufinden, wuerde der Algorithmus eben diese "Schwierigkeit" mit dem Preis einer Wegstrecke gleichsetzen, fuer den schnellsten Weg wuerde die Schwierigkeit der Fahrtzeit entsprechen.
A*(sprich A-Star)-Algorithmen werden auf mehreren Spieleseiten beschrieben, z.B. auf http://www-cs-students.stanford.edu/~amitp/gameprog.html. Ist aber fuer Programmieranfaenger nicht unbedingt einfach umzusetzen...
Ciao!
Sebastian