Das Problem des Handlungsreisenden
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
Bei Fragen, Problemen oder Anregungen bitte E-mail an
denzinge@informatik.uni-kl.de