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 TadschikistanLaden...

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 …

07/2021

Spektrum - Die Woche – 07/2021

Warum brechen Kinder den Kontakt zu ihren Eltern ab? Und wie können diese damit umgehen? Darüber lesen Sie mehr in dieser Ausgabe. Außerdem: Hilberts 13. Problem und ein erfolgreicher falscher Entdecker.

06/2021

Spektrum - Die Woche – 06/2021

Rapsöl ist das beliebteste Öl der Deutschen. Nachvollziehbar – denn es ist günstig, massentauglich und gesund, wie Sie in dieser Ausgabe lesen können. Außerdem erfahren Sie mehr über einen Mathematiker aus Silizium sowie einen gefräßigen Weißen Zwerg.

Highlights 1/2021

Spektrum der Wissenschaft – Highlights 1/2021: Mathematische Spiele und Strategien

Ziegenproblem: Ist hinter der nächsten Tür eine Ziege oder das Auto? • Gefangenendilemma: Kooperieren, betrügen oder ganz aussteigen? • Strategien der besten Wahl: Wie lange soll die Prinzessin auf den Traumprinzen warten?

Lesermeinung

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, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften 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 Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!