next up previous contents
Next: Simulated Annealing Up: Verfahren zur nichtlinearen Previous: Verfahren zur nichtlinearen

Nichtlineare Optimierung als NP-hartes Problem

NP-harte Probleme sind Probleme, bei denen die Zahl der benötigten Rechenoperationen für eine algorithmische Lösung stärker als polynomial mit der Komplexität der Problemstellung anwächst. Das bedeutet, daß der Rechenaufwand so schnell mit der Zahl der Unbekannten, Dimensionen, etc. wächst, daß schon mittlere Probleme eine Rechenzeit benötigen, die auch bei Verwendung aller Supercomputer der Welt zusammen nicht bis zum Ende der Lebensdauer des Sonnensystems abgearbeitet wäre. Diese Aussage gilt für ein allgemeines Problem aus der betrachteten Klasse. Für einzelne Problemfälle kann es aber einen Algorithmus geben, der die Lösung in kurzer Zeit findet. Die vorgestellten Methoden können also durchaus --- mit etwas Glück --- eine Lösung finden.



Werner Eberl
Sat Apr 15 13:17:50 MET DST 1995