Optimale Route

Hallo,
ist es möglich mit Navigon eine optimale Route zu berechnen. Ich möchte beispielsweise 5 verschiedene Ziele anfahren, Reihenfolge ist egal. Nun soll er mir die kürzeste Route berechnen, wobei alle Ziele auf der Route enthalten sein sollen.
Danke

Hi snapple!

Was du da machen möchtest nennt sich in der Informatik Traveling-Sales-Man Problem (Siehe auch http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden). Und es gehört zu den härtesten Nüssen, die es so an mathematischen Problemen gibt, den sogenannten NP-vollständigen Problemen.

Das Problem ist, dass mit jeder zusätzlichen Stadt die Anzahl der Möglichkeiten explodiert. Bei einem Punkt A muss man nur eine Strecke berechnen (Start S=>A). Bei zwei sind es drei (S=>A, S=>B, A=>B); bei drei sind es schon sechs (S=>A, S=>B, S=>C, A=>B, A=>C, B=>C). Ab dann fängt es an fix mehr zu werden. Bei vier Punkten sind es dann 10 (S=>A, S=>B, S=>C, S=>D, A=>B, A=>C, A=>D, B=>C, B=>D, C=>D). Dabei haben wir noch nicht betrachtet, dass es ja auch Einbahnstraßen gibt, so dass der Weg A=>B anders aussehen kann als B=>A.

Aber damit ist es ja noch nicht getan man muss dann ja auch noch alle möglichen Kombinationen der Punkte-Reihenfolge ausprobieren, die es gibt, um die kürzeste rauszufinden. Bei einem Punkt ist es noch einfach, da fahre ich einfach nach A: S=>A (Anzahl = 1). Bei zwei Punkten muss ich wissen was kürzer ist: erst A dann B oder umgekehrt: S=>AB oder S=>BA (Anzahl = 1 * 2 = 2). Bei drei sind es mit S=>ABC, S=>ACB, S=>BAC, S=>BCA, S=>CAB und S=>CBA schon sechs Strecken (Anzahl = 1 * 2 * 3 = 6). Für vier Ziele sind das S=>ABCD, S=>ABDC, S=>ACBD, S=>ACDB, S=>ADBC, S=>ADCB, ... also 24 Stück (Anzahl = 1 * 2 * 3 * 4 = 24). Und das werden noch viel schneller mehr als die Einzelstrecken (Fakultatives Wachstum). Bei deinen fünf Punkten sind es schon 120 Möglichkeiten.

Naja, bei fünf Zielen könnte das Navi dann wahrscheinlich nach etlichen Minuten die kürzeste Strecke haben. Aber packst du nur zwei Ziele drauf braucht es bestimmt schon über ne Stunde (Anzahl = 120 * 6 * 7 = 5040).

Was ich sagen will, Ich glaube nicht, dass in absehbarer Zeit ein Navi auf den Markt kommt, das eine solche Funktion für etliche Ziele bietet.

So, ich hoffe, ich habe das verständlich erklärt und es klang nicht zu sehr nach Kluscheißer,
Lafranconi

Danke für die ausführlichen Antworten. Jetzt weiss ich zumindest warum das auf dem PNA zur Zeit noch nicht möglich ist.
Gruß

Medion scheint's aber geschafft zu haben oder versteh ich das hier falsch?

Könnte man so verstehen. Aber Medion hat die Anzahl der Zwischenziele auf fünf begrenzt (vielleicht deshalb, wie oben zu sehen ist wirds spätestens bei 7 echt haarig). Fakt ist, das Traveling Sales Man Problem ist nicht gelöst. Wer das schafft kommt zu Weltrum (ohne Untertreibung) und macht damit der Weltelite der theoretischen Informatiker ne lange Nase.

Was es gibt, sind Verfahren, die zu sehr guten Lösungen kommen. Die liefern einen sehr kurzen Weg, aber ob das dann auch tatsächlich der kürzeste Weg ist können sie nicht garantieren.

Könnte aber auch heißen, dass sie die Zwischenziele nach dem Abstand zum Startpunkt sortieren. Das ist ja dann ne leichte Übung.

Ich weiß nicht, wie es gemeint ist. Vielleicht kann uns da ja mal ein mitlesender Medion Besitzer erhellen. Wäre dann auch interessant wie lange die Kiste dann braucht, um die optimale Route bei fünf Zwischenzielen zu berechnen.

Nacht!

Zitat

Original von Farmer John
Medion scheint's aber geschafft zu haben oder versteh ich das hier falsch?

Auch Destinator und andere hatten schon ähnliche Ansätze. Hierbei werden nur die Zwischenziele (Start- und Endpunkt liegen fest) nach ihrer Entfernung zum Start geordnet. Das funktioniert auf langen Strecken, wenn zwischen Hamburg und München einige Städte eingegeben werden.
Kleinräumig geht das System in die Hose. Falls ein größeres Gewässer oder Höhenzug ohne nahe Querung dazwischenliegen, kommen absurde Routings zustande.

Gruß
bonnie

Zitat

Original von bonnie
Das funktioniert auf langen Strecken, wenn zwischen Hamburg und München einige Städte eingegeben werden.
Kleinräumig geht das System in die Hose.
Gruß
bonnie

Gerade kleinräumig fände ich es interessant. Beispiel: Ich wohne in Hamburg ( tue ich nicht, nur ein Beispiel ) und will an 5 verschiedene Adressen und wieder nach Hause, und das auf dem kürzesten Weg. Da wird selbst ein Hamburger Taxifahrer einige Zeit nachdenken müssen, wie er da am besten fährt.

Zitat

Original von Dr.No
Gerade kleinräumig fände ich es interessant.

Eben.
Und genau da funktioniert es nicht richtig.

Gruß
bonnie