In der Informatik treten häufig Probleme auf, die als sogenannte
,,NP-vollständige Probleme`` bezeichnet werden. Hierbei bedeutet
NP-vollständig, daß die Laufzeit zum Auffinden einer optimalen Lösung
exponentiell mit der Größe des Problems anwächst. Diese Probleme
stellen eine große Herausforderung an die Algorithmen dar, da für
große Problemgrößen Verfahren mit exponentieller Laufzeit in der
Regel nicht mehr anwendbar sind.
Ein Beispiel für ein
NP-vollständiges Problem ist das Problem des Handlungsreisenden.
Hierbei soll eine möglichst kurze Rundreise zum Besuch von vorgegebenen
Städten gefunden werden.