DIE VERBORGENE ZAHL DES HANDLUNGSREISENDEN, IN DIE ENGE GETRIEBEN

KI-Nutzung erklärt. In einer „Erklärung zur KI-Nutzung“ geben die Autoren an, dass sie das KI-Werkzeug GPT-5.6 Sol Pro bei der Vorbereitung der Arbeit genutzt, alle Ergebnisse überprüft und verifiziert haben und die volle Verantwortung für den Inhalt übernehmen. Ihr Code ist auf Anfrage erhältlich.

Das Problem des Handlungsreisenden fragt nach der kürzesten Rundreise, die jeden Punkt einer Menge einmal besucht und zum Start zurückkehrt. Nun mache man die Punkte zufällig: Man werfe n Punkte gleichmäßig in ein Quadrat der Seitenlänge 1 und frage, wie lang die kürzeste Rundreise ist.

1959 bewiesen Beardwood, Halton und Hammersley eine verblüffende Antwort. Wächst n, wird die Länge der besten Rundreise fast sicher gleich β√n, wobei β eine universelle Konstante ist – dieselbe für jede zufällige Verteilung. Sie zeigten außerdem, dass 0,625 ≤ β ≤ 0,9212.

Mehr als fünfundsechzig Jahre später kennt niemand β. Es gibt keine Formel. Große Computerexperimente beziffern es auf etwa 0,7124, doch ein Experiment ist kein Beweis. Bisher waren die besten bewiesenen Schranken 0,6277 ≤ β ≤ 0,90367. Solche Konstanten sind in der Logistik wichtig, wo man mit ihnen die Länge von Lieferrouten abschätzt, ohne sie zu berechnen – deshalb stammt das neue Ergebnis von der McCombs School of Business der University of Texas at Austin, von Zhuolun Dong und Junyu Cao.

Die neue Klammer

Die Arbeit beweist:

0,6421 ≤ β ≤ 0,8810

und zeigt mithilfe von Zufallsstichproben, dass 0,6536 ≤ β ≤ 0,8749 mit einer Wahrscheinlichkeit von mindestens 1 − 2 × 10⁻⁴ gilt. Diese Wahrscheinlichkeit betrifft den Zufall der Computerstichprobe, nicht β selbst, das eine feste Zahl ist.

Von unten: die langen Kanten kappen

Um zu beweisen, dass jede Rundreise lang sein muss, betrachten die Autoren, was passiert, wenn man alle Kanten einer Rundreise löscht, die länger als eine bestimmte Länge r sind. Die Rundreise zerfällt in Wegstücke, und jedes Stück bleibt innerhalb eines Clusters von Punkten, die weniger als r voneinander entfernt sind. Je mehr Wege nötig sind, um einen Cluster abzudecken, desto mehr lange Kanten muss die Rundreise gehabt haben. Summiert man das über alle möglichen r, erhält man die Länge der Rundreise:

ℓ(H) = ∫₀^∞ N_H(r) dr,

wobei N_H(r) die Kanten zählt, die länger als r sind.

Isolierte Punkte und Wegenden liefern den alten Term 5/8 = 0,625 – genau die Schranke von 1959. Die neue Zutat ist eine Reihe von Korrekturen aus kleinen Clustern von 3, 4 und 5 Punkten, jede ein Integral über die möglichen Lagen der Punkte. Diese Integrale lassen sich nicht exakt berechnen, also zerlegen die Autoren ihre Definitionsbereiche in winzige Würfel und schätzen jeden Würfel nach unten ab, wobei jede irrationale Zahl in die ungünstige Richtung gerundet wird, damit das Ergebnis eine echte Schranke ist:

β ≥ 0,625 + 0,01113528859 + 0,005040573276 + 0,001015487669 > 0,6421.

Von oben: Zickzack in Fünferblöcken

Eine obere Schranke braucht nur eine gute Rundreise. Das klassische Rezept zerschneidet das Quadrat in waagerechte Streifen und durchläuft sie im Zickzack, von links nach rechts, dann von rechts nach links. Die neue Wendung: Innerhalb jedes Streifens werden die Punkte in Fünferblöcken genommen, und jeder Block wird in der besten seiner 24 möglichen Reihenfolgen besucht.

Die erwartete Länge eines Blocks ist ein elfdimensionales Integral – fünf waagerechte Abstände zwischen Punkten und sechs Höhen. Die Autoren schätzen es numerisch auf einem feinen Gitter ab, wieder mit rationalen Zahlen, die in die sichere Richtung gerundet werden, und erhalten β < 0,8810.

Die verbleibende Lücke

Die Klammer ist von einer Breite von etwa 0,28 auf etwa 0,24 geschrumpft, doch der empirische Wert 0,7124 liegt noch immer weit darin. Feinere Gitter, schärfere Abschätzungen sich überlappender Kreisflächen und längere Blöcke könnten sie weiter verengen. Die restliche Distanz zu schließen, schreiben die Autoren, „könnte neue Techniken erfordern“.