Многофрагментный алгоритм - Multi-fragment algorithm

Многофрагментный алгоритм

Класс	Алгоритм приближения
Структура данных	График
Пессимистический производительность	${\ Displaystyle \ Theta (N ^ {2} \ log N)}$

Алгоритм мульти-фрагмент (MF) является эвристическим или приближение алгоритма для задачи коммивояжера (TSP) (и связанные с этим проблемы). Этот алгоритм также иногда называют «жадным алгоритмом» для TSP.

Алгоритм строит тур для коммивояжера по одному ребру за раз и, таким образом, поддерживает несколько фрагментов тура, каждый из которых представляет собой простой путь в полном графе городов. На каждом этапе алгоритм выбирает край минимальной стоимости, который либо создает новый фрагмент, либо расширяет один из существующих путей, либо создает цикл длины, равной количеству городов.

Ссылки

Эта статья, посвященная алгоритмам или структурам данных, является незавершенной . Вы можете помочь Википедии, расширив ее . v т е