next up previous contents
Next: Aufgabenstellung des Netzes Up: No Title Previous: Contents

Einleitung

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.




Marius Heuler
Thu Nov 23 00:27:57 GMT 1995