3-опт
В оптимизации 3-opt — это простая эвристика локального поиска для поиска приближенных решений проблемы коммивояжера и связанных с ней задач оптимизации сети . По сравнению с более простым алгоритмом 2-opt он медленнее, но может генерировать решения более высокого качества.
Анализ 3-оптов предполагает удаление трех ребер из текущего решения задачи, создание трех подобходов. Существует восемь способов соединить эти подтуры обратно в один обход, один из которых состоит из трех удаленных ребер. Эти пересоединения анализируются для поиска оптимального. Затем этот процесс повторяется для другого набора из трех подключений, пока в сети не будут опробованы все возможные комбинации. Один проход через все тройки ребер имеет временную сложность . [1] Итерированный 3-opt, при котором проходы повторяются до тех пор, пока не будет найдено больше улучшений, имеет более высокую временную сложность.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Блазинскас, Андрюс; Мишевичюс, Альфонсас (2011). Объединение 2-OPT, 3-OPT и 4-OPT с возмущениями K-SWAP-KICK для задачи коммивояжера (PDF) . 17-я Международная конференция по информационным и программным технологиям . Каунас, Литва. S2CID 15324387 .
Дальнейшее чтение
[ редактировать ]- БОК, Ф. (1958). «Алгоритм решения коммивояжера и связанных с ним задач оптимизации сети». Исследование операций . 6 (6).
- Линь, Шен (1965). «Компьютерное решение задачи коммивояжера». Технический журнал Bell System . 44 (10). Институт инженеров по электротехнике и электронике (IEEE): 2245–2269. дои : 10.1002/j.1538-7305.1965.tb04146.x . ISSN 0005-8580 .
- Лин, С.; Керниган, BW (1973). «Эффективный эвристический алгоритм для задачи коммивояжера». Исследование операций . 21 (2). Институт исследования операций и наук управления (ИНФОРМС): 498–516. дои : 10.1287/опре.21.2.498 . ISSN 0030-364X .
- Сипсер, Майкл (2006). Введение в теорию вычислений . Бостон: Технология курса Томсона. ISBN 0-534-95097-3 . OCLC 58544333 .