möchte­gern­geek

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.

%.d: %.c
    @set -e; rm -f $@; \
    $(CC) -M $(CPPFLAGS) $< > $@.$$$$; \
    sed ’s,\($*\)\.o[ :]*,\1.o $@ : ,g’ < $@.$$$$ > $@; \
    rm -f $@.$$$$

include $(sources:.c=.d)

Falls man .o Dateien in ein obj/ Verzeichnis speichert, muss man die Regex anpassen. In meinen Projekten leistet mir diese Rule gute Dienste.

Alternativ könnte man natürlich auf ein anderes Buildsystem statt handgepflegter Makefiles umsteigen.

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)
    ;
}

Simulated Annealing ist eine Optimierungsmethode, die von natürlichen Kristallisationsprozessen inspiriert ist. Man startet in der Schmelze bei hohen Temperaturen und lässt es dann abkühlen, sodass die Atome sich in einem Zustand minimaler Energie anordnen, dem Kristallgitter. Wenn man also für ein Optimierungsproblem die zu optimierende Größe als Energie ansieht, und man eine Lösung durch eine kleine Änderung in eine andere Lösung verwandeln kann, kann man mit dieser Methode eine Näherung für das Optimum finden.

Wenn wir also eine Sequenz \(S\) von \(N\) Zahlen sortieren wollen, können wir die Summe der Differenzen zwischen benachbarten Zahlen als Energie betrachten, denn die ist minimal in einer sortierten Liste.

Um eine Lösung in eine andere zu verwandeln, reicht es zwei Elemente der Sequenz zu tauschen.

Der Kern von Simulated Annealing ist der Metropolis Algorithmus.

1. Starte bei einer hohen Temperatur \(T\).
2. Berechne die Energie \(\mathcal{H}(S)\) der aktuellen Konfiguration \(S\).
3. Erzeuge eine neue Konfiguration \(R\) durch eine kleine Änderunge von \(S\).
4. Akzeptiere \(R\) mit der Wahscheinlichkeit
   $$p_\mathrm{acc} = \min\left[1 ,\exp(-(\mathcal{H}(R) - \mathcal{H}(S))/T) \right],$$
   sodass eine „sortiertere“ Sequenz immer akzeptiert wird und eine „unsortiertere“ vor allem bei hohen Temperaturen. Wenn \(R\) akzeptiert wird, gilt \(S:=R\), ansonsten wir die alte Konfiguration \(S\) weiter benutzt.
5. Reduziere die Temperatur (beispielsweise durch Multiplikation mit einer Zahl etwas kleiner als 1) und breche ab, wenn die Zieltemperatur erreicht ist. Ansonsten beginne wieder bei Punkt 2.

Genug der Theorie: In einem Gist auf GitHub präsentiere ich ein schnell terminierendes Sortierprogramm, das zwar nicht immer eine sortierte Liste findet, aber zumindest eine Näherung! Es ist also Bogosort in mehr als nur einer Hinsicht überlegen!

Wer braucht da noch \(\mathcal{O}(N \log(N))\) Sortier-Algorithmen?!