TravelingSalesmanProjekt

Achtung, das ganze Projekt ist derzeit nur unter Linux lauffähig!

Motivation

Mit diesem Projekt will ich zeigen:

• Wie C++ Programme/Funktionen aus Matlab heraus gestartet werden können
• Wie ein einfaches makefile funktioniert
• Wie die GSL GNU_Scientific_Library verwendet wird
• Wie man die C++ Funktion debugt (und das ist vielleicht der wichtigste Punkt)

Ein ganz einfacher Traveling Salesman Algorithmus

Das Traveling Salesman Problem ist ein recht alltägliches Problem der Theoretischen Informatik. Es modelliert die Frage, wie man möglichst schnell oder billig mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt.
Als Beispiel habe ich einen ganz einfachen Algorithmus gewählt: Es werden einfach alle möglichen Wege berechnet. Dazu werden die Stadtkoordinaten einfach durchpermutiert, und jeweils die Weglänge berechnet. Das kann normalerweise nur in einer for Schleife gemacht werden, und ist somit in C/C++ wesentlich schneller als in Matlab zu berechnen.
Den nicht zeitkritischen Programmteil lässt sich oft besser in Matlab programmieren, weil es einfach bequemer ist.

Projektaufbau

Wie in der Grafik angedeutet besteht das Projekt aus mehreren Dateien. Es gibt einen Matlab Teil und einen umfangreichen C++ Teil. Die eigentliche Berechnung der kürzesten Route wird in berechnung.cc durchgeführt. Die Funktion rechnen() in berechnung.cc kann entweder von Matlab aus mit hilfe von m_c_interface.cc aufgerufen werden, oder von main() in c_c_interface.cc.
Das klingt etwas umständlich. Warum nicht direkt von Matlab aus die Funktion rechnen() in berechnung.cc aufrufen? Wozu die anderen Dateien? Auch die kurze Version wäre eine Möglichkeit. (Man müsste dann berechnung.cc ein wenig umschreiben.) Man würde dann nur die zwei Dateien brauchen. Es würde aber zwei grosse Nachteile geben:

• Die Funktion rechnen() könnte dann nur von Matlab aus gestartet werden.
• Das Debuggen der C++ Funktion ist dann wesentlich schwieriger.

Wie die Funktion von Matlab aus verwendet wird

• In Matlab wird eine (n * 2) Matrix generiert. n ist die Anzahl der Städte, in der Matrix stehen die Stadtkoordianten.
• Es wird vom Matlab m_c_interface.cc als externe Funktion aufgerufen, die Städtematrix wird als Argument übergeben.
• Im m_c_interface.cc werden die Matlab- Argumente 'abgeholt', die Städtematrix wir in ein C++ Array kopiert, es wird Speicher für die Rückgabewerte reserviert. Dann wird die externe C++ Funktion rechnen() aufgerufen.
• In der Funktion rechnen() wird die Stadtreihenfolge durchpermutiert und der kürzeste und längste Weg gesucht. Für das Durchpermutieren wird die GSL Library verwendet.
• rechnen() speichert die zwei Wege in den von m_c_interface.cc Reservierten Speicher.
• rechnen() beendet, und springt zu m_c_interface.cc zurück.
• m_c_interface.cc beendet, und das Matlab Script wird weiter abgearbeitet. Die Wege werden dort graphisch dargestellt.

Wie die Funktion als reines C++ Programm verwendet wird

• Mit c_c_interface.cc kann das alles auch ohne Matlab ausgeführt werden. In c_c_interface.cc befindet sich die Funktion main().
• Nach dem kompilieren von c_c_interface.cc kann dieses main() mit dem Konsolen Befehl

$ ./c_c_interface

Ausgeführt werden. (Vorher muss eventuel noch ein make ausgeführt werden, und das Verzeichniss muss natürlich stimmen.)

• In c_c_interface.cc wird ähnlich wie in m_c_interface.cc Speicher reserviert, und die funktion rechnen() in berechnung.cc ausgeführt. Es wird also die gleiche Funktion rechnen() ausgeführt, die auch von Matlab heraus indirekt verwendet wird.
• c_c_interface.cc bekommt von rechnen() die zwei Wege, sie werden dann als Text ausgegeben.

Debuggen

