2020/03 - Das Problem des Handlungsreisenden
Schurli ist zwar kein Handlungsreisender (es sei denn, man betrachtet die Reise als Handlung). Unter dieser Bezeichnung verbirgt sich jedoch ein veritables Problem, das sogar Mathematiker alt aussehen läßt.
Klar gibt es Computerprogramme, die alle Möglichkeiten der Routenführung durchrechnen und dann die kürzeste Variante ausgeben können. Bei mehreren Städten muss der Computer dabei aber schnell genug sein, um vor Reiseantritt fertig zu werden, auch wenn die Reise erst zB in einem Monat beginnt!
Bei 15 Städten, wie Schurlis Reise beinhaltete, gibt es bereits 1.307.674.368.000 Möglichkeiten. In diesem Fall müßte der Computer ca. 500.000 Varianten pro Sekunde durchrechnen, um in 1 Monat fertig zu werden. Nur 2 Städte mehr, und derselbe PC würde statt 1 Monat über 22 Jahre brauchen!
Mittlerweile (seit 1930) haben viele Mathematiker versucht, eine schnellere Berechnungsweise zu finden. Allen Lösungen ist gemeinsam, dass sie nicht beweisbar sind. Im Jahr 2000 hat das Clay Mathematics Institute für eine echte Lösung 1 Million Dollar ausgelobt, die mangels Lösung bis heute noch nicht abgeholt wurden.
Die beste Lösung aus Schurlis Problem habe ich inzwischen bei einem mir bekannten Mathematiker nachrechnen lassen, und es ist mit an Sicherheit grenzender Wahrscheinlichkeit wirklich die beste Lösung.
In dieser Sache ist es allgemein anerkannt, dass die Menschen durch "Probieren" der geballten Rechenpower von Computern durchaus ebenbürtig sind!
Liebe Grüße,
Euer Rätselonkel Peter