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