Rundreise als Problem

image_pdfimage_print

TSP_Deutschland_3Die meisten Leute buchen Rundreisen beim Reiseveranstalter und überlassen dem die Sorge um die Streckenführung. Daran tun sie gut, denn es ist schwer, optimale Rundkurse zu finden. Das Fachgebiet Operations Research (OR) vereinigt Angewandte Mathematik, Wirtschaftswissenschaften und Informatik, um mathematische Methoden für das Rundreiseproblem zu liefern.

Ein Beispiel: Finde die kürzeste Rundreise durch die 15 größten deutschen Städte. Prinzipiell sind dann 15! (15 Fakultät) Routen zu untersuchen. Für den ersten Stop gibt es 15 Möglichkeiten, für den 2. 14, für den 3. 13 usw. Weil es für die Routenlänge egal ist, wo man anfängt, teilt man durch 15, und weil rechtsrum genausolang ist wie linksrum, teilt man noch durch 2. Bleiben 14! / 2 Möglichkeiten zu untersuchen, und das sind 43.589.145.600 verschiedene Wege (das Beispiel und das Bild stammen von Kapitän Nemo at German Wikipedia).

Seit langem machen sich Wissenschaftler Gedanken, wie man schneller zu der Lösung kommt, als all die Möglichkeiten zu untersuchen. Es gibt diverse mathematische Verfahren für das Rundreiseproblem (traveling salesman problem TSP), die alle aufwendig sind. Das Studium der Methoden ist kein reiner mathematischer Zeitverteib, das TSP hat Anwendungen von der Maschinenbelegung bis hin zum Flugverkehr.

Deshalb stößt ein neuer Artikel von Nature Communications und PHYS.ORG auf einiges Interesse, Physics may bring faster solutions for tough computational problems (12.5.). Neu ist, dass physikalische Methoden eingesetzt werden. Wissenschaftler von der University of Central Florida (UCF) und von der Boston University (BU) haben einen neuen Ansatz entwickelt, der Statistische Mechanik verwendet. Das ist ein Bereich der Physik, der effizientere Algorithmen liefern kann, und die entsprechenden Programme können nicht nur auf herkömmlichen Computern laufen, sondern auch auf den erwarteten neuen Quantencomputern.

Statistische Mechanik wurde entwickelt, um Systeme mit vielen Teilchen zu analysieren, fest, flüssig oder gasförmig. Zunächst ging es um makroskopische Systeme, nun aber auch um eine Vielzahl von komplexen Materiezuständen von Magnetismus über supraleitende Systeme bis hin zu neuronalen und Verkehrsnetzen, zu Sandlawinen und Aktienkursfluktuationen.

Es gibt schon Algorithmen auf dieser Basis, die in erfolgreichen Computerprogrammen niedergelegt sind. Als Datengrundlage wird ein Graph verwendet, dessen Knoten Binärvariablen zugeordnet sind. Das Modell kann hardwaremäßig aufgebaut werden oder als Computersimulation repräsentiert werden. Dann wird das System gekühlt bzw. das computermäßige Äquivalent davon durchgeführt, und beim niedrigsten Energiezustand enthüllt sich die Lösung.

Das Problem bei diesem Ansatz sind die Phasendurchgänge, wie sie beim Übergang von flüssigen zu Glasphasen auftreten, wo viele konkurrierende Konfigurationen mit niedriger Energie parallel existieren. Solche Phasenübergänge bremsen den Kühlungsprozess zu einem Schneckentempo und können die Methode nutzlos machen.

Diese Worte stammen von Professor Eduardo Mucciolo, dem Vorstand vom Department of Physics des College of Sciences der UCF. Mucciolo und seine Kollegen Claudio Chamon und Andrei Ruckenstein von der BU haben diese Schwierigkeit überwunden.

Dazu bildeten sie das originale Rechenproblem auf ein elegantes statistisches Modell ohne Phasenübergänge ab, genannt "vertex model". Das Modell ist auf einem zweidimensionalen Raster repräsentiert. Jeder Kreuzungspunkt entspricht einem Schalter, der mit vier Nachbarn verbunden ist. Eingabe- und Ausgabedaten sitzen auf den Rändern des Rasters. Um die Phasenübergangsprobleme zu vermeiden, musste das Raster sehr gleichförmig sein und die Schalter mussten saubere "reversible logic gates" sein.

Die Methode arbeitet von hinten nach vorn, so dass die schwierigsten Probleme lösbar werden. Vorgangsweise ist, jedem der Schalter eine Energie zuzuordnen. Um den Schaltvorgang auszulösen, muss die Energie sehr niedrig sein. Wenn alle Schalter durchschalten, sollte die Gesamtenergie des Systems also besonders niedrig sein. Das ist ein ganz neuer Ansatz, das Problem anzugehen. Es vermeidet die massenweisen Phasenübergänge, die ein Haupthindernis der vorigen Modelle waren.

Das vertex model kann auch für komplexe Probleme beim Maschinellen Lernen eingesetzt werden, beim Layoutoptimieren und bei anderen zentralen Herausforderungen der Programmierung. Untersucht wird, ob sich das Modell auch zur Faktorisierung von Halb-Primzahlen eignet (semi-primes, die Produkte von zwei Primzahlen). Die Schwierigkeit, solche semi-primes zu faktorisieren, bildet die Grundlage der modernen Kryptographie und war einer der Hauptantriebe für die Schaffung von großen Quantencomputern. 

Mehr noch, das Modell kann verallgemeinert werden, um einen neuen Weg zur Lösung klassischer OR-Probleme zu liefern. Dabei wird der Vorteil der Parallelität ausgenutzt, den die Quantencomputer mit ihren Superpositionen verschiedener Zustände bieten, die viele klassische Zustände zugleich abbilden. Deshalb bietet das Verfahren Aussicht auf erhebliche Beschleunigung der Lösungszeiten für klassische OR-Probleme.

 

Link zum Originalartikel bei PHYS.ORG

Links von wissenbloggt:

Mehr zum Thema:
Dieser Beitrag wurde unter Wissenschaft veröffentlicht. Setze ein Lesezeichen auf den Permalink.

Schreibe einen Kommentar