A* und Dijkstra-Algos in PHP

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • A* und Dijkstra-Algos in PHP

    Hallo Leute,

    hat sich jemand von Euch schonmal mit A*- und Dijkstra-Algorithmen
    in PHP beschäftigt?

    Im Detail geht es um einen Routenplaner für Bahnfahrten, der einmal
    ohen Heuristik (Dijkstra) und einmal mit Heuristik (A*) arbeiten
    soll.

    Als Basis habe ich ein Programm, was vor einigen Jahren mal in
    C geschrieben wurde. Allerdings kenne ich mich nicht sehr gut
    mit den Algorithmen aus, da ich Raumplaner und kein Informatiker
    bin.

    Würde mich über Kooperationen freuen.

    Viele Grüße
    Tobias

  • #2
    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.
    Webdesign und Webentwicklung - Plunix.de

    Kommentar


    • #3
      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.

      Kommentar


      • #4
        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.
        Zuletzt geändert von Lennie; 07.03.2007, 20:19.
        Webdesign und Webentwicklung - Plunix.de

        Kommentar


        • #5
          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!

          Kommentar


          • #6
            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.

            Kommentar


            • #7
              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.
              Webdesign und Webentwicklung - Plunix.de

              Kommentar


              • #8
                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

                Webdesign und Webentwicklung - Plunix.de

                Kommentar


                • #9
                  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.

                  Kommentar


                  • #10
                    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.


                    Zuletzt geändert von Lennie; 07.03.2007, 20:37.
                    Webdesign und Webentwicklung - Plunix.de

                    Kommentar


                    • #11
                      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.
                      Zuletzt geändert von TobWen; 07.03.2007, 20:38.

                      Kommentar


                      • #12
                        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.

                        Kommentar


                        • #13
                          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. ^^
                          Webdesign und Webentwicklung - Plunix.de

                          Kommentar


                          • #14
                            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.

                            Kommentar


                            • #15
                              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.
                              Webdesign und Webentwicklung - Plunix.de

                              Kommentar

                              Lädt...
                              X