A* und Dijkstra-Algos in PHP

**Lennie** · 07.03.2007, 19:12

Hallo,
Weist du denn in welcher Form du welche Daten zur verfügung hast?
Das wäre zum Berechnen des A*-Algorythmus durch erst einmal zu wissen.

**TobWen** · 07.03.2007, 19:17

Gegeben sind:
- der Graph mit topologischen Beziehungen (Trassen mit Entfernungen der einzelnen Bahnhöfe in Tarifkilometern und Minuten)
- Kanten (Endbahnhöfe)
- Knoten (Trassenüberschneidungen)

Daraus könnt man natürlich nur mit Dijkstra (oder schlechter) ans Ziel kommen.

Für A* brauche ich ja noch mehr Informationen und da ist mir folgende Idee gekommen:
Ich kann die Koordinaten der Gemeinden oder der Bahnhöfe als Heuristik nehmen. Diese stehen mir ebenfalls zur Verfügung, allerdings müsste ich die Tabellen noch über einen gemeinsamen Schlüssel joinen .

Man kann aus den Koordinaten ja die Luftlinie und den Lagekurs bestimmen, also z.B. 239°, 350km. So läuft man erstmal in die richtige Richtung und nicht, wie Dijkstra kreisförmig in alle Richtungen.

**Lennie** · 07.03.2007, 20:14

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.

Ort A -> Ort B = 100 km
Strecke x +/-50 __100km

(kann es nicht besser veranschaulichen)

Mit diesem Auschließen fallen doch in dem falle gleich alle ergebnisse ab, die in eine andere richtung verlaufen, da diese die maximal länge überschreiten. mit weiteren angaben könnte man die angaben +/- um ein paar kilometer verlängern, sollte keine strecke gefunden werden.

Wenn es sich bei diesen Angaben allerdings wie ich verstanden habe um Bahnhöfe und Bahnstrecken handelt, wird der Algorythmus um einiges Komplizierter, wenn man Wartezeiten bzw. unterbrechungen beachten möchte.

**PHP-Desaster** · 07.03.2007, 20:24

ich kenne den A*-Algo nicht, aber den Dijkstra. Ich nehme mal an, der A* sucht in eine Richtung anstatt kreisförmig!
Was ist denn jetzt genau das Problem? Im Grunde musst deinen C-Code "lediglich" in PHP implementieren!

**TobWen** · 07.03.2007, 20:26

Original geschrieben von Lennie
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.

Klar, die einfachste Methdoe wäre natürlich alle möglichen Verbindungen abzulaufen und alle gefundenen Wege in einer Datenbank zu speichern.

Heute ist diese Methode okay, weil genug Kapazität bereit steht.
Vor ein paar Jahren wäre das noch undenkbar gewesen.

Aber mein Problem ist eher, dass er erstmal den Weg suchen muss.

Man kommt von Dortmund über Köln nach Frankfurt, wenn man in Koblenz umsteigt. Man kommt von Dortmund aber auch über Siegen nach Frankfurt, wenn man in Siegen umsteigt.

Die Wartezeiten und so sind erstmal nebensächlich, ich möchte nur etwas mit dem "Finden" experimentieren.

Das Problem, was die Algos ohne Heuristik haben sind, dass sie nicht wissen, woe z.B. Frankfurt liegt. Sie laufen also von Dortmund mal eben nach Hamburg und öffnen so lange Knoten, bis sie am Ende sind oder der Zweig unten Frankfurt gefunden hat.

**Lennie** · 07.03.2007, 20:27

Es geht darum das in einem A* der direkteste (damit auch der kürzeste) weg gefunden wird.
Nun sind wir bzw. er auf der Suche nach einer Methode wie er am besten/einfachsten/sinnvollsten seinen Code baut, um an die A* Strecke zu kommen.

**Lennie** · 07.03.2007, 20:30

Das habe ich nun übersehen. In diesem Falle müsste doch aber Bei Bahnstrecken bekannt sein welche Schienen so ungefähr in diese richtung gehen. hierfür wirst du aber auch erst einmal mit ungefähren graden arbeiten müssen +/-

EDIT:

Sorry für doppelpost

**TobWen** · 07.03.2007, 20:31

Original geschrieben von Lennie
Es geht darum das in einem A* der direkteste (damit auch der kürzeste) weg gefunden wird.
Nun sind wir bzw. er auf der Suche nach einer Methode wie er am besten/einfachsten/sinnvollsten seinen Code baut, um an die A* Strecke zu kommen.

