Глава 2. Способы решения

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

Точные методы.

Одним из точных методов решения данной задачи является метод полного перебора, иначе называемый перебор по всем перестановкам.

Этот метод заключается в переборе всевозможных перестановок и обхода вершин графа в порядке расположения номеров вершин в выбранной перестановке.

Рассмотрим пример кода для данного метода на Maple.

> with(combinat);

задаем количество городов

> N:=8; N1 := N - 1:

запоминаем все перестановки

> PermList:=permute(N1):

> readlib(randomize)():

> random:=rand(1..N*N):

создаем матрицу N*N

> CostMatrix:=matrix(N,N):

диагональные элементы матрицы (расстояние от города до него самого) заполняем значениями бесконечность

> for r from 1 to N do CostMatrix[r, r] := infinity od;

заполняем матрицу рандомными числами

> for r from 2 to N do

For c from 1 to r - 1 do

CostMatrix[r, c] := random();

CostMatrix[c, r] := CostMatrix[r, c] ;

od;

od;

выводим получившуюся матрицу

> evalm(CostMatrix);

минимальной стоимости присваиваем бесконечность

> MinCost := infinity;

для каждой перестановки считаем получившуюся стоимость обхода и, если она меньше минимальной стоимости, обновляем минимальную стоимость, и выводим на экран

> for r from 1 to nops(PermList) do

TourPermut:=PermList[r];

TourCost:=CostMatrix[TourPermut[N1], N] + CostMatrix[N, TourPermut[1]]:

For c from 1 to N - 2 do

TourCost:= TourCost+CostMatrix[TourPermut[c],TourPermut[c + 1]]

od:

if TourCost <= MinCost then

MinCost:= TourCost : lprint(`Tour->`, [op(TourPermut), N], `Cost=`, MinCost);

fi

od:

`Tour->`, [1, 2, 3, 4, 5, 6, 7, 8], `Cost=`, 312

`Tour->`, [1, 2, 3, 4, 5, 7, 6, 8], `Cost=`, 276

`Tour->`, [1, 2, 3, 4, 6, 5, 7, 8], `Cost=`, 269

`Tour->`, [1, 2, 3, 4, 6, 7, 5, 8], `Cost=`, 241

`Tour->`, [1, 2, 3, 5, 7, 4, 6, 8], `Cost=`, 213

`Tour->`, [1, 2, 3, 6, 4, 7, 5, 8], `Cost=`, 211

`Tour->`, [1, 5, 3, 2, 6, 4, 7, 8], `Cost=`, 208

`Tour->`, [1, 5, 3, 2, 6, 7, 4, 8], `Cost=`, 203

`Tour->`, [1, 5, 3, 2, 7, 4, 6, 8], `Cost=`, 200

`Tour->`, [1, 5, 7, 2, 3, 6, 4, 8], `Cost=`, 193

`Tour->`, [4, 6, 3, 2, 7, 5, 1, 8], `Cost=`, 193

выводим итоговую минимальную стоимость

> lprint(MinCost);

Данный алгоритм, несмотря на абсолютную точность вычислений, имеет огромный недостаток, заключающийся в том, что он оптимален только для маленькой размерности входных данных. Сложность этого алгоритма O(n!).

Так как данный алгоритм имеет достаточно большую сложность, он может использоваться для подсчета до 15 городов.

Вторым точным методом решения задачи коммивояжера является алгоритм Литтла, также известный, как метод ветвей и границ.

Общая идея этого метода: разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

Описание алгоритма Литтла.

1. В каждой сроке матрицы найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это и для столбцов не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержит хотя бы один нулевой элемент.

2. Для каждого нулевого элемента матрицы c_{i j}рассчитаем коэффициент Г_{i j}, который равен сумме минимального элемента строки i,исключая нулевой элемент c_ij, и наименьшего элемента столбца j. Из всех коэффициентов Г_{i j} выберем максимальный (Г_{k l} =max(Г_{i j})). В Гамильтонов контур вносится соответствующая дуга (k,l).

3. Удаляем k-ю строку и l-ый столбец и меняем значение элемента c_{l k} на бесконечность, так как обратный путь недопустим.

4. Повторяем предыдущие шаги, пока порядок матрицы не станет равным двум.

5. Затем в текущий ориентированный граф вносим две недостающие дуги, определяющиеся однозначно матрицей порядка 2. Получаем Гамильтонов контур.

Сложность алгоритма Литтла O(n²cⁿ),где c-некоторая константа. Так же, как и метод перебора, этот метод решает задачу только для небольшого количества городов(около 30).

На сегодняшний день существует достаточно много хороших методов, позволяющих решать задачу точно, но они слишком громосткие.