Direkt zum Inhalt

Lexikon der Mathematik: algorithmische Prinzipien

Methoden zum Entwurf effizienter Algorithmen (effizienter Algorithmus).

Eine der bekanntesten Methoden ist die Divideand-Conquer Technik, bei der Probleme in Teilprobleme zerlegt werden, diese rekursiv gelöst werden und schließlich die Gesamtlösung aus den Teillösungen zusammengesetzt wird.

Bei der dynamischen Programmierung werden die Teilprobleme nach aufsteigender Größe behandelt. Bei der Behandlung größerer Probleme kann auf die Lösung kleinerer Probleme zurückgegriffen werden.

Branch-and-Bound Methoden finden bei Optimierungsproblemen Anwendung. Für den optimalen Wert der Lösung jedes betrachteten Teilproblems werden untere und obere Schranken berechnet. Noch nicht gelöste Teilprobleme werden weiter zerlegt, wobei die Betrachtung von Teilproblemen, deren Lösung die beste bekannte Lösung nicht übertreffen kann, eingespart wird. Während die genannten Methoden sichern, daß eine optimale Lösung gefunden wird, kann bei heuristischen Suchverfahren nur gehofft werden, daß oft eine gute Lösung berechnet wird. Zu diesen Strategien zählen Greedy Algorithmen, Lokale Suche, Simulated Annealing sowie evolutionäre und genetische Algorithmen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos