Vollständige Enumeration

Die vollständige Enumeration kann herangezogen werden, um das in vorherigen Abschnitt dargstellte Traveling-Salesman-Problem zu lösen. Bei der vollständigen Enumeration werden alle möglichen Lösungen ermittelt und danach die Lösung mit dem geringsten Wert ausgewählt, es handelt sich also um ein exaktes Verfahren zur Bestimmung einer optimalen Lösung. Für das Traveling-Salesman-Problem bedeutet dies, dass zunächst alle möglichen Rundreisen ermittelt werden und danach diejenige Rundreise mit den geringsten Kosten oder der kürzesten Zeit ausgewählt wird. 

Das Problem der vollständigen Enumeration ist die Anzahl der möglichen Lösungen. Für $n$-Knoten existieren $(n - 1)!$ mögliche Lösungen. Die manuelle Anwendung der vollständigen Enumeration ist bis zu einer Knotenanzahl von $n = 6$ gerade noch vertretbar:

$(6 - 1)! = 5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$

Bei einer Knotenanzahl von $n = 6$ existieren also 120 mögliche Lösungen. Bei einer Knotenanzahl von $n = 7$ schon 720 mögliche Lösungen uws.

In diesem Abschnitt sol gezeigt werden, wie man die vollständige Enumeration anwendet, wenn $n = 5$ Knoten gegeben sind. Die möglichen Lösungen sind dann $(5 - 1)! = 24$.

In den folgenden zwei Abschnitten wird das Verfahren der vollständigen Enumeration anhand des Traveling-Salesman-Problems dargestellt.