Im letzten Monat habe ich jemanden getroffen, auf dessen Armbanduhr eine MCMC Simulation von Hamilton-Pfaden
auf einem quadratischen Gitter liefen. Ich war derartig begeistert, dass ich
beschlossen habe auch etwas auf meiner Pebble simulieren zu lassen. Aufgrund
der geringen Auflösung des Displays (\(144 \times 168\)) bieten sich “blockige”
Visualisierungen an. Glücklicherweise habe ich schon genügend Spielereien
geschrieben, die sich eignen
[1,
2,
3,
4].
Pebble wurde zwar inzwischen von Fitbit aufgekauft, aber das SDK ist noch
verfügbar. Die neueren Exemplare lassen sich per JavaScript programmieren,
meine “Kickstarter Edition” aus der ersten Generation allerdings noch nicht.
Da ich meine Uhr also in C programmieren muss, konnte ich allerdings den
den alten Code aus Wolfram’s Rules wiederbenutzen.
Man hat ein großes C++ Projekt, ändert einen Header, führt make aus und
ein seltsamer Fehler tritt im Programm auf. Das liegt natürlich daran, dass
make nicht alle Quelldateien neu kompiliert hat, die den Header einbinden.
Woher sollte make das auch wissen? Alle Header per Hand in der Makefile
einzutragen und zu pflegen, ist Wahnsinn und wird den Programmierer in denselben treiben.
make ist ein sehr allgemein gehaltenes Programm, wie ich in einem vorherigen Eintrag
gezeigt habe. Sich um Eigenheiten von C oder C++ zu kümmern fällt also nicht
in den Aufgabenbereich von make. Aber glücklicherweise gibt es ein Programm,
dessen Hauptaufgabe es ist, sich mit den Eigenheiten von C bzw. C++ auszukennen:
den Compiler.
Tatsächlich bietet (zumindest GCC) die Option eine C oder C++ Datei zu parsen
und alle inkludierten Header auszugeben.
g++ -MM myCode.cpp
Das ausnutzend, bietet die offizielle Dokumentation
von GNU make folgende Rule, um je eine “dependency” Makefile
pro .c Datei zu erzeugen und automatisch einzubinden.
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: