Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города ровно по одному разу с последующим возвратом в исходный город. Задача относится к классу NP-трудных задач, что означает, что для неё не существует алгоритма, который мог бы найти точное решение за полиномиальное время. Это делает её вычислительно сложной, поскольку время решения растет экспоненциально с увеличением числа городов...