A* und Dijkstra-Algos in PHP

[Lennie]

wenn ich in ein paar jahren es endlich geschafft haben sollte mich durch php zu hecheln ^^ dann fang ich ja vllt mit c/c++ an. momentan reicht mir noch php

Sorry, lrs ist wieder durchgesickert

[TobWen]

Original geschrieben von closure
@tobwen
ok, dann fällt c++ flach.
PM schicken geht hier nicht, bzw. nicht so ohne weiteres.

Wenn C++ aber schon die Bibliotheken anbieten, muss ich halt den Hoster wechseln oder einfach lokal arbeiten. Bei einem konstruktiven System (heißt das bei euch so?), muss sowas ja sowieso klappen.

[TobWen]

Original geschrieben von penizillin
tobi, hast du eine konkrete aufgabe? oder willst du einfach über _eine mögliche_ implementierung sprechen?

wenn du konkreter wirst, erhält die diskussion u.u. einen sinn.

Es gibt keine Aufgabe, sondern viel mehr die Herausforderung, einen eigenen Routerplaner zu schaffen.

Da ich ÖPNV-Fan bin (ja, sowas gibt es), habe ich starkes Interesse an einer Implemention und durch mein Studium habe ich Zugänge zu allen Daten, die ich dafür benötige.

[penizillin]

dann fang die planung mal weiter außen an: was soll die anwendung können, wer soll sie benutzen und wie, lege dich auf eine plattform fest.

so kannst du dich selbst vor konkrete aufgaben stellen, sie zu lösen ist dann "nur noch" programmierung.

[PHP-Desaster]

ich weiß jetzt gar nicht, was genau topicersteller denn haben möchte?? also, den dijkstra habe ich bereits mal in c++ programmiert, da wäre eine Portierung nach php bestimmt machbar! wenn deine knoten(bahnhöfe) alle die passenden Verbindungen in deinem Graphen haben, dann weiß ich ehrlich gesagt nicht, wo das Problem ist...

[TobWen]

@penizillin:
Ich möchte einen Startbahnhof, einen Zielbahnhof und (falls möglich) einen oder mehrere Zwischenbahnhöfe eingeben.

Herauskommen soll eine Liste mit Routen (also Strecken) vom Start zum Ziel, gegebenfalls über den Zwischenbahnhof (Via). Es wird ja sicher nicht nur einen wenig geben - der kürzeste ist natürlich von Vorteil, aber der Algorithmus darf auch "nicht kurze" finden und ausgeben.

@PHP-Desaster:
Die Programmierung der Realität ist mein Problem. Ich kann Dir gerne zur Referenz das Original C-Programm zukommen lassen.

[penizillin]

was ein routenplaner ist, ist mir bekannt, doch leider beantwortet das immer noch nicht alle fragen. soll es eine stand-alone applikation sein? willst du dich auf c++ festlegen? welche datenstruktur nimmst du? adjazenzmatrix? hat stl evtl. etwas geeignetes? welche strukturen verwenden andere applikationen, die die a-stern-suche implementieren?

[TobWen]

Original geschrieben von penizillin
was ein routenplaner ist, ist mir bekannt, doch leider beantwortet das immer noch nicht alle fragen. soll es eine stand-alone applikation sein? willst du dich auf c++ festlegen? welche datenstruktur nimmst du? adjazenzmatrix? hat stl evtl. etwas geeignetes? welche strukturen verwenden andere applikationen, die die a-stern-suche implementieren?

