Anmerkungen und Erläuterungen


 

 

Im Artikel:  Grötschel M, Padberg M „Die optimierte Odyssee“ in: Spektrum der Wissenschaft 4/99, S.80 ff. heißt es dazu: 

...........
Stellen wir uns einen Topmanager oder - prosaischer - Handelsvertreter (travelling salesman) vor. Er will alle 16 Städte in beliebiger Reihenfolge besuchen, und zwar auf dem kürzestmöglichen Wege - Zeit ist Geld. Das ist das berühmte Traveling Salesman Problem (TSP): schnell formuliert, höchst praxisrelevant, scheinbar harmlos, in Wirklichkeit aber - für große Städteanzahlen - so schwer, daß die Mathematiker sich auch nach Jahrzehnten harter Arbeit die Zähne daran ausbeißen. ....................

.... Diese Enumeration ist der klassische Ansatz zur Lösung von kombinatorischen Optimierungsproblemen, das heißt solchen mit endlich vielen Auswahlmöglichkeiten. Es steckt nichts dahinter als die gedankenlose Anwendung roher Gewalt; aber diese Methode lebt immer noch in einigen (etwas angestaubten) Köpfen fort. Nur scheitert sie bereits an Problemen, die geringfügig größer sind als die Reiseplanung des Odysseus. Wir haben dieses Beispiel unter anderem deswegen gewählt, weil es mit heutzutage vorhandenen Computern gerade noch mittels Enumeration lösbar ist. Bereits 25 Städte würden die größten Supercomputer mit den ausgefeiltesten Enumerationstechniken hoffnungslos überfordern. (Hervorhebung durch den Autor) ......

Den ganzen Artikel finden Sie hier im Internet.  

 

Eine weitere Aussage über die Unmöglichkeit einer kombinatorischen Lösung 
für k = 25 Orte finden Sie hier: .http://www.jgiesen.de/Divers/TSM/TSM.html