Алгоритм мульти-фрагмент (MF) является эвристическим или приближение алгоритма для задачи коммивояжера (TSP) (и связанные с этим проблемы). Этот алгоритм также иногда называют «жадным алгоритмом» для TSP.
Класс | Алгоритм приближения |
---|---|
Структура данных | График |
Наихудшая производительность |
Алгоритм строит тур для коммивояжера по одному ребру за раз и, таким образом, поддерживает несколько фрагментов тура, каждый из которых представляет собой простой путь в полном графе городов. На каждом этапе алгоритм выбирает край минимальной стоимости, который либо создает новый фрагмент, либо расширяет один из существующих путей, либо создает цикл длиной, равной количеству городов. [1]
Рекомендации
- ^ Джонсон, Дэвид; А. МакГеоч, Лайл (1997). «Проблема коммивояжера: пример локальной оптимизации». Локальный поиск в комбинаторной оптимизации . 1 . CiteSeerX 10.1.1.92.1635 .