Verfahren des besten Nachfolgers (reduzierte Matrix)

Das Verfahren soll außerdem anhand der reduzierten Kostenmatrix betrachtet werden. Hierbei wird zunächst eine Zeilenreduktion vorgenommen, wobei das kleinste Element der Zeile von den anderen Elementen der Zeile subtrahiert wird:

Danach wird eine Spaltenreduktion vorgenommen, indem der kleinste Wert der Spalte von allen anderen Elementen der Spalte subtrahiert wird. Dies ist nur für die letzte Spalte möglich, da die anderen Spalten als kleinsten Wert Null besitzen:

Die Reduktionskonstante ist:

Für die reduzierte Kostenmatrix wird das Verfahren erneut angewendet. Diesmal ergeben sich aber aufgrund der teilweise gleichen Kosten mehrere Nachfolger, die ebenfalls untersucht werden müssen. Hierzu wird ein Graph verwendet, um das Verfahren übersichtlicher darzustellen:

In der obigen Grafik ist nun das Verfahren des besten Nachfolgers anhand der reduzierten Kostenmatrix mit der Reduktionskonstante $k_R = 164$ dargestellt. Die Kosten sind kumuliert dargestellt.

Es ergibt sich die folgende Reihenfolge:

Die Gesamtkosten ergeben sich zu:

Das bedeteut eine Abweichung zur optimalen Lösung von 2 GE.

Mittels der reduzierten Kostenmatrix ist zwar nicht das optimale Ergebnis gefunden worden, aber das Ergebnis ist in jedem Fall besser als ohne Reduktion der Matrix. Deswegen sollte in jedem Fall eine Matrixreduktion (zeilen- und spaltenweise) vorgenommen werden.