möchte­gern­geek

Das Problem des Handlungsreisenden ist es, die kürzeste Rundtour zu planen, sodass man alle Städte besucht. Es ist eines der berühmtesten Optimierungsprobleme und gehört zur Klasse NP-hard.

Es gibt also (bis jetzt) keine effiziente Möglichkeit zur Lösung. Allerdings gibt es Näherungen, untere Schranken und unzählige Heuristiken.

Die einfachsten dieser Heuristiken habe ich in einem kleinen Programm TSPview implementiert, mitsamt Visualisierung. Der Quellcode ist auf GitHub zu finden.

Algorithmen

Hier folgt eine kurze Beschreibung der verwendeten Algorithmen und jeweils ein Bild, welche Lösung die Methode auf einer berühmten Instanz des TSP findet.

Das sind 42 Hauptstädte der Vereinigten Staaten von Amerika und Washington, DC (Hawaii und Alaska, sowie einige Staaten an der Ostküste, die das Problem nicht schwieriger machen, fehlen). Dieses Problem war das erste größere, das 1956 beweisbar optimal gelöst wurde.

Nearest Neighbor

Die Nearest Neighbor Heuristik (\(\mathcal{O}(N^2)\)) startet bei einer zufälligen Stadt und wählt als nächste Stadt immer die Stadt, die am nächsten an der aktuellen Stadt ist und noch nicht besucht wurde.

Greedy

Diese Heuristik (\(\mathcal{O}(N^2 \log N)\)) ist ähnlich zu Kruskals Algorithmus für minimal spannende Bäume. Sie nimmt die kürzeste Verbindung zwischen zwei Städten und fügt sie der Tour hinzu, wenn sie in der Tour noch erlaubt ist.

Farthest Insertion

Farthest Insertion (\(\mathcal{O}(N^3)\)) startet bei einer zufälligen Stadt und fügt dann die Stadt, die am weitesten von der aktuellen Tour entfernt ist an der Stelle in die Tour, die dafür sorgt, dass die Tour möglichst kurz bleibt.

Two-Opt

Two-Opt beginnt mit einer beliebigen Tour, die bspw. durch eine der obigen Heuristken erstellt wurde und verbessert sie, indem sie zwei Verbindungen nimmt und die Endpunkte über Kreuz austauscht, wenn die Tour dadurch verbunden bleibt und kürzer wird.

Lineare Programmierung mit „Subtour Elimination Cuts“

Lineare Programmierung (LP) zu erklären, würde diesen Artikel sprengen. Aber diese Methode liefert untere Schranken für die Tourlänge und kann somit benutzt werden, um die Qualität einer heuristischen Lösung abzuschätzen. Falls man die optimale Lösung durch lineare Programmierung findet, erkennt man sie auch sofort als optimal.

Für weitere Details, kann ich auf einen arXiv Artikel von mir verweisen.

Concorde

Concorde ist der „State of the Art“ Solver für das Problem des Handlungsreisenden und löst problemlos Instanzen mit mehr als 1000 Städten. Intern benutzt es zwar eine Menge Heuristiken, allerdings auch lineare Programmierung, um nachzuweisen, dass die gefundene Lösung optimal ist.

Technische Details

TSPview ist ein Python3 Programm, das zur Darstellung PyQt5 benutzt, das sich per pip3 install PyQt5 einfach installieren lässt.

Darüber hinaus enthält es eine optionale Abhängigkeit zu CPLEX, einem kommerziellen LP solver.

boost::python

Da das Hauptprogramm in Python geschrieben ist, aber der LP-Teil in C++, braucht man eine Möglichkeit der Kommunikation. Glücklicherweise gibt es mit boost::python eine Möglichkeit C++ Klassen in Python als Python-Klassen zu benutzen.

Um beispielsweise die C++ Klasse MyClass, deren Konstruktor einen Integer und eine Python-Liste entgegen nehmen soll, in Python benutzen und myMethod aufrufen zu können, reicht folgender Code:

