Vollständige Enumeration

Vollständige Enumeration Definition

Vollständige Enumeration bei Optimierungsproblemen bedeutet: 1) alle Möglichkeiten vollständig aufzählen und berechnen und 2) je nachdem, um was es ging, das Maximum (zum Beispiel höchster Gewinn) oder Minimum (zum Beispiel kürzeste Strecke) auswählen.

Das ist eine einfache Methode; das Ergebnis wird nicht mit intelligenten Algorithmen, sondern mit reiner Rechenkraft der Computer berechnet. Vorteil: man findet garantiert das Optimum (keine Näherungslösung).

Beispiel

Beispiel: Vollständige Enumeration

Möchte man beispielsweise 4 Städte auf einer Rundreise mit der kürzesten Gesamtstrecke besuchen (als Travelling-Salesman-Problem bekannt), könnte man alle Möglichkeiten für die Route auflisten und deren jeweilige Strecke berechnen und die kürzeste Strecke auswählen.

Die Städte und (fiktiven, klein gehaltenen) Entfernungen seien:

Aachen - Bonn : 1 km

Aachen - Celle: 3 km

Aachen - Dortmund 5 km

Bonn - Celle: 4 km

Bonn - Dortmund: 8 km

Celle - Dortmund: 10 km

Bei 4 Städten gibt es (4-1)! = 3! = 3 × 2 × 1 = 6 Möglichkeiten.

Wenn man die 4 Städte nur mit ihren Anfangsbuchstaben schreibt, sind das folgende 6 mögliche Touren:

A - B - C - D - A = 1 + 4 + 10 + 5 = 20 km

A - B - D - C - A = 1 + 8 + 10 + 3 = 22 km

A - C - B - D - A = 3 + 4 + 8 + 5 = 20 km

A - C - D - B - A = 3 + 10 + 8 + 1 = 22 km

A - D - B - C - A = 5 + 8 + 4 + 3 = 20 km

A - D - C - B - A = 5 + 10 + 4 + 1 = 20 km

Allerdings ist jeweils die Hälfte der gefundenen Rundreisen eine Umkehrung (mit gleicher Wegstrecke; zum Beispiel die 2. Tour A - B - D - C - A und die 4. Tour A - C - D - B - A). Deshalb würde es reichen, die Hälfte der Touren zu berechnen, bei 6 Städten also 3.

Die kürzeste Rundreise benötigt 20 km (und man kann hier im Beispiel aus mehreren 20 km - Touren wählen).

Die vollständige Enumeration ist im Grundsatz geeignet für die kombinatorische und ganzzahlige Optimierung.

Für Optimierungsprobleme, bei denen die Anzahl der möglichen Lösungen (im Beispiel gab es maximal 6 Lösungen) vielleicht groß, aber endlich ist, ist die vollständige Enumeration gut machbar; die Berechnungszeit durch den Computer wächst allerdings exponentiell, bei einer sehr großen Ausgangsmenge (zum Beispiel Anzahl Städte) kann die Berechnung dauern.

Neben der vollständigen Enumeration gibt es noch sogenannte Enumerationsverfahren, die versuchen, abzukürzen, das heißt, aufzulisten, aber nicht vollständig.