6/2018 Weg eines Handlungsreisenden
Das „Problem des Handlungsreisenden“ ist eine mathematische Aufgabe, ein so genanntes kombinatorisches Optimierungsproblem, das erstmals in den 1930er Jahren von dem österreichischen Mathematiker Karl Menger formuliert wurde, obwohl es als Problem schon länger bekannt war. Dabei geht es darum, auf einer Landkarte den kürzesten Verbindungsweg zwischen mehreren Städten bzw. Reisezielen zu finden. Es ist relativ leicht, dafür (auch als Mensch, nicht nur als Computer) eine gute Lösung zu finden, aber es ist sehr schwierig, die optimale Lösung zu finden. Für die Lösung gibt es etliche exakte und heuristische Methoden – letzteres bedeutet, dass mit beschränkten Mitteln und begrenzter Zeit eine möglichst gute, praktikable Lösung gesucht wird, die aber in den meisten Fällen nicht das Optimum sein wird, sondern nur nahe daran. Der Software-Entwickler Todd W. Schneider hat für eine solche heuristische Lösung des Handlungsreisenden-Problems eine interaktive Online-Applikation produziert, die der Methode der „simulierten Abkühlung“ folgt. Man beginnt dabei den Lösungsweg damit, irgendeinen Weg festzulegen und dann dessen unmittelbare „Nachbarn“, also nur wenig unterschiedliche Wege, zu vergleichen: Sind sie besser oder schlechter? Dadurch kann man allerdings in ein so genanntes „lokales Minimum“ gelangen, das heißt sobald ein schlechterer Nachbar erreicht wird, sucht man in diese Richtung nicht weiter, obwohl dort nach Überwindung eines kleinen „Hügels“ vielleicht noch bessere Wege zu finden wären. Deshalb die „Abkühlung“: Man nimmt zu Beginn eine hohe Temperatur (wie bei der Abkühlung von Metall) an und das Verfahren akzeptiert, solange die Temperatur noch hoch ist, auch schlechtere Nachbarwege. Mit jedem Schritt sinkt die Temperatur ein wenig, sodass nach einiger Zeit kaum mehr schlechtere Nachbarn angenommen werden und so schließlich zumindest ein lokales Minimum, vielleicht aber sogar das globale Minimum erreicht wird. Die Anwendung funktioniert entweder für die ganze Welt oder die USA. Man wählt eine Reihe von Städten aus, kann ein paar Parameter der Heuristik regeln und dann startet die Berechnung: Voreingestellt werden 25.000 Rechenschritte gemacht, dann sollte eine ziemlich gute Reiseroute vorliegen. Vielleicht für den Sommerurlaub verwendbar?