Beispiel: Vollständige Enumeration (Reduktion der Matrix)

Beispiel: Vollständige Enumeration beim TSP

Die obige Matrix stellt eine Maschine dar mit den Produkten $i = 1, 2, 3, 4, 5$. Die Kosten $c_{ij}$ sind gegeben für die Umrüstung der Maschine von z.B. Produkt 3 auf Produkt 1 mit 32 Geldeinheiten (GE). Gesucht wird diejenige Reihenfolge mit minimalen Umrüstungskosten.

Da hier die Matrix gegeben ist, muss kein Graph gezeichnet werden. Es wird zunächst die obige Matrix angepasst, indem alle unerwünschten Verknüpfungen bzw. nicht vorhanden Verknüpfungen (Hauptdiagonale) und alle deutlich abweichenden Kosten (hier: 180) mit $c_{ij} = \infty$ belegt werden:

Es ist außerdem sinnvoll eine Matrixreduktion vorzunehmen, bevor mit der vollständigen Enumeration begonnen werden kann. Hierzu wird das kleinste Element einer Zeile von allen anderen Elementen dieser Zeile subrahiert:

In der linken Zeile sind in den Klammern die kleinsten Elemente der Zeile aufgeführt (der Übersicht halber). Die Summe aller kleinsten Elemente ergibt dann die Reduktionskonstante:

Es kann nun mit dem Verfahren der vollständigen Enumeration begonnen werden (siehe folgenden Abschnitt).