"Problem des Handlungsreisenden"
Moderators: Miles66, Licht & Feuer
- haemoglobin
- Euro-Master
- Posts: 1414
- Joined: Sat Apr 12, 2003 11:26 pm
- Location: Oldenburg, Germany
- Contact:
"Problem des Handlungsreisenden"
an unsere Mathematik- und Informatiknerds....
Ich sitze grad mal wieder über Google Earth und trage noch zu trackende Locations ein. Bei der Menge der Locations ist eine vernünftige Tourplanung mehr als angebracht.
Da gibt es doch das schöne Problem des Handlungsreisenden
Gibt es vielleicht irgendwo in den Weiten des Netzes eine versteckte Seite oder spezielle Routenplaner die dieses Problem angehen?
man könnte sich dann so manchen km sparen...
Ich sitze grad mal wieder über Google Earth und trage noch zu trackende Locations ein. Bei der Menge der Locations ist eine vernünftige Tourplanung mehr als angebracht.
Da gibt es doch das schöne Problem des Handlungsreisenden
Gibt es vielleicht irgendwo in den Weiten des Netzes eine versteckte Seite oder spezielle Routenplaner die dieses Problem angehen?
man könnte sich dann so manchen km sparen...
- helloggs
- Euro-Master
- Posts: 1340
- Joined: Sat Oct 02, 2004 1:17 pm
- Location: Berlin, Germany
- Contact:
Re: "Problem des Handlungsreisenden"
Also wirds fuer deine Touren bestimmt 35 Jahre dauern.Wikipedia wrote:Komplexitätstheoretisch gehört das TSP zur Klasse der NP-äquivalenten Probleme. Es wird daher sehr stark angenommen, dass die Worst-case-Laufzeit jedes deterministischen Algorithmus, der für dieses Problem stets optimale Lösungen liefert, im besten Fall exponentiell von der Anzahl der Städte abhängt. Schon für wenige Städte kann die benötigte Laufzeit eines solchen Algorithmus also unpraktikabel viel Zeit beanspruchen.
- taucher
- Euro-Master
- Posts: 1572
- Joined: Thu Jun 30, 2005 10:57 pm
- Location: Frankfurt am Main, Germany
Re: "Problem des Handlungsreisenden"
Und wenn Jenni noch die Schuhgeschäfte mitnimmt, bestimmt 45 Jahrehelloggs wrote:Also wirds fuer deine Touren bestimmt 35 Jahre dauern.
infinity is a great place to start
10.08.2010 | 360° Frankfurt
we're one, but we're not the same
10.08.2010 | 360° Frankfurt
we're one, but we're not the same
-
- Euro-Master in Training
- Posts: 766
- Joined: Sun May 20, 2007 4:04 pm
- Location: Hannover, Germany
Re: "Problem des Handlungsreisenden"
Versuchs mal damit (ich habe es nicht getestet, aber anscheinend gibts den Quellcode auf der Seite und das Programm).
http://www.lalena.com/AI/Tsp/
So nebenbei würde ich mal auf 42 Jahre tippen
http://www.lalena.com/AI/Tsp/
So nebenbei würde ich mal auf 42 Jahre tippen
One Currency, one Union, one Eurobilltracker...
My dots are of the same order as 10.
My dots are of the same order as 10.
- androl
- Euro-Master
- Posts: 4318
- Joined: Sun Feb 08, 2004 1:20 pm
- Location: München (Myeenack, Mjuncken), Deutschland (Chairmany, Djutschländ)
- Contact:
Re: "Problem des Handlungsreisenden"
du hast das mit der exponentiellen Zeit nicht verstanden.taucher wrote:Und wenn Jenni noch die Schuhgeschäfte mitnimmt, bestimmt 45 Jahrehelloggs wrote:Also wirds fuer deine Touren bestimmt 35 Jahre dauern.
Wenn Jenny ein Schuhgeschäft mitnummt, braucht das Programm 100 Jahre. Bei zwei Schuhgeschäften 300 Jahre. Bei drei Stück 1000 Jahre.
Schuhgeschäfte gibt es aber noch viel mehr
Hämo: Ich glaube, gehört zu haben, dass es einen polynomiellen Algorithmus gibt, der das Problem mit einer bestimmten Fehlerschwelle löst, also der einen Weg findet, wo es keinen anderen Weg gibt, der mehr als 20 Prozent kürzer ist. Reicht dir das?
Joshu, a Chinese Zen master, asked a cow:
"Do you have Buddha-nature or not?"
The cow answered: "Moo."
"Do you have Buddha-nature or not?"
The cow answered: "Moo."
Re: "Problem des Handlungsreisenden"
hab da mal google gewälzt und was gefunden, klein, relativ schnell (im vergleich zu den oben genannten zeitspannen 0o) und auf basis von googlemaps
http://gebweb.net/optimap/
ich habs ausprobiert.. bei ca 30 locations geschätze 30-60 sekunden ladezeit
http://gebweb.net/optimap/
ich habs ausprobiert.. bei ca 30 locations geschätze 30-60 sekunden ladezeit
Re: "Problem des Handlungsreisenden"
Toll DkL, danke für den link..
Große Klasse, das geht ja auch für Fußgänger/Radfahrer
Habe das gerade auch ausprobiert und festgestellt, dass meine 15 Lieblingsbanken hier in Berlin schon in 5:15 h zu Fuß oder die 24 km mit dem Fahrrad in 2-3 Stunden zu erreichen wären. Statt in 2-5 Tagen wie jetzt.
Dass das in der Praxis natürlich bedeutend mehr Zeit beanspruchen wird ist schon klar aber nett ist das Teil auf jeden Fall.
Wir können also auch als nicht Bahn/Autofahrer uns schöne Rundgänge errechnen lassen.
Ob es nun unserem Haemo hilft weiß ich nicht, aber mir und anderen wird es gefallen.
Danke und freundliche Grüße
Volker
Große Klasse, das geht ja auch für Fußgänger/Radfahrer
Habe das gerade auch ausprobiert und festgestellt, dass meine 15 Lieblingsbanken hier in Berlin schon in 5:15 h zu Fuß oder die 24 km mit dem Fahrrad in 2-3 Stunden zu erreichen wären. Statt in 2-5 Tagen wie jetzt.
Dass das in der Praxis natürlich bedeutend mehr Zeit beanspruchen wird ist schon klar aber nett ist das Teil auf jeden Fall.
Wir können also auch als nicht Bahn/Autofahrer uns schöne Rundgänge errechnen lassen.
Ob es nun unserem Haemo hilft weiß ich nicht, aber mir und anderen wird es gefallen.
Danke und freundliche Grüße
Volker
- haemoglobin
- Euro-Master
- Posts: 1414
- Joined: Sat Apr 12, 2003 11:26 pm
- Location: Oldenburg, Germany
- Contact:
Re: "Problem des Handlungsreisenden"
DAS ist genau das wonach ich gesucht habe
mal schauen wie es sich in der praxis bewährt
leider bleibt dann auch mehr zeit für schuhgeschäfte
mal schauen wie es sich in der praxis bewährt
leider bleibt dann auch mehr zeit für schuhgeschäfte
Re: "Problem des Handlungsreisenden"
Ganz netter Link!
Aber ich finde: Eine EBT Tour ohne eigener Planung ist nur der halbe Spaß! Gerade das lange Brüten über der Karte lässt die Vorfreude und Neugierde auf bisher unbekanntes Land so richtig wachsen.
Aber ich finde: Eine EBT Tour ohne eigener Planung ist nur der halbe Spaß! Gerade das lange Brüten über der Karte lässt die Vorfreude und Neugierde auf bisher unbekanntes Land so richtig wachsen.
Tombola & Hias: Klasse statt Masse!
86/98 Bezirke of Austria
681/2358 "Gemeinden” of Austria
85/443 Kreise of Germany
114/114 Dots in Austria
314 Eu Dots
15 W Dots
86/98 Bezirke of Austria
681/2358 "Gemeinden” of Austria
85/443 Kreise of Germany
114/114 Dots in Austria
314 Eu Dots
15 W Dots
- haemoglobin
- Euro-Master
- Posts: 1414
- Joined: Sat Apr 12, 2003 11:26 pm
- Location: Oldenburg, Germany
- Contact:
Re: "Problem des Handlungsreisenden"
hab das tsp-tool mal an unseren partner für den probentransport in unserem labor weitergeleitet. vielleicht kann der ja die touren dadurch etwas optimieren und ich hab früher feierabend..
btw: es werden leider "nur" 24 locations berechnet, aber trotzdem immer noch super
btw: es werden leider "nur" 24 locations berechnet, aber trotzdem immer noch super
-
- Euro-Regular in Training
- Posts: 80
- Joined: Tue May 30, 2006 9:58 am
Re: "Problem des Handlungsreisenden"
Auch wenn das Thema schon älter ist, hier mal zwei Kommentare:haemoglobin wrote:Gibt es vielleicht irgendwo in den Weiten des Netzes eine versteckte Seite oder spezielle Routenplaner die dieses Problem angehen?
1. Mein Navigationssystem (Garmin, Typ "ich saug mich an der Scheibe fest") hat einen Menüpunkt für Routen. Man kann grundsätzlich alle Ziele eingeben und das Navi dann arbeiten lassen.
2. Ich halte trotz allem nicht viel von vollautomatischer Planung, da so ein vollautomatisches Programm meist Probleme mit "Sonderbedingungen" hat. Beispiel: Ich nehme demnächst an einer Veranstaltung teil und reise mit dem PKW an. Ich möchte bei der Gelegenheit "Mühlenweg 10,39517 Lüderitz" besuchen, nur ist zu beachten, dass der Geldautomat der Sparkasse in der Nacht geschlossen hat (Geld gibt's dort nur von 05:00 bis 23:00 Uhr). Also muss ich mir überlegen, ob ich später los fahre und ggf. etwas später bei der Veranstaltung erscheine oder ob ich den Ort nicht in der kilometermäßig angesagten Reihenfolge anfahre oder ob ich noch was anderes mache (denkbar wäre es auch die STAR-Tankstelle in Dolle anzufahren, die hat laut I-Net immer offen). -> Da hilft nur "manuelle" Planung.
Gruß Kurzschluss
- lmviterbo
- Euro-Master
- Posts: 6529
- Joined: Thu Aug 21, 2003 5:23 pm
- Location: Lisboa, Portugal
- Contact:
Re: "Problem des Handlungsreisenden"
https://www.routexl.nl/?lang=de
"RouteXL ist ein Routenplaner mit mehreren Zielorten. Auf einfache Weise finden Sie hier die schnellste Route entlang mehrerer Zwischenstationen. RouteXL bringt die Zieladressen in optimierter Reihenfolge. Für bis zu 20 Adressen können Sie RouteXL gratis benutzen. Möchten Sie bis zu 100 Adressen abrufen dan bieten wir Sie um einen kleine Beitrag."
"RouteXL ist ein Routenplaner mit mehreren Zielorten. Auf einfache Weise finden Sie hier die schnellste Route entlang mehrerer Zwischenstationen. RouteXL bringt die Zieladressen in optimierter Reihenfolge. Für bis zu 20 Adressen können Sie RouteXL gratis benutzen. Möchten Sie bis zu 100 Adressen abrufen dan bieten wir Sie um einen kleine Beitrag."