In C++ programmen nach Ursachen für einen Speicherzugriffsfehler zu suchen, ist mühsam. Es gibt aber Tools (siehe Cpp_Programmierung) die dabei eine grosse Hoilfe sind. Sie funktionieren aber nur aus der Konsole heraus. Das bedeutet die von Matlab aus aufgerufene Funktion kann damit nicht getestet werden. Dafür gibt es bei diesem Projekt das c_c_interface.cc, das von der Konsole gestartet wird.
Zur Demonstration, was passiert wen man in berechnung.cc in Zeile 70

optimaler_weg[i] = gsl_permutation_get(p, i);

durch

optimaler_weg[i+1] = gsl_permutation_get(p, i);

ersetzt, (und mit make kompiliert)? Wenn das Matlab Script nun ausgeführt wird, und mann Glück hat, stürzt das Matlab gleich ab. Vielleicht aber auch nicht, und man glaubt, richtig programmiert zu haben. Dafür kann es aber später doch noch abstürzen, und keiner weiss warum.
Wenn man aber das Projekt aus der Konsole heraus ausführt kann es auch einen Speicherzugriffsfehler verursachen, oder auch nicht. Es gibt aber noch das valgrid Tool.

$ valgrind ./c_c_interface

gibt unter anderem folgende Ausgabe:

==16825== Invalid write of size 8
==16825==    at 0x8049B21: rechnen(double**, int, int, double, int, double*, double*) (berechnung.cc:70)

Wir haben also in Zeile 70 in berechnung.cc in nicht initialisierten Speicher geschrieben! So etwas darf man im Programmcode auf keinen Fall stehelassen! Mehr zu valgrind: Cpp_Programmierung

Das Makefile

Da das Projekt aus mehreren Quellcode- Dateien besteht, ist es einfacher mit einem makefile zu arbeiten. Mehr zu make ist hier geschrieben: GNU_Make. Bei diesem Projekt wird die GSL- library verwendet, deshalb sind die entsprechenden Compilerflags dafür im makefile gesetzt. m_c_interface.cc wird statt mit g++ mit dem Befehl mex kompiliert. Dazu muss mex vor der erstmaligen verwendung mit

$ mex -setup

initialisiert werden. mex kompiliert C/C++ Dateien die von Matlab aus gestartet werden sollen. Auch beim mex können die üblichen g++ Compilerflags gesetzt werden. Weitere Optionen bekommt man mit

$ mex -help

Die Projektdateien

Die Projektdateien sind hier zu finden:
http://itp.tugraz.at/~golubk_a/download/matlab_c3/

• traveling_salesman.m ist das Hauptprogramm das aus Matlab heraus gesttartet wird. Es wird hier die Stadtliste erstellt, die Stadtkoordinaten werden zufällig gewählt. Es wird die in C++ geschriebene Unterfunktion aufgerufen. In der Funktion wird der beste und der schlechteste Weg berechnet. Die Ergebnisse werden wiederum in Matlab visualisiert.

• m_c_interface.cc beinhaltet die Funktion, die von Matlab aus gestartet wird. Die von Matlab übergebenen Parameter werden ein wenig umstrukturiert, speicher wird für die Rückgabeparameter an Matlab reserviert. Dann wird die Funktion rechnen in der Datei berecnung.cc aufgerufen. Diese Funktion sucht den optimalen weg.

• berechnung.cc Die Funktion rechnen befindet sich in dieser Datei. Die Funktion bekommt die Städteliste und berechnet die Reisedauer für alle möglichen Reiserouten. Die Beste und die schlechteste werden zurückgegeben. Es wird hier die GSL GNU_Scientific_Library verwendet um alle Permutationen der Stadtliste zu finden.

• c_c_interface.cc hier ist das Program main zu finden. Es wird gestartet, indem in der Konsole

$ ./c_c_interface

eingegeben wird. Das Program macht das gleiche wie traveling_salesman.m, nur ohne die Visualisierung. Es ist ein reines C++ Programm und benötigt Matlab nicht. Es ruft ebenfalls die Funktion rechnen auf, und gibt dann die gefundene Reiseroute als Text aus.

• makefile Mit dem Konsole Befehl

$ make

wird das makefile ausgewertet, und die C++ Programme, wenn nötig, neu kompiliert. Nach jeder Änderung in einer der C++ Dateien sollte man make ausführen.

--Golubkov 00:58, 14 Jul 2005 (CEST)