| Autor |
Beitrag |
benorth
Hält's aus hier
Beiträge: 6
|
Verfasst: Mo 27.01.03 12:36
Hallo,
hat jemand eine Idee wie man einen Routenplaner programmiert?
Speziell die Logik: Wie komme ich z.B. von Punkt A nach Punkt Z?
|
|
foxy
 
Beiträge: 814
Ubuntu, Gentoo
C++, PHP, Java, Ruby, Perl (Eclipse)
|
Verfasst: Mo 27.01.03 13:07
also ich kann nur mal verdacht äussern ....
also als erstes würde ich ma ne DB machen, in denen alle Städte und Dörfer mit Breiten und längengrad sind...
ich denke das diese angaben man im i-net findet sprich schon fertig als db (denk ich mal) wenn du das hast, würde ich als ersten schritt erst mal die Luftlinien entfernung ausrechen...
um genaue angaben zu haben brauchst du das gesamte Strassennetz ....
ma ne andere Frage wiso willste sowas machen?? iss wirklich denke ich sehr kompliziert und benötigt eine grosse DB, die auch nicht einfach verwaltbar ist oder täuch ich mich (bitte um berichtigung)
aber ich denke so müsste es gehn zumindest der ansatz der mir spontan einfällt ......  _________________ "Only wimps use tape backup: real men just upload their important stuff on ftp, and let the rest of the world mirror it." (Linus Torvalds)
OperatingSystem Laptop (Ubuntu Hardy)
|
|
Udontknow
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mo 27.01.03 13:07
Hi!
Nun, also ein Routenplaner ist schon ein wenig komplizierter.
Du musst dafür Rekursion benutzen. Ausserdem benötigst du ein Knotennetz (den Strassenplan). Deiner rekursiven Prozedur übergibst du den Startknoten als Parameter.
Innerhalb der Prozedur schaust du dann, ob der übergebene Knoten der Zielknoten ist. Ist er es nicht, müssen die mit dem überprüften Knoten verbundenen Knoten per Rekursion überprüft werden.
Das ist nur die grundlegende Vorgehensweise. Wenn du Fragen hast, poste einfach mal.
Google mal nach "Back-Tracking" bzw. "Travelling Salesman" (wobei TSM eine erweiterte Problematik der Routenplanung darstellt).
Cu,
Udontknow
|
|
foxy
Beiträge: 814
Ubuntu, Gentoo
C++, PHP, Java, Ruby, Perl (Eclipse)
|
Verfasst: Mo 27.01.03 13:09
hör lieber auf udont ... der hat denke ich mehr erfahrung damit _________________ "Only wimps use tape backup: real men just upload their important stuff on ftp, and let the rest of the world mirror it." (Linus Torvalds)
OperatingSystem Laptop (Ubuntu Hardy)
|
|
benorth 
Hält's aus hier
Beiträge: 6
|
Verfasst: Mo 27.01.03 14:08
Ich brauche den Routenplaner nur für eine Kleinstadt. Straßennetz hab ich bereits in einer DB. Problem ist nur, dass ich nicht auf andere Programme zurückgreifen kann, da der Routenplaner ein Teil eines größeren Programms ist.
Das mit der Rekursion habe ich nicht ganz verstanden. Vorallem müssten in der Datenbank auch die Länge der Straße bzw. sämtliche Kreuzungen (=Knoten) stehen. Woher weiß das Programm wo er abbiegen soll um schnellstmöglich das Ziel zu erreichen? Ich müsste so praktisch das ganze Straßennetz der Stadt "virtuell" aufbauen.
|
|
Udontknow
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mo 27.01.03 15:01
Schau mal in der Sparte Tutorials nach "Rekursion", dort bin ich ein Tutorial am basteln. Ich werde im Laufe des Tages das Tut soweit erweitern, daß du dann einen Routenplaner schreiben kannst.
Cu, 
Udontknow
|
|
UGrohne
Beiträge: 5502
Erhaltene Danke: 220
Windows 8 , Server 2012
D7 Pro, VS.NET 2012 (C#)
|
Verfasst: Mo 27.01.03 15:05
Da gibts auf [url] www.derentwickler.de[/url] vielleicht einen Artikel dazu. Auf jeden Fall war in einer der letzten Zeitschriften der A+-Algorithmus beschrieben, mit dem man sowas machen kann. AUf der CD war ein Beispiel-Programm dabei, wo man auch eigene Pläne erstellen konnte, incl. Source. Vielleicht schauste da mal nach. Aber es ist nicht einfach!
Gruß
|
|
Udontknow
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mo 27.01.03 16:54
Hallo nochmal,
ich habe eine Demo fertig geschrieben, das Programm und die Quellen dazu könnt ihr hier downloaden.
Cu, 
Udontknow
|
|
littlemike1005
Beiträge: 187
|
Verfasst: Mo 27.01.03 17:17
@Udontknow
Hut ab. SUPER.
|
|
benorth
Hält's aus hier
Beiträge: 6
|
Verfasst: Mo 27.01.03 17:29
Wow. Respekt !!
Werd das Programm gleich mal durchschauen.
Vielen Dank.
|
|
Udontknow
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Mo 27.01.03 18:43
@littlemike: Thx.
|
|
Andreas L.
Beiträge: 1703
Erhaltene Danke: 25
Windows Vista / Windows 10
Delphi 2009 Pro (JVCL, DragDrop, rmKlever, ICS, EmbeddedWB, DEC, Indy)
|
Verfasst: Mo 27.01.03 18:59
Der Routenplaner ist sehr gut. RESPEKT. Wäre natürlich toll wenn du ihn in Farbe und mit Stadtteilen ausstatten könntest.
|
|
littlemike1005
Beiträge: 187
|
Verfasst: Mo 27.01.03 19:42
@onlinehome Udontknow hat doch den source auch veröffentlicht. deine gewünschten änderungen kannst du doch selber machen 
also ich werde mir das teil mal aus der nähe betrachten. zwar nicht mehr diese woche aber am sa habe ich etwas zeit.
so muss jetzt wieder los. tschau.
|
|
Cashels
Beiträge: 167
|
Verfasst: Di 28.01.03 16:36
Hey,
wie Ugrone bereits angedeutet hat ist der A+ Algorythmus ziemlich performant. Dabei wird von Näherungsmethoden ausgegangen, da das Problem an sich bei wachsender Knotenzahl in keinem zeitlichen Rahmen mehr zu berechnen ist. Ab 50 Knoten wirds schon ziemlich kritisch. Aber in www.derentwickler.de ist der Artikel inkl. Sourcecode zu lesen.
Gruss,
Tom
|
|
Udontknow
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Di 28.01.03 16:56
Hmm? Ich weiss nicht, wo du die Zahl 50 her hast, aber diese Aussage ist definitiv falsch. Ich habe mit einem etwas optimierten Algo Netze von über 20000 Knoten durchsucht, die Weg-Suche lag unter 1 sek.
Cu,
Udontknow
|
|
littlemike1005
Beiträge: 187
|
Verfasst: Di 28.01.03 17:02
Udontknow ich finde dein progi nach wie vor beeindruckend aber ich habe auch meine probleme bei 100 knoten gehabt. ich habe zwei neben einander liegenende als start und ziel genommen da hat mein rechner sich tot gesucht.
aber trotzdem hut ab. das du so schnell ein progi gezaubert hast.
|
|
Cashels
Beiträge: 167
|
Verfasst: Di 28.01.03 17:04
@Udontknow,
die Zahl 50 hab ich aus einem amerikanischem Buch über DNA-Computer. Tut aber nix zur Sache zum Problem... Aber du redest doch auch von optimiertem Code. Dieser Algorythmus würd mich auch interessieren. Denn die meisten Algs arbeiten erst mal mit Näherungsverfahren, um dann eine detaillierte Route zu finden. Der A+ Alg z.B. rechnet nicht rekursiv alle möglichen Wege durch um dann definitiv den günstigsten zu finden, sondern startet die Suche mit einem verdächtigem Kandidaten, z.B. der in Luftlinie der nächste ist. Erst daraufhin wird dann der detaillierte Weg gesucht.
Übrigens ist dieser Alg auch in anderen Probleme anwendbar, z.B. den Ausweg aus einem Labyrinth zu suchen.
Gruss,
Tom
|
|
Udontknow
Beiträge: 2596
Win7
D2006 WIN32, .NET (C#)
|
Verfasst: Di 28.01.03 17:42
@Littlemike: Du musst natürlich die Checkbox "Info" ausknipsen, ansonsten zeichnet er bei jeder Rekursion erst einmal den Pfad neu...
@Cashels: Ich vermute mal, die 50 bezog sich auf die Rekursionstiefe und nicht auf die Anzahl der Knoten...
Was Näherungsverfahren angeht:
Genau so etwas wende ich auch in der optimierten Variante an. Ich sortiere, bevor ich durch die Verbindungen gehe, diese nach Nähe zum Zielknoten (das ein Knoten näher am Zielknoten dran ist, bedeutet eine höhere Wahrscheinlichkeit, über diesen einen Weg zum Zielknoten zu finden):
  Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
| procedure TKnoten.VerbindungenSortierenNachNaeheZu(Knoten: TKnoten);
var i,j:integer;
var Temp:TKnoten;
begin
for i:=0 to AnzahlVerbindungen-2 do
begin
for j:=i to AnzahlVerbindungen-1 do
begin
if Verbindungen[j].DistanzZuKnoten(Knoten)<Verbindungen[i].DistanzZuKnoten(Knoten) then
begin
Temp:=Verbindungen[j];
Verbindungen[j]:=Verbindungen[i];
Verbindungen[i]:=Temp;
end;
end;
end;
end; |
Jaja, BubbleSort ist langsam, ich weiss, aber ich war zu faul, jetzt was anderes zu schreiben.
Mit dieser Optimierung geht die Anzahl der Funktions-Aufrufe in meinem Proggie bei der Einstellung "100 Knoten, RandomSeed 0" auf gerade mal 143 Aufrufe runter, im Gegensatz zu 66234 Aufrufe vorher.
Allerdings ermittelt diese Variante dann noch immer den definitiv kürzesten Pfad.
Cu,
Udontknow
|
|
