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