Mir ist es eigentlich vorläufig gar nicht sooo wichtig die kürzeste Strecke zu finden, sondern überhaupt eine Strecke zu finden.
A* und Dijkstra bieten laut Literatur jedoch die besten Ansätze dafür.
Es gibt ja noch BFS, DFS, Greedy und viele mehr (vgl. Wikipedia).

Lennies Ansatz wäre ja BFS. Dann kann man schön nachher selektieren, welche Route am Besten ist.

Ich vermute, dass im C-Programm bereits Dijkstra verwendet wurde, weil die Berechnung teuflich schnell und genau geht. Für A* sind im Datensatz aber (meines Erachtens) nicht genug Informationen, um die Suchrichtung zu finden.

Daher wäre vorerst eine Umsetzung mit Dijkstra mein Herzenswunsch und nachher, wenn ich die Geokoordinaten eingebunden habe, eine Erweiterung nach A*:

Gehe von Dortmund nach Süden, denn da ist Frankfurt.
Gehe von Dortmund nicht nach Norden, denn da ist Frankfurt nicht.

**Lennie** · 07.03.2007, 20:33

Wie umfangreich ist denn das Programm? Möglicherweise übersehen wir den Aspekt, das sämtliche mögl. routen schon bekannt sind.
was auch der beschriebenen geschwindigkeit zupassen würde.

**TobWen** · 07.03.2007, 20:34

Original geschrieben von Lennie
Das habe ich nun übersehen. In diesem Falle müsste doch aber Bei Bahnstrecken bekannt sein welche Schienen so ungefähr in diese richtung gehen. hierfür wirst du aber auch erst einmal mit ungefähren graden arbeiten müssen +/-

Anhand der Kursdaten weiß ich ja, welche Bahnhöfe angefahren werden (Beispiel ohne Realitätsbezug):

Dortmund - Hagen - Wuppertal - Köln - Bonn - Koblenz || Koblenz - Frankfurt

Nur Dijkstra weiß nicht, dass die trasse Dortmund - Koblenz [...] auch irgendwann nach Frankfurt führt, weil man ja in Koblenz umsteigen muss.

Dijkstra und auch alle anderen laufen alle Dortmund - Koblenz ab und klappen auf dem Weg alle Knoten auf und gucken, ob irgendwann Frankfurt hinten rauskommt.

**TobWen** · 07.03.2007, 20:38

Original geschrieben von Lennie
Wie umfangreich ist denn das Programm? Möglicherweise übersehen wir den Aspekt, das sämtliche mögl. routen schon bekannt sind.
was auch der beschriebenen geschwindigkeit zupassen würde.

Das Programm ist ziemlich simpel. Ein Großteil beschräftigt sich mit dem Einlesen der Datenbanken: Bahnhöfe, Bahnhofsnummern, Entfernung auf Basis von Tarifkilometern und die Trassen.

Die eigentliche Kalkulation ist ziemlich gering.
Ich kann Dir gerne den Sourcecode mal zukommen lassen, falls Du C lesen kannst.

**Lennie** · 07.03.2007, 20:38

Da muss ich jetzt allerdings passen. ohne weitere informationen wüsste ich keine andere methode. und ohne weitere einschränkungen wie ungefähre richtung wüsste ich nicht, wie ich auf eine schnelle ausgabe finden könnte.

PS: nein meine fehler in php reichen mir. ^^

**TobWen** · 07.03.2007, 20:41

Original geschrieben von Lennie
Da muss ich jetzt allerdings passen. ohne weitere informationen wüsste ich keine andere methode. und ohne weitere einschränkungen wie ungefähre richtung wüsste ich nicht, wie ich auf eine schnelle ausgabe finden könnte.

Vielleicht sind doch irgendwelche Positionsangaben in den Bahnhofsnummern kodiert - ähnlich wie bei den Postleitzahlen.

Aber, wie gesagt: Anhand der Geodaten kann man ja einfach eine Richtung ausmachen ... wir könnten das ganz ja erstmal im "kleinen" Simulieren, wenn Du Bock auf das Projekt hast.

100%ig unkommerziell.

**Lennie** · 07.03.2007, 20:47

Hallo,
Momentan bin ich leider nicht in der Lage mich großartig mit Programmieren zu beschäftigen.
In den ferien steht dann erstmal mein CMS und ein paar kleinaufträge aus.
Ich könnte allerhöchstens gegen den 10. april mit sowas beginnen. allerdings kann ich dir auch da nicht 100% zusagen. Ein gewisses interesse habe ich allerdings schon.

A* und Dijkstra-Algos in PHP