Постановка задачи.
Коммивояжер (К) должен обойти N городов и вернуться в исходный город. Пронумеруем эти города 1,2….N. Известна матрица расстояний L=(lij)NN так как К из города i переходит в другой город j, то lij не существует. Если из города i нельзя переход в j то расстояние lij=?. В общем случае lij? lji. Будем предполагать что К находится в 1 городе. Он должен побывать в каждом из последующих городов один раз и вернуться в исходный город. Необходимо определить в какой последовательности К должен посещать все города, чтобы его суммарно пройденный путь имел минимальную длину.
Изобразим города в виде точек на плоскости а расстояние между городами в виде дуг. Получим полный ориентированный граф. Путь К на этом графе представляет собой гамильтоновой контур.
Задача заключается в том, чтобы из всех гамильтоновых контуров выбрать контур с наименьшей длиной. Если решать задачу методом перебора то задача К с N городами имеет (N-1)!.
Математическая модель задачи
Поставим в соответствие каждой дуге графа (i,j) переменную хij, (1) хij=(1, если из города i К следует в j; 0, если иначе), так как в каждом городе должен побывать 1 раз, то он 1 раз въезжает в любой город j и 1 раз выезжает из любого города.
Условие, что К 1 раз выезжает в любой город j изображается схематически: (2) ?хij=1, j=1,N i?j.
Аналогично, записывается условие что К 1 раз выезжает из любого города i: (3) ? хij=1, i=1,N i?j
Условий (1) (2) (3) недостаточно для образования пути К.
(4) Ui-Uj+Nxij?N-1 i,j=1,N. Это условие показывает на каком шаге К посещает i и j.
Длина пути К: (5) Z=??lijxij?min
Определение множества решений D(1) в задаче К
Решением задачи К является путь К или гамильтонов контур графа с N вершинами => D(1) множество всевозможных путей К или множество гамильтоновых контуров графа. необходимо найти нижнюю границу, оценку длины любого пути К то есть ?( D(1))
Нахождение ?( D(1)) Теорема 1 и 2
Теорема 1: длина любого пути К не меньше суммы приведенных констант соответствующей матрицы расстояний L.
Доказательство: пусть К должен посетить N городов, задана матрица L=(lij)NN – расстояний между городами.
Рассмотрим любой путь К f=(i1,i2…..iN,i1), где i1,i2…..iN,i1 некоторая перестановка из чисел 1,2….N.
В самом начале пути К находится в некотором городе i1. Длина этого пути l=li1,i2+li2,i3+liN,i1 (6).
В любой i-ой строке матрицы расстояний L найдем наименьший элемент и обозначим его hi, то есть hi=min lij, i=1,N — где hi приведенная константа i-ой строки матрицы L. Из элементов каждой i-ой строки вычитаем соответствующую приведенную константу hi,то есть вычисляем значение lij’=lij- hi,i,j=1,N i?j (7).
Получим L’, lij’?0. Из (7) lij = lij’ + hi. Подставим эти значения в (6) получим l=li1,i2’+li2,i3’+liN,i1’+? hi (8). В каждом j-ом столбце матрицы L’ найдем наименьшее значение Hj=min lij’, Hj – приведенная константа столбца j. Из элементов каждого j-ого столбца вычитаем соответствующее значение Hj, lij’’=lij’- Hj (9).
Получим матрицу L’’= (lij’’)NN, lij’’?0. Из (9) найдем lij’= lij’’ + Hj и подставим в (8). l= li1,i2’’+li2,i3’’+liN,i1’’+? hi+? Hj (10), l?? hi+? Hj, l — длина пути, т.е. l не меньше суммы приведенных констант матрицы L. =>?(D(1))? ? hi+? Hj

Теорема 2: оптимальный путь (оптимальное решение) Задачи К с матрицей L совпадает с оптимальным путем задачи К с матрицей L’’. Длина пути в задаче с матрицей L больше длины соответствующего пути в задаче с матрицей L’’ на сумму приведенных констант.
Процесс перехода от L?L’ ?L’’ называется приведением матрицы L,а L’’ приведенной матрицей
Процесс разбиения (ветвления) множества D(1).
Будем искать оптимальный путь в задаче с матрицей L’’. Наиболее вероятно, что в кратчайший путь К войдут те дуги (i,j) для которых в L’’ lij’’=0. Среди этих дуг необходимо найти ту исключение которой из пути приведет к большему увеличению ?(D(1)) => такую дугу на данном этапе исключать нецелесообразно. Эта дуга называется наиболее перспективной. Чтобы найти ее рассмотрим поочередно нулевые элементы матрицы L’’ и для lij’’=0 в i-ой строке и j-ом столбце находим наименьшие элементы (исключая элемент lij’’=0), складываем их. Их сумму обозначим ?. Среди всех ?ij найдем max ?kr=max?ij – наиболее перспективной является дуга (k,r), множество D(1)1 – множество путей К которые не содержат дугу (k,r). Условно обозначаем D(1)1-(k,r). D(1)2 — множество путей К которые содержат дугу (k,r). Условно обозначаем (k,r).
Необходимо определить матрицу расстояний подмножества D(1)1 обозначим L(k,r), для D(1)2 L(k,r).