Travelling Salesman - Nur Länge der optimalen Rundreise berechnen?
-
Ok, hab mal weiter gesucht, aber nichts sinnvolles gefunden, anscheinend gibt es Rundreisen, bei denen die kürzeste Route nachgewiesen ist (per Großrechner und Branch & Bound) weiß zufällig jemand, wo es solche Strecken mit relativ wenig Städten gibt (20-50)?
-
naja, du kannst ne untere schranke angeben (z.b. bei kürzeste weg problem, kannste auch sagen, dass der gefundene weg von A nach B nicht kürzer als der luftlinienabstand sein kann ;)) und bei manchen algorithmen haste eben auch eine obere schranke und aus obere und untere schranke (optimaler weg) berechenste dann die max abweichung vom optimalen weg..
-
kleine Zwischenfrage:
was ist "Travelling Salesman"?
-
TheToast schrieb:
Ok, hab mal weiter gesucht, aber nichts sinnvolles gefunden, anscheinend gibt es Rundreisen, bei denen die kürzeste Route nachgewiesen ist (per Großrechner und Branch & Bound) weiß zufällig jemand, wo es solche Strecken mit relativ wenig Städten gibt (20-50)?
50? da gibt es doch n! möglichkeiten. ein rechner der das bewältigt wäre echt geil
aber das wäre doch mal ein schöner WPC
rapso->greets();
-
rapso schrieb:
50? da gibt es doch n! möglichkeiten. ein rechner der das bewältigt wäre echt geil
Deswegen wunderts mich auch und deswegen frag ich ja...
-
Frage siehe oben... Bitte um Antwort, dass ich armer kleiner Bub auch bei den Großen mitreden kann!
-
MasterCounter schrieb:
Frage siehe oben... Bitte um Antwort, dass ich armer kleiner Bub auch bei den Großen mitreden kann!
das ist das stichwort für deine nächste google-session
ein handelsreisender will verschiedene orte besuchen (zum handeln halt) und am schluß wieder zuhause ankommen. das "problem" besteht darin, den kürzesten weg zu finden.
-
MasterCounter schrieb:
Frage siehe oben... Bitte um Antwort, dass ich armer kleiner Bub auch bei den Großen mitreden kann!
na ich hoffe noch, dass dir niemand die arbeit abnimmt um den link suchen zu lassen, sodass du entweder selbst ein neues browserfenster öffnest und dort diese zwei wörter in die googleleiste pastest, oder du weiter auf dem schlauch stehst und dich kurz vor deinem ableben dafür hasst, dass du nie nachgesehen hast was es heißt und nun unwissend von dannen gehst
on topic:
also bis 18knoten dürfte das optimum noch durch brute force rauszufinden sein.rapso->greets();
-
TheToast schrieb:
Ok, hab mal weiter gesucht, aber nichts sinnvolles gefunden, anscheinend gibt es Rundreisen, bei denen die kürzeste Route nachgewiesen ist (per Großrechner und Branch & Bound) weiß zufällig jemand, wo es solche Strecken mit relativ wenig Städten gibt (20-50)?
http://encyclopedia.lockergnome.com/s/b/Traveling_salesman_problem#Exact_algorithms schrieb:
An exact solution for 15,112 German cities from TSPLIB was found in 2001 using the cutting-plane method proposed by George Dantzig, Ray Fulkerson, and Selmer Johnson in 1954, based on linear programming. The computations were performed on a network of 110 processors located at Rice University and Princeton University, see the Princeton external link. The total computation time was equivalent to 22.6 years on a single 500 MHz Alpha processor. In May 2004, the traveling salesman problem of visiting all 24,978 cities in Sweden was solved: a tour of length approximately 72,500 kilometers was found and it was proven that no shorter tour exists.
-
und nach was sucht ihr jetzt?
ach ja, hab nach 5sec (
) googeln das gefunden:
http://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/java/TSP/
-
Wenn man effizient die Länge der kürzesten Rundreise berechnen kann, so geht das auch mit der Rundreise selbst.