AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

route berechnen?

Ein Thema von Newbie44 · begonnen am 15. Mai 2007 · letzter Beitrag vom 15. Mai 2007
Antwort Antwort
Seite 1 von 3  1 23   
Newbie44
(Gast)

n/a Beiträge
 
#1

route berechnen?

  Alt 15. Mai 2007, 15:55
Hallo,

ich hab mal eine frage an alle hier, die sich mit navigation schon mal beschäftigt haben. es geht nicht um eine spezielle programmiersprache (is ja eh alles sehr ähnlich)

Wie macht man einen Navigationsalgorythmus? Hat jemand schon mal sowas gemacht, bzw hat es vor das ganze zu machen? Ich bin heute nämlich mit nem Navigationssystem gefahren und finde es einfach nur genial.

Die Route war perfekt, schön kurz und ich bin rechtzeitig angekommen.

Jedoch wie sieht so ein algorythmus aus?

gruß

sebastian
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#2

Re: route berechnen?

  Alt 15. Mai 2007, 15:58
Hi,

der A*-Algorithmus, den ich für mein Snake nutze, falls du das mitverfolgt hast, kann auch für Navis eingesetzt werden. Siehe hierzu auch das Beispiel von Wikipedia.

Edit: Wieso geht denn diese URL nicht mit den [url]-Tags? Naja, dann so: http://de.wikipedia.org/wiki/A*-Algorithmus#Beispiel
  Mit Zitat antworten Zitat
Newbie44
(Gast)

n/a Beiträge
 
#3

Re: route berechnen?

  Alt 15. Mai 2007, 16:04
hey danke, wusste gar nicht das es schon so nen algo gibt. aber ich finde es echt beeindruckend was heutzutage schon alles möglich ist. aber seit ich auf die navigation gekommen bin, find ich es spannend wie das alles funktioniert.

Bin mal gespannt auf das Galileo Navigationssystem

ach ja dann noch ne frage, kennt jemand ne navigationssoftware die opensource ist, damit man sich das ganze mal ansehen kann?

@Matze

Hab leider dein Thema nicht verfolgt, bin ja auch nur noch selten online
  Mit Zitat antworten Zitat
Der_Unwissende

Registriert seit: 13. Dez 2003
Ort: Berlin
1.756 Beiträge
 
#4

Re: route berechnen?

  Alt 15. Mai 2007, 16:05
HI,
der konkrete Algorithmus dürfte sicherlich je nach System etwas anders ausfallen, aber an sich kannst Du Dich ganz einfach vom Routing insperieren lassen. Daten von einer IP-Adresse an eine andere zu leiten ist selten direkt möglich, auch hier geht es also um nichts anderes als eine Route (einen Weg) zu finden. Zudem wird beim Routing auch gleich versucht Staus u.Ä. zu berücksichtigen.

Bei Navigationssystemen dürfte der Ansatz prinzipiell ähnlich funktionieren (ohne Gewähr!). An sich bietet es sich aber schon an, dass Du einfach mit Graphenalgorithmen arbeitest. Dabei wird nicht jede Straße gleich bewertet, man wird sicherlich eher mit verschieden großen Rastern arbeiten (z.B. lässt sich der kürzeste Weg von einer Stadt in eine andere getrennt vom Weg in den jeweiligen Städten betrachten!). Ähnlich dürfte es dann wiederum in einzelnen Städten aussehen, da gibt es schließlich auch wieder Bezirke (bzw. eine Rasterung), so dass man erstmal nur die kürzeste (besser gesagt schnellste/kostengünstigste) Route in den entsprechenden Sektor sucht und erst von dem Punkt aus weiter ins Detail geht (die eigentliche Straße).

Gruß Der Unwissende

[roter Kasten]
A*, Dijkstra, ... sind dann alles mögliche Algorithmen um einen kürzesten Weg zu finden. Wie gesagt, Graphenalgorithmen eben
[/roter Kasten]
  Mit Zitat antworten Zitat
Benutzerbild von leddl
leddl

Registriert seit: 13. Okt 2003
Ort: Künzelsau
1.613 Beiträge
 
Delphi 2006 Professional
 
#5

Re: route berechnen?

  Alt 15. Mai 2007, 16:06
Zitat von Newbie44:
hey danke, wusste gar nicht das es schon so nen algo gibt.
Wie sollte dein Navi doch sonst geleitet haben? Und warum fragst du dann danach?
Axel Sefranek
A programmer started to cuss, cause getting to sleep was a fuss.
As he lay there in bed, looping round in his head
was: while(!asleep()) ++sheep;
  Mit Zitat antworten Zitat
