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