TSP: Das Travelling Salesman Problem

Vor einigen Wochen beschäftigten wir uns im Informatikunterricht mit dem Travelling salesman problem. Ohne näher auf die existierenden Algorithmen zum Lösen dieses Problems einzugehen lernten wir, dass es sich bei diesem Problem um ein NP-Vollständiges Problem handelt. Das TSP ist also eine Problemstellung die sich nicht in polynomieller Zeit lösen lässt. Anders ausgedrückt, lässt sich die Laufzeitkomplexität dieses Problems in Abhängigkeit von der Problemgröße n (Anzahl der Knoten bzw. Städte) nicht ausschließlich mit einem Polynom beschreiben.

Es existieren zwar einige Algorithmen die die perfekte Lösung mehr oder weniger gut annähern können und dafür nur eine zu n quadratische Komplexität besitzen (O(n²)).

Eine perfekte Lösung lässt sich bis heute praktisch aber noch nicht exakt bestimmen. TSP: Das Travelling Salesman Problem weiterlesen

n-Damen Problem

Für meine morgige Informatik-Klausur habe ich mich mal wieder an C++ gewagt um einen Algorithmus zu implementieren. Die Hauptthemen der Klausur werden das n-Dame Problem und das Josephus Problem sein.

JS, PHP & CSS Frontend

Für das n-Damen-Problem habe ich eine iterative Backtracking-Implementation in C++ geschrieben. Gleichzeitig ist es mein erstes funktionsfähiges und komplexeres C++ Programm 😉

Um euch meine Ergebnisse zeigen zu können, habe ich mich bei der PHP, JS & CSS Version meines Freundes Micha bedient und sie leicht angepasst.

Das PHP-Script ruft über den Backtick-Operator das C++ Programm auf und stellt es anschließen mit JS und CSS dar.

Um den Server zu schonen habe ich die maximale Feldgröße auf 13 beschränkt. Das sind zu mindestens schon mal 5 Damen mehr als bei der PHP-Version.

Ohne die Beschränkung sind auch Problemgrößen bis 16 in einem angemessenen Zeitrahmen zu bewältigen. An den Weltrekord (25 Damen) komme ich jedoch noch nicht 😉

Wer interesse an dem Quellcode hat, kann sich einfach per Mail melden.