BLOG / FORSCHUNG – SOFTWAREENTWICKLUNG

RÄTSEL MACHEN MACHT MEHR SPASS ALS RÄTSEL MACHEN – DAS TRAVELLING SALESMAN-PROBLEM


KONTAKT ›

I Ich habe nicht viele Kreuzworträtsel gemacht und wenn, dann ging es meistens schnell, was auf eine Verbindung von mangelndem Vokabular mit mangelnder Geduld zurückzuführen war. Wenn mir die Vokabeln beim Kreuzworträtseln ausgingen, gab es meistens den kurzen Moment, in dem die Gedanken abschweiften und ich mich fragte, wie man generell wohl Rätsel erzeugt. Im Folgenden möchte ich ein kleines Rätsel vorstellen, dass wir Studenten angeboten haben, die unseren FLS Campus besucht haben. Ich möchte erläutern, warum dieses Rätsel ein altbekanntes Optimierungsproblem ist und wie ich versucht habe, es einigermaßen übersichtlich aber trotzdem schwierig zu gestalten.


In der Abbildung sieht man 7 Icons von Orten oder Produkten und diese sind durch eine Vielzahl von Linien verbunden. Der Leser mit mathematischem Hintergrund nennt so etwas „Graph“. Er fängt an von 7 „Knoten“ und diese verbindenden „Kanten“ zu schwadronieren und wetzt sich erregt das Kinn. Wie dem auch sei, an den Kanten sind jeweils noch eine Zahl und ein Buchstabe zu sehen.

In dem Rätsel ging es nun um Rundreisen, die ausgehend vom HQ (Headquarters) entlang der Kanten jeden Knoten genau einmal besuchen und dann wieder zum HQ zurückkehren. Im Folgenden nennen wir diese Rundreisen Touren, die Symbole Knoten, Verbindungen Kanten, Zahlen an Kanten Kosten. Aufgabe war es, diejenige unter diesen Rundreisen zu finden, bei der die Summe aller Zahlen an den gewählten Kanten minimal ist. Die Buchstaben an den gewählten Kanten ergeben dann ein Lösungswort (Nein, ich verrate es nicht). Wir haben es hier mit einem Klassiker aus dem Operations Research zu tun, dem Großvater der Optimierungsprobleme, dem Optimierungsproblem, das (textuell) schon formuliert wurde, als es auf der Welt weniger Rechner gab als manche Leute Vornamen haben:


»Das Travelling Salesman-Problem – Es taucht bereits um die Wende zum 20. Jh. auf, noch bevor Begriffe wie "Operations Research" geprägt werden, oder es Computer gibt.«




Berechnungen zum Finden guter Rundtouren finden täglich tausende auf Rechnern im Keller von FLS statt, nämlich wenn es um die Ressourcen-schonende Anordnung von Kundenaufträgen geht. Zugegeben, die „Summe der Zahlen, die an den Kanten stehen“, wird noch durch eine Vielzahl anderer Faktoren verkompliziert, aber das Grundproblem steckt drin und trägt entscheidend zur „Schwierigkeit“ bei!

Ich habe mich seit meinem Studium der Informatik schon viele Stunden damit beschäftigt, wie man spezielle Abwandlungen solcher Planungsaufgaben effektiv mit Algorithmen lösen kann. Mein Ziel für das Rätsel war es jetzt, eine Aufgabenstellung zu entwerfen, die überschaubar ist und trotzdem ein gewisses Engagement erfordert. Ehrlich zugegeben: Ich wollte die Rätsel-Nerds in eine „Probiere ich das jetzt schnell durch oder code ich mir jetzt doch ein Programm dafür?!“-Zwickmühle treiben. Ich finde, es kommt dem Alltag vieler Tätigkeiten als Entwickler nahe, permanent zu hinterfragen, ob der Ansatz, den man gerade verfolgt, die Techniken und Technologien, noch die zielführendsten sind.

Wie habe ich das Rätsel erzeugt? Hier im „Pseudocode“:
  1. Länge des Lösungswortes überlegen; dies liefert die Anzahl der Knoten.
  2. Zufällige Kanten einsetzen. Je mehr, desto mehr mögliche Touren, aber desto unübersichtlicher. (Fun Fact: Das ist auch der Punkt, an dem ich beschloss, es „auszuprogrammieren“)
  3. Alle Touren berechnen.
  4. Solange es verschiedene Touren gibt, die zu minimalen Kosten führen, erhöhe die Kosten einer Kante, die nicht auf allen günstigsten Touren vorkommt.
  5. Fies: Erhöhe die Kosten von zufällig gewählten Kanten, die nicht auf der (jetzt eindeutigen) günstigsten Tour liegen. Dadurch werden andere Touren günstiger.
  6. Die Knoten und Kanten automatisch zeichnen lassen mit Graphviz. Falls unübersichtlich oder durch scharfes Hinsehen zu lösen, wiederhole ab Punkt 2.
  7. Zum Abschluss graphische Umsetzung zusammen mit einem Designer. (Ihm habe natürlich verraten, welche die kürzeste Tour ist, damit er die Beschriftung mit dem Lösungswort vornehmen konnte ;) )

Programmiert habe ich in C# unter OS X mit Xamarin Studio

Sourcecode hier
Alternativprogramm hier