Das Verfahren des besten Nachfolgers gehört zu den heuristischen Verfahren der kombinatorischen Optimierung. In diesem Abschnitt soll gezeigt werden, wie man dieses Verfahren auf ein Traveling-Salesman-Problem anwendet.
Methode
Vorgehensweise: Verfahren des besten Nachfolgers
Ausgehend von einem Knoten $i$ (einem Ort) wird derjenige Ort als Nachfolger $j$ gewählt, welcher die geringsten Kosten bzw. die geringste Zeit aufweist $\min[c_{ij}]$. Dieser Ort wird dann als Nachfolger von Ort $i$ eingetragen. Danach wird der Nachfolger betrachtet und auch für diesen wieder der Ort als Nachfolger gewählt, welcher die geringsten Kosten bzw. Zeit aufweist. Dieser Vorgang wird solange wiederholt, bis alle Orte einbezogen sind. Danach wird wieder der Ausgangsort angesteuert.
Im Folgenden soll das Verfahren des besten Nachfolgers anhand des Beispiels aus dem Abschnitt Vollständige Enumeration anhand der Ausgangsmatrix und anhand der reduzierten Kostenmatrix durchgeführt werden.
Weitere interessante Inhalte zum Thema
-
Verfahren des besten Nachfolgers (reduzierte Matrix)
Vielleicht ist für Sie auch das Thema Verfahren des besten Nachfolgers (reduzierte Matrix) (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Einbeziehung von Stationen (Ausgangsmatrix)
Vielleicht ist für Sie auch das Thema Einbeziehung von Stationen (Ausgangsmatrix) (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