Udontknow

Registriert seit: 17. Jun 2002
223 Beiträge
 
#6

Re: route berechnen?

  Alt 15. Mai 2007, 16:12
Hallo!

In diesem Tutorial habe ich mal per Backtracking die Wegfindung realisiert, vielleicht hilft es ja.

Cu,
Udontknow
  Mit Zitat antworten Zitat
Newbie44
(Gast)

n/a Beiträge
 
#7

Re: route berechnen?

  Alt 15. Mai 2007, 16:13
Zitat von Der_Unwissende:
HI,
man wird sicherlich eher mit verschieden großen Rastern arbeiten
da is was dran mit den rastern, is mir auch aufgefallen, das navi zeigt ja nicht alle straßen auf einmal an, in den verschiedenen zoom größen. je näher man rangeht, desto mehr details findet man.

es könnte auch so sein, das das navi erst die großen strassen berechnet, und dann die kleinen, sprich erst den groben weg, und den dann noch optimiert.

wäre das denkbar oder zu unhandlich?
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#8

Re: route berechnen?

  Alt 15. Mai 2007, 16:16
Zitat von Newbie44:
wäre das denkbar oder zu unhandlich?
Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen), sofern diese nicht zu allzu großen Umwegen führen. Dann werden kleinere Straßen berücksichtigt, wenn es beispielsweise durch Orte geht oder man in Zielnähe ist bzw. auf dem Weg zu Schnellstraßen. Natürlich müssen Einbahnstraßen berücksichtigt werden.

Das fand ich kürzlich so faszinierend: Das Navi lotste uns einmal im Kreis herum und ich wunderte mich, was das soll, habe dann jedoch gesehen, dass man nicht direkt links abbiegen durfte, wo wir hin mussten und so machte das Navi einen intelligenten Bogen.
  Mit Zitat antworten Zitat
Newbie44
(Gast)

n/a Beiträge
 
#9

Re: route berechnen?

  Alt 15. Mai 2007, 16:22
das stimmt, das wäre die beste lösung zum navigieren. aber wenn man mal mit knotenpunkten rechnet, nur mal bei autobahnen, das sind ja da schon viele, aber es gibt enorm viele knotenpunkte die man beachten müsste.

das navi müsste die ja alle durchprüfen, was jetzt der beste weg wäre, eigentlich müsste dsa ja länger dauern, es geht aber immer unheimlich schnell, das is das was mich so wundert.

scheint ein ziemlich schneller algorithmus zu sein
  Mit Zitat antworten Zitat
Benutzerbild von leddl
leddl

Registriert seit: 13. Okt 2003
Ort: Künzelsau
1.613 Beiträge
 
Delphi 2006 Professional
 
#10

Re: route berechnen?

  Alt 15. Mai 2007, 16:27
Zitat von Matze:
Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen
Das kommt natürlich drauf an, was der Zweck der Routenberechnung ist
Im Normalfall kannst du zwischen schnellster und kürzester Route (und evtl. noch diverse anderen) wählen. Ich zB lasse immer die kürzeste berechnen und manchmal verbiete ich Autobahnen sogar komplett, da ich ganz genau weiß dass ich auf Bundes- und Landstraßen *hüstel* ein bißchen schneller unterwegs bin, als das Navi es vorsieht
Und dann werden aber wirklich nicht unbedingt die größten möglichen Straßen gewählt, sondern dann findet man sich ganz schnell auch mal auf nem kleinen Feldweg wieder, weil man damit die 100m Umweg einer Kurve spart

//Edit:
Zitat von Newbie44:
das stimmt, das wäre die beste lösung zum navigieren. aber wenn man mal mit knotenpunkten rechnet, nur mal bei autobahnen, das sind ja da schon viele, aber es gibt enorm viele knotenpunkte die man beachten müsste.

das navi müsste die ja alle durchprüfen, was jetzt der beste weg wäre, eigentlich müsste dsa ja länger dauern, es geht aber immer unheimlich schnell, das is das was mich so wundert.
Ich gehe davon aus, dass bereits durch heuristische Verfahren ein ungefährer Weg errechnet wird, wodurch dann sehr viele Wege gar nicht mehr berechnet werden müssen. Wenn dann noch die dynamische Programmierung angewendet wird, fallen wieder einige Wege weg, so dass die endgültige Menge an vollständig zu berechnenden Wegen halbwegs überschaubar sein wird.
Axel Sefranek
A programmer started to cuss, cause getting to sleep was a fuss.
As he lay there in bed, looping round in his head
was: while(!asleep()) ++sheep;
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:17 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz