Kombinatorische Optimierung

Kombinatorische Optimierung Definition

In dem Begriff Kombinatorische Optimierung ist der Bezug zur Kombinatorik enthalten. D.h., es geht hier vor allem um Kombinationen und Permutationen und es soll die optimale (z.B. kürzeste, kostengünstigste, schnellste) gefunden werden.

Beispiel

Beim Travelling-Salesman-Problem soll z.B. die kürzeste Rundreise für einen Vertreter durch mehrere Städte gesucht werden.

Bei 3 Städten A, B und C gibt es dafür z.B. 2 mögliche Touren: 1) A - B - C - A oder 2) A - C - B - A.

Kombinatorische Optimierung heißt dann, aus den kombinatorischen Möglichkeiten die optimale (hier die kürzeste Route) zu finden (im Beispiel ist das uninteressant – die beiden einzig möglichen Touren sind gleich lang).

Bei größerer Grundmenge (z.B. 10 Städte) gibt es bereits Hunderttausende Möglichkeiten, deshalb ist das nicht trivial.

Ähnlich soll beim Rucksackproblem eine Teilmenge aus einer Menge von Gegenständen optimal ausgewählt werden, ebenfalls ein kombinatorisches Optimierungsproblem.