#include <boost/python.hpp>
namespace py = boost::python;

// implement MyClass

BOOST_PYTHON_MODULE(MyClass)
{
    py::class_<MyClass>("MyClass", py::init<int, py::list>())
        .def("myMethod", &MyClass::myMethod)
    ;
}

Programmiersprachen muss man üben, um sie zu lernen und um sie nicht wieder zu vergessen. Ich habe also meine Zeit damit vertrieben einen SHA-256 zu schreiben — eine kryptographische Hash Funktion. Die Spezifikation ist glücklicherweise sehr sehr verständlich. Und auch wenn es tausende andere Implementationen gibt, die schneller sind, alle Grenzfälle beachten (ich befürchte, dass mein Programm Probleme auf Big Endian Systemen bekommt), und sogar Schaltkreise, die hochoptimiert nur diese Operation beherrschen (Stichwort: Bitcoin ASIC), ist meiner dennoch sehenswert, da er SHA-256 in 256 Zeilen darstellt.

Der Code ist als Gist auf GitHub, da er in seinen 256 Zeilen ansonsten den Lesefluss stören würde.

In Python ist es übrigens etwas kürzer.

print(hashlib.sha256(b"Hallo Welt!").hexdigest())

Nachdem ich so vielen Differenzialgleichungssystemen [1, 2, 3, 4] begegnet bin, die sich nicht analytisch lösen lassen, habe ich mir ein Programm zur numerischen Lösung und Visualisierung derselben geschrieben.

Die grundlegende Idee zur numerischen Lösung von Differentialgleichungen ist es, die Zeit in diskreten Schritten \(\tau\) vergehen zu lassen. Nach jedem Schritt wird der Zustand so geändert, als ob sich während des Zeitschrittes nichts geändert hätte und die „Kräfte“ werden entsprechend der Bewegungsgleichungen neu berechnet. Für infinitesimal kleine \(\tau \to \mathrm{d}t\) ist diese Methode schließlich exakt.

Im einfachsten Fall, dem Euler Verfahren, sähe das für ein einfaches Fadenpendel nach \(k\) Zeitschritten so aus

Unglücklicherweise hat dieses Verfahren ernsthafte Probleme mit der Energieerhaltung und braucht sehr kleine \(\tau\) für brauchbare Ergebnisse. Es gibt deutlich ausgefeiltere Methoden, wie den klassischen Runge-Kutta Algorithmus. Es gibt Methoden, den Zeitschritt \(\tau\) während der Simulation adaptiv anzupassen, um nur wenig Rechenaufwand in den wenig fehleranfälligen Phasen zu verbringen. Es gibt spezialisierte Methoden, die sehr gut für bestimmte Bewegungsgleichungen funktionieren, wie Velocity-Verlet, der oft für Molekulardynamiksimulationen eingesetzt wird.

Chaotische Systeme haben in der Regel etwas kompliziertere Bewegungsgleichungen. Das oben abgebildete Doppelpendel etwa wird, wie ich in einem anderen Post beschrieben habe durch folgendes Ungetüm beschrieben.

Anfangs empfiehlt es sich also etwas einfacheres und vertrauteres zu lösen, wie den Lorenz-Attraktor

Oder das Dreikörperproblem

Da man das 3-Körperproblem trivial auf ein \(N\)-Körperproblem erweitern kann, habe ich hier ein „Sonnensystem“ bzw. Bohrsches „Atom“-modell simuliert.

Um die obigen (bewegten) Bilder zu erzeugen und um ein bewegtes Doppelpendel für meinen Schreibtisch zu haben, — wennauch nur auf einem Bildschirm — habe ich in C++ einen adaptiven Runge-Kutta-4 Löser geschrieben, der mit den Qt Zeichenprimitiven animiert wird.

Auch wenn der Code nicht sehr aufgeräumt ist und Startwerte im Quellcode angepasst werden müssen, sind die Quellen auf GitHub: github.com/surt91/DGLshow.