Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Informatik: Die optimale Reise

Ein Händler möchte auf einer möglichst kurzen Route mehrere Städte besuchen und anschließend wieder heimkehren – das berühmte »Problem des Handlungsreisenden«. Nach 44 Jahren gibt es erstmals einen Fortschritt dazu.
Fahrrad mit viel Gepäck auf einer Schotterstraße in Tadschikistan

Als Nathan Klein 2018 zu promovieren begann, schlugen ihm seine Betreuer ein ambitioniertes Projekt vor: die Mitarbeit an einem der bekanntesten Probleme der theoretischen Informatik. Selbst wenn sie es nicht lösen sollten, würde der Student viel dabei lernen. Daher schloss er sich der Idee spontan an. »Mir war nicht ganz klar, welche Tragweite das hatte«, gibt er zu. »Ich war schließlich in meinem ersten Promotionsjahr – ich hatte keine Ahnung.«

Im Juli 2020 hat Klein schließlich gemeinsam mit seinen Betreuern Anna Karlin und Shayan Oveis Gharan von der University of Washington ein Ergebnis veröffentlicht, dem Computerwissenschaftler seit fast einem halben Jahrhundert nachjagen: Sie haben einen Algorithmus entwickelt, der bessere Lösungen für das so genannte Problem des Handlungsreisenden findet.

Ziel ist es hierbei, den kürzesten Rundweg zwischen einer vorge­gebenen Menge an Städten – oder allgemein Orten – zu bestimmen. Die Aufgabe hat Anwendungen, die von der DNA-Sequenzierung bis zur Logistik einer Mitfahrzentrale reichen. Im Lauf der Jahrzehnte hat das Problem zu etlichen grundlegenden Fortschritten in der Informatik geführt und dazu beigetragen, bekannte Techniken wie die lineare Programmierung zu beleuchten. Dennoch haben Wissenschaftler das gesamte Potenzial der Optimierungsaufgabe noch lang nicht ausgeschöpft – was nicht daran liegt, dass sie es nicht eingehend untersucht hätten.

Ob überhaupt ein Algorithmus existiert, der das Problem des Handlungsreisenden in annehmbarer Zeit exakt löst, ist unklar …

Kennen Sie schon …

Spektrum der Wissenschaft – Formen der Mathematik

Die Mathematik ist ein erstaunlich vielfältiges Fach und zeigt sich in den verschiedensten Formen: Lesen Sie von den bunten Fraktalen der Mandelbrotmenge, einer Einstein-Kachel, die den Boden mit erstaunlichen, lückenlosen Mustern versieht oder den Falten eines zerknitterten Papiers. Diese unterschiedlichen Strukturen bergen spannende mathematische Eigenschaften, die Fachleute in den letzten Jahren entdeckt und zum Staunen gebracht haben. Darüber hinaus stellen wir die Frage, warum Kieselsteine oval sind und zeigen Ihnen, nach welchen Regeln die faszinierenden Sandzeichnungen auf dem südpazifischen Archipel Vanuatu entstehen.

Spektrum - Die Woche – Akustische Kur gegen Stress

Naturgeräusche haben eine unglaublich beruhigende Wirkung auf uns. Wieso das so ist und wie Vogelgezwitscher und Wasserrauschen im Gehirn verarbeitet werden und auf unsere Psyche wirken, lesen Sie in der aktuellen Ausgabe der »Woche«. Außerdem: Läutet das KI-Zeitalter eine neue Ära der Physik ein?

Spektrum - Die Woche – Wie die Guinness-Brauerei den t-Test erfand

Wer hätte gedacht, dass eine Brauerei der Geburtsort für eine der wichtigsten mathematischen Methoden ist? Dem Guiness-Bier haben wir zu verdanken, dass Ergebnisse in der Wissenschaft als statistisch signifikant gewertet werden können. Außerdem in dieser »Woche«: Wie Rauchen das Immunsystem stört.

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.