Hallo Leute.:-)
Wie schon im Titel erwähnt suche ich eine Software, bei der ich z.B. 15 verschiedene Adressen eingebe, und dann der ökonomischste Weg zwischen diesen Adressen berechnet wird.
Hat jemand ne Idee?
Hallo Leute.:-)
Wie schon im Titel erwähnt suche ich eine Software, bei der ich z.B. 15 verschiedene Adressen eingebe, und dann der ökonomischste Weg zwischen diesen Adressen berechnet wird.
Hat jemand ne Idee?
Verstehe ich deine Frage nicht, oder suchst du einen Routenplaner?
Hm, er sucht nen Routenplaner, dem er z.B. 15 Orte in beliebiger Reihenfolge vorwirft und der dann den kürzesten Weg sucht mit dem man alle 15 Orte abfahren kann. Optimierte Reihenfolge eben.
Map24.de und Google Maps kennen zwar Zwischenstops, optimieren aber nicht die Reihenfolge...
Schätze nils wird jetzt Vertreter.
nein andi, nicht ganz :-)
ich fahre medikamente für ne apotheke aus.
google -> map
aha.. klingt nach einem für bb geigneten beruf.. :-)Zitat:
ich fahre medikamente für ne apotheke aus.
eigentlich bin ich ja student, ist also nur mein nebenjob.
wie soll das denn funktionieren bei google maps?
da kann man doch auch nur einzeln die dressen eingeben und von a nach b nach c usw.
ich möchte alle adressen eingeben und DIE SOFTWARE soll mich dann auf kürzestem wege an allen adressen vorbeiführen.
10/10Zitat:
Zitat von xerof
Ontopic, kann ich nichts beitragen
hab sowas auch mal gesucht als ich zivi gemacht habe. kannst knicken.
zumindest damals. ist aber auch schon 10 jahre her.
Wenn du das Problem löst, bekommst du 1 Million Dollar!
"Not eines Handlungsreisenden"
http://www.sueddeutsche.de/wissen/625/305593/text/
öäahh...Zitat:
Zitat von newbuilder
kotz mich weg
das ding heisst "traveling salesman problem" und lernt jeder informatik-student bereits im vorkurs
ist übrigens mit n! (Fakultät) lösbar und somit existieren für 15 Orte bereits 1307 Milliarden möglicher Lösungen, von denen nur eine optimal ist
btw: das Problem IST LÖSBAR, halt nur nicht effizient, weil jede mögliche Lösung getestes werden muss (ich diskutuiere mit Bodybuilding-Hirnkastraten hier aber keine Komplexitätstheorie aus)
Was du suchst findest du eher unter dem Begriff Tourenplaner (nicht Routenplaner).
Google halt mal... Tourenplaner, Logistik Software, Tourenplanung...
http://www.ptv.de/logistics/software/tourenplanung/
http://www.soloplan.de/wintour.html?&L=
http://www.fls-service.de/ (VisiTour)
:)
An dieser Stelle erst mal mein Beileid...Zitat:
informatik-student
Wow, das Ausrufezeichen heißt Fakultät, wann hatte man das, 8. Klasse Wahrscheinlichkeitsrechnung... :lol: ?Zitat:
ist übrigens mit n! (Fakultät) lösbar
Ah ja, Taschenrechner kannst du also bedienen...Zitat:
und somit existieren für 15 Orte bereits 1307 Milliarden möglicher Lösungen, von denen nur eine optimal ist
Hab ich nie anders behauptet...Zitat:
btw: das Problem IST LÖSBAR, halt nur nicht effizient, weil jede mögliche Lösung getestes werden muss
:)) :lol:Zitat:
(ich diskutuiere mit Bodybuilding-Hirnkastraten hier aber keine Komplexitätstheorie aus)
lineare optimierung/ transportproblem. sowas lernste im grundstudium :langweil:
Zitat:
Zitat von newbuilder
Schade, wäre auch zu schön gewesen :crybaby:
naja, einen vorteil hats ja. ich kenn mich bald besser in meiner heimatstadt aus :-)
map and guide
"wenn du das löst..., dann ...."Zitat:
Zitat von newbuilder
und wenn ich es dir löse? bei 15 orten dauert das nur einige minuten mit brute force.
ach, meine letzte informatik-prüfung hatte zB was mit Approximationsschemen für TSP zu tun :D dafür gibts auch ne lineare Lösung (also 15, und nicht 15!) mit Güte 3/2
Es gibt 1307 Mill. Möglichkeiten die Orte abzufahren.Zitat:
Zitat von Megaman X
Schön, wenn jede Routenberechnung zwischen zwei Punkten als einzelner Rechenschritt gilt brauche ich überschlägig 120 davon und ich hab meine Route. Wo ist das Problem?
dann klär mich mal auf, was du genau geplant hast?
was machst du, wenn auf den ersten blick kürzere routen am ende hin mit unnötigen umwegen verbunden sind?
ausserdem kostet der schritt zwischen zwei orten eben nicht nur Kosten von 1. man muss prinzipiell alle noch verbleibenden Orte durchrechnen. daher sinds für den ersten schritt 15 orte, im 2. schritt 14, im driten 13 usw... also 15*14*13*...*1 = 15! = 1300 Mill
glaub mir, dass problem ist nicht effizienter lösbar, als dass man prinzipiell die schnellste aller lösungswege sucht
wäre das nicht so, dann wäre TSP ein P-Problem, und somit würde NP=P gelten; eine Vermutung, von der Informatiker eher abweichen würden... (und ausserdem könnte ichh dann dein konto knacken)
wichtig ist jedenfalls in deinem fall nicht das finden einen optimalen route, sondern, dass du nicht mehr zeit damit verbringst die optimale route zu finden, als sie dann abzufahren.
daher wuerd ich mich an deinerstelle mit ner heuristik begnuegen.
Startpunkt nehmen, das ist theoretisch Ort Nr. 16, der zählt aber nicht.Zitat:
Zitat von Megaman X
Von da aus die Distanz (Fahrstrecke, nicht Luftlinie! Wegfindungsroutine haben wir ja schon) zu den anderen 15 Orten herausfinden = 15 Schritte.
Kürzeste Distanz wählen, dort neuen Startpunkt setzen und den Ort von der Liste streichen.
Jetzt vom neuen Startpunkt aus die verbliebenen 14 Orte durchgehen und den kürzesten wählen. = 14 Schritte
Bis man alle durch hat braucht man 15+14+13[...]+2+1 Schritte, dazu einen für den Rückweg sind wir bei 121 Stück.
Ohne die Theorie näher zu überprüfen sollte das eventuell nicht die effektivste aber warscheinlich die effizienteste Lösung sein und zumindest einen sehr guten Näherungswert liefern.
sogenannter Greedy(gierig)-Ansatz. Funktioniert manchmal, aber nicht allgemein. Dafür gibts Gegenbeispiele. Die Näherungswerte sind jedoch nicht immer so gut, wie man intuitiv vermuten würde, können bis zur doppelten Länge reichen!Zitat:
Zitat von da_andi
Ahja, wusste nicht das es dafür nen Namen gibt.
Muss ich mir mal näher ansehen, schätze das vor allem dann Mist rauskommt wenn die Orte untereinander annähernd gleich weit entfernt sind.
Naja, für ein Gedankenexperiment wäre das zumindest mein erster Lösungsvorschlag, ohne Machbarkeitsstudioe oder sonst was.
1,3 Billionen Möglichkeiten kann man aber trotzdem nur theroetisch heranziehen, davon ist der großteil totaler Blödsinn.
Nils, vielleicht findest Du ja hier das richtige:
http://www.navi-magazin.de/index.html
wie ich schon gepostet habe: Map&Guide, ist nur dafür entwickelt worden :kult:Zitat:
Zitat von Legomeister
Hab eben mal dieses map & guide ausprobiert. das ist fast wie ein normaler routenplaner. man muss schon selber festlegen in welcher reihenfolge man die orte abfährt.
nö, gibts ne Funktion wo Du nach Zeit oder Strecke optimieren lassen kannst!