Ankündigung

Einklappen
Keine Ankündigung bisher.

[Erledigt] Kürzester Weg Berechnung (Shortest Path)

Einklappen

Neue Werbung 2019

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

  • [Erledigt] Kürzester Weg Berechnung (Shortest Path)

    Hallo,
    ich bekomme aus einer Datenbank mehrer GPS-Koordinaten und will nun den kürzesten direkten Weg zwischen diesen Punkten berechnen.
    Habe leider noch keinen passenden Algorithmus gefunden.
    Kann mir irgendwer weiterhelfen?
    lG
    Tom


  • #2
    Sind es 2 Punkte? Dann Satz des Pythagoras vielleicht?

    Sonst eventuell http://de.wikipedia.org/wiki/Problem...lungsreisenden

    Bin mir aber nicht sicher, ob ich dich richtig verstanden habe.

    Kommentar


    • #3
      Es sind viel mehr als 2 Punkte!!!
      geh einmal von 10-20 aus!!!

      Kommentar


      • #4
        http://www10.informatik.uni-erlangen...html#Prb%20Hdr

        Ich hoff du hast ne schöne Server-Armada

        Kommentar


        • #5
          hat doch nix mit dem handlungsreisenden zu tun.

          nimm den startpunkt, gehe zum naechstgelegenen punkt, von da aus wieder zum naechstgelegenen punkt, ausser natuerlich den schon besuchten, usw. gut is. das is sicherlich in endlicher zeit berechenbar
          Was ist validität?

          Kommentar


          • #6
            Moin,

            @fantast: Dein System funktioniert nicht. Was ist, wenn du eine Reihe von Punkten, in unterschiedlichen Abständen hast, die verbunden eine Senkrechte Linie bilden würden. Der Startpunkt ist in der Mitte, über ihm 27 und unter ihm 2 Punkte. Daher der nächstgelegen Punkt relativ zum Startpunkt, der da drüber ist, führt dich der Weg nach oben, bis du beim obersten bist. Du hast aber unter dem Startpunkt auch noch Punkte. Daher aber zuerst der Lange weg abgegangen wird...gehst du den langen zweimal. Nach unten gehen, wäre klüger gewesen, weil man dann 2mal einen küurzeren WEg gelaufen wäre und nur einmal den langen.

            Ganz so einfach geht das also nicht.

            wilko :wink:

            Kommentar


            • #7
              und will nun den kürzesten direkten Weg zwischen diesen Punkten berechnen
              Genau das ist das "Problem des Handlungsreisenden" (nur eben mit der Einschränkung, wohl nicht mehr zum Startpunkt zurückkehren zu müssen)

              Wikipedia zum Problem des Handlungsreisenden
              Es modelliert die Frage, wie man möglichst schnell oder billig mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt.

              Kommentar


              • #8
                gut ich bin ueberstimmt. bei genauerer betrachtung faellt mir das auch auf. mein algorithmus loest dieses problem nicht, bzw. wird in eher seltenen faellen den kuerzesten weg finden. stimmt. aber er is schnell
                Was ist validität?

                Kommentar


                • #9
                  Algorthmus:

                  stelle ne Tabelle auf mit allen möglichen wegpunkten.

                  Starte bei Start, alle möglichen zielpunkte die erreichbar sind schreibst du jetzt die zeit(oder km) rein, die du brauchst um das zu erreichen.

                  --> erstelle ne neue Tabelle, gehe nun vom punkt mit der geringsten Zeit aus weiter. --> wieder alle erreichbaren punkte in die tabelle eintragen. --> ist der wert größer als der der schon drinsteht(falls einer drinsteht), dann schreib die kleinere zahl rein.

                  --> nächste Tabelle erstelle. punkt1 (start) und 2(kürzeste Zeit von 1 au) sind fertig. --> aber immer schön mit schreiben --> wähle nun wieder den punkte mir der kleinesten Zeit .... und wieder alle rerreichbaren punkte durchmachen... etc.

                  hoffe du hast verstanden wies geht?!! net so einfach zu erklären, aber probiers mal aus, dann wirst es schon hinbekommen. am besten rechnen mal ein beispioel von hand durch, dann verstehst leichert wie es funktioniert#

                  --> statt immer ne neue Tabelle zu machen, kannst au nur ne neue Zeile hinzufügen, wäre wohl einfacher und besser.


                  Bsp:
                  Tabelle:
                  p1 p2 p3 p4 p5
                  Zeit 0 - - - -
                  0 5 - 7 - <-- wähle p2 aus..
                  Gruß HaVoK

                  Kommentar


                  • #10
                    Bei google mal nach Dijkstra und/oder Floyd-Warshall suchen.

                    Kommentar


                    • #11
                      Die Berechnung wird etwas dauern....

                      Das nennt sich, auch wenns einfach klingt, das "Kürzeste-Wege-Problem" (Domschke und Drexel). Berechnung der Zeit entspricht der Laufzeitkomplexität.

                      Die sog. Laufzeitkomplexität O beträgt dabei O(n^2). n ist die Anzahl der Knotenpunkte.

                      Bei heutigen PC's kann man ganz grob sagen, dass n^2 der Sekunden entspricht, die er rechnet

                      Somit wirst du für die Berechnung von 20 Knoten wahrscheinlich etwas mehr als eine Stunde brauchen. Bei vorherigen Algorithmus wird das wohl der Fall sein.

                      Musst halt entscheiden ob du so lange warten willst

                      Kommentar


                      • #12
                        Habe leider noch keinen passenden Algorithmus gefunden.
                        http://en.wikipedia.org/wiki/Great_circle_distance ?

                        Kommentar


                        • #13
                          Nein, in der Frage steht nichts von einer Kugel.

                          http://en.wikipedia.org/wiki/Great_circle_distance
                          Because spherical geometry is rather different from ordinary Euclidean geometry, the equations for distance take on a different form

                          Kommentar


                          • #14
                            Nein, in der Frage steht nichts von einer Kugel.
                            Auf was beziehen sich da die GPS-Koordinaten ?

                            Kommentar


                            • #15
                              grmpf, habe ich mal wieder übersehen.

                              Kommentar

                              Lädt...
                              X