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