Tut mir leid. Ich hätte eigentlich gerne eine PHP-Version gehabt, da ich gut in PHP programmieren kann und so gewährleistet ist, dass sie auf vielen Servern funktioniert. Leider ist der Interpreter wohl nicht effizient genug, daher bleibt wohl nur eine Konsolenvariante, die dann unter Linux im Hintergrund aufgerufen wird und die Ausgabe vom PHP-Script ausgewertet wird. Antwort also: Stand-Alone. Nachteil ist, dass ich da jetzt nicht mitwirken kann :-(

Bislang kannte ich Adjazenzmatrixen nicht, aber Wikipedia hat mir einen kurzen Einblick dazu verschafft. Die Antwort ist daher: Nein, verwende ich nicht. Wenn ich aber herausfinde, wie diese Matrixen aufgebaut werden, kann ich meinen Datensatz dahingehend ändern.

Leider kenne ich, außer ArcGIS und diversen Routenplanern, kein Anwendung welcher A-Stern-Suchen durchführen können. ArcGIS verwendet SQL, gefüttert mit dBase-Dateien. Die Routernplaner wären proprietäre Datenbanken nutzen.

[penizillin]

in welcher form liegen die daten bei dir denn vor?

[TobWen]

Momentan noch sehr chaotisch, da undokumentiert, vom Vorprogrammierer.

Eine Datei mit Bahnhöfen, eine Datei mit Strecken und Knotenpunkten, eine Datei mit Tarifkilometern (der Schienenentfernung) zwischen zwei Bahnhöfen, eine Datei mit "Leitpunkten".

Das Programm diente ursprünglich dazu, Tarifkilometerpreise zu berechnen, hat allerdings auch die Wege ausgeworfen, die ja Basis zur Berechnung waren.

Ich kann sie allerdings aufbereiten, Beispiel (KBS = Kursbuchstrecke):

KBS 431: Soest [Knoten];Westönnen;Werl;Hemmerde;Lünern;Unna [Knoten];Holzwickede [Knoten];Dortmund-Sölde;Dortmund-Aplerbeck;Dortmund-Hörde[Knoten];Dortmund Signal Iduna Park[Knoten]; Dortmund Hbf[Knoten]

Anstatt der Namen würden dann natürlich die Bahnhof-Nummern da stehen.

[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)

[TobWen]

@Shurakai: Natürlich wäre es schön, APSPs zu haben, um Alternativrouten anbieten zu können. Routenplaner, wie z.B. von der Bahn, werfen "leider" nur kürzeste Wege aus und man muss sie mit Hilfe von Vias (Zwischenbahnhöfen) zum Umlegen zwingen.

[penizillin]

soweit ich weiß benutzen "große" routenplaner a-stern. man kann sich aber auch sicher sein, dass die streckenänderungen äußerst selten stattfinden und man (z.b. heuristisch) immens viele strecken cachen kann (ich wette fast, bahn.de berechnet nicht jedes mal "berlin-münchen mit ice" aufs neue).

tobi, die dateistruktur ist mir nicht klar, wobei ich grundsätzlich dazu raten würde, die daten in eine db zu verlegen. trotzdem ist es enorm wichtig, sich für dir richtige tabellenstruktur zu entscheiden.

[TobWen]

@penizillin: Klar, das Caching kann man ja immer noch einfügen, das ist ja kein Problem.

Klar will ich die neue Dateistruktur in der Datenbank vernünftig anlegen. Das was ich gepostet habe, waren die Verbindungen der Kursbuchstrecke 431 von Soest nach Dortmund.

Das waren die einzelnen Haltepunkte und wo [Knoten] hinter stand, kreuzen sich zwei Bahnlinien, z.B. in Soest fährt ein Zug über Hamm weiter ins Ruhrgebiet oder andersrum nach Paderborn. In Unna fährt ein Zug bis Venlo und ein anderer über Hamm nach Münster.

Von Werl aus kommt man über Unna nach Hamm und über Soest.
Die Fahrt über Unna ist schneller. Ich habe auch die Beziehungen der Haltepunkte untereinander: Einmal die Fahrtzeit laut Fahrplan und die Tarifkilometer. Wobei ich mich lieber auf die Fahrtzeit festlegen will, weil die Tarifkilometer mittlerweile nicht mehr von der Bahn offiziell herausgegeben werden.

Als heuristische Funktion, die A* braucht, könnte man jetzt (wie oben gesagt) eine Himmelsrichtung aus den Koordinaten der Gemeinde ableiten:

Hamm ist "links oben" von Werl. Also führt der Wegs nach "links" über Unna und dann nach "oben" von Unna nach Hamm. Diese Variante lässt aber die Verbindung über Soest ("rechts" von Werl) außer betracht.

Ist das ein Nachteil von A* ? Es könnte ja auch sein, dass die Soester Verbindung schneller ist.

[TobWen]

Ich male morgen mal ein Beispiel auf.