Formale Methoden und Deduktion
Prof. Dr. J. Avenhaus

 FB Inf

Das Problem des Handlungsreisenden

TSP
Das Problem des Handlungsreisenden ist ein sogenanntes Optimierungsproblem, das heißt, es reicht nicht, bei der Suche eine Lösung zu finden, sondern man möchte die bestmögliche (oder zumindest eine sehr gute) haben.
Die Formulierung des Problems ist sehr einfach: Ein Handlungsreisender muß Kunden in einer Reihe von Städten besuchen und zwar in jeder Stadt genau einen. Da er möglichst wenig unterwegs sein möchte, will er die kürzest mögliche Route für seine Tour zusammenstellen. Er kennt die kürzesten Entfernungen zwischen je zwei Städten.
Im nebenstehenden Bild sehen wir das Problem für fünf Städte graphisch umgesetzt mit zwei möglichen Touren. Bei so wenigen Städten sieht das Problem noch relativ leicht aus. Betrachtet man aber 100 oder sogar 1000 Städte, so stellt man schnell fest, daß eine systematische Suche sehr aufwendig ist.
Bisher ist es noch niemandem gelungen, ein Verfahren anzugeben, das nicht exponentiell in der Größe der Eingabe (das sind im wesentlichen die Entfernungsangaben) aufwendiger wird. Man vermutet sehr stark, daß es gar kein Verfahren gibt, das nicht mindestens dieses exponentielle Verhalten zeigt, konnte das allerdings bisher nicht beweisen. Man konnte allerdings beweisen, daß das Problem des Handlungsreisenden ein Muster für eine Menge von Problemen mit diesem exponentiellen Verhalten (die Klasse NP) ist. Dies ist der Grund, warum sich viele Forschungsgruppen in der Informatik mit diesem Problem beschäftigen, da gute Verfahren auf andere Probleme übertragen werden können.
Hier geht es
Impressum AG Formale Methoden und Deduktion Fachbereich Informatik Technische Universität Kaiserslautern Valid HTML 4.01!
Letzte Änderung: Wednesday, 26-Oct-05 08:59:21 GMT
www-aven@informatik.uni-kl.de