Algorytm wielofragmentowy

Algorytm wielofragmentowy

Klasa	Algorytm aproksymacji
Struktura danych	Wykres
Wydajność w najgorszym przypadku	${\ Displaystyle \ Theta (N ^ {2} \ log N)}$

Algorytm wielofragmentowy (MF) to algorytm heurystyczny lub aproksymacyjny dla problemu komiwojażera (TSP) (i problemów pokrewnych). Algorytm ten jest czasami nazywany „algorytmem zachłannym” dla TSP.

Algorytm buduje trasę dla komiwojażera po jednej krawędzi na raz, a tym samym utrzymuje wiele fragmentów trasy, z których każdy jest prostą ścieżką na pełnym grafie miast. Na każdym etapie algorytm wybiera krawędź o minimalnym koszcie, która tworzy nowy fragment, przedłuża jedną z istniejących ścieżek lub tworzy cykl o długości równej liczbie miast.