Задача коммивояжера (ЗК) является NP сложной задачей дискретной оптимизации и определяется следующим образом: для заданного полного взвешенного графа G = (V, E, D) с множеством вершин V = {vi}n, множеством ребер E и матрицей весов D = {di,j}nxn необходимо найти Гамильтонов цикл (vi1, vi2,…,vin), где (i1,…,in) — перестановка на множестве {1,2,…,n}, а viV, с минимальной суммой весов дуг [1] Вершины графа G часто называются городами, а любой Гамильтонов цикл называется маршрутом коммивояжера. Очевидным решением задачи является метод полного перебора. Выйдя из первого города, коммивояжер может направиться в один из (n – 1) городов, откуда в (n – 2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число маршрутов, подлежащих просмотру, составляет (n – 1) · (n – 2) … 2 · 1 = (n – 1) всевозможных вариантов. С увеличением количества городов это значение быстро возрастает и уже при 15 городах достигает астрономических цифр. Поиск точных и приближенных способов решения задачи о коммивояжере остается актуальным и с теоретической, и с практической точки зрения, так как не найдено, а возможно, и не существует точных алгоритмов, решающих ЗК за короткое (полиномиальное) время. Поэтому для решения задачи коммивояжера эффективнее использовать не точные, а эвристические методы. Применение эвристических алгоритмов к какой-либо практической задаче обычно позволяет сформулировать рекомендации, которые намного лучше произвольного решения и которые наиболее близки к лучшему варианту.