|
Seite 14 von 77 |
Das Travelling Salesman-Problem und die Alignments gehören zu der Klasse der sogenannten NP-vollständigen Probleme, die nur in exponentiell ansteigender Rechenzeit vollständig gelöst werden können.
Für den Programmierer bedeutet dies, dass er keinen Algorithmus anwenden kann, der das Problem vollständig löst, denn dann wäre der Rechenaufwand unvertretbar hoch. Vielmehr muss er einen Algorithmus finden, der das Problem in linear ansteigender Rechenzeit möglichst gut näherungsweise bearbeitet. Solche Algorithmen werden heuristische Algorithmen genannt.
Der Nutzer solcher heuristischen Algorithmen muss sich darüber im Klaren sein, dass er nicht die richtige Lösung erhält, sondern eine näherungsweise Lösung. Deren Güte hängt davon ab, welche Parameter er dem Programm übergeben hat. Zu solch einer näherungsweisen Lösung muss also auch stets deren Güte angegeben werden.