Исследование решения задачи коммивояжера

Проведен обзор наиболее распространённых алгоритмов, используемых для решения задачи коммивояжёра: точных (алгоритм полного перебора, метод ветвей и границ), эвристических (метод включения дальнего, BV-метод); поисковых (генетический алгоритм, муравьиный алгоритм — ACS-Q). Сравнительный анализ алгоритмов относительно качества получаемых решений и их «быстродействия» показал: эвристические алгоритмы — бесспорные «лидеры» по быстродействию с хорошим соотношением качество/время; точные методы мало пригодны для решения задач больших размерностей (не способны решить задачу за разумное время); алгоритмы поиска являются компромиссом между эвристикой и точными методами, но требуют подбора параметров. Временные оценки, данные алгоритмам, позволяют оценить время решения задачи и выбрать наиболее подходящий метод, когда быстродействие является критичным параметром.
Библиогр. 4. Ил. 3.