Задача коммивояжёра

- общий метод для нахождения решений задач дискретной и комбинаторной оптимизации. Метод является алгоритмом перебора с отсевом подмножеств допустимых решений, не содержащих оптимальных решений. Опишем идею метода на примере поиска минимума функции f(x) на конечном множестве допустимых значений Ω. Метод ветвей и границ основан на трёх процедурах: ветвление, нахождение оценок (границ), отсев вариантов.
Ветвление состоит в разбиении по некоторому правилу A множества допустимых решений на подмножества
Процедура нахождения оценок заключается в поиске по некоторому правилу B нижних границ для минимальных значений функции f(x) на Пусть полученные нижние границы . Очевидно, .
Из полученных подмножеств выбираем подмножество Ωm, у которого
По правилу A разбиваем Ωm на подмножества
и вычисляем по правилу B нижние границы для минимальных значений функции f(x) на

.

Ωm1

Ωmp

Ωmk

. . .

γ

. . .

Ωmp1

Ωmph

Ωmpk

. . .

. . .

γ1

γm

γk

γm1

γmp

γmk

γmp1

γmph

γmpk

для задачи коммивояжёра. Правило ветвления состоит в разбиении множества рассматриваемых гамильтоновых циклов на два подмножества, одно из которых состоит из циклов, содержащих выбранную дугу e, а другое из циклов, не содержащих этой дуги. Дуга e выбирается среди дуг минимальной длины по условию, что запрет на использование этой дуги должен приводить к максимальному увеличению длины гамильтонова цикла. Правило вычисления нижних границ основано на процедуре приведения матриц расстояний, соответствующих вновь полученным висячим вершинам дерева поиска.
Опишем алгоритм Литтла.
Шаг 1. Приведение матрицы расстояний. Находим в каждой i-ой строке матрицы минимальный элемент αi и вычитаем его из всех элементов этой строки. В полученной матрице в каждом j-ом столбце находим минимальный элемент βj и вычитаем его из всех элементов данного столбца. После проделанных операций получим матрицу C’, каждая строка и каждый столбец которой содержит, по крайней мере, один нуль.
Шаг 2. Вычисляем сумму приводящих констант . Очевидно, что γ является нижней границей для всего множества решений , которое берется в качестве корня дерева поиска и текущего множества решений.
Шаг 3. Для каждого нулевого элемента c’ij = 0 матрицы C’ находим штраф за неиспользование (сумма минимальных элементов в строке и столбце, на пересечении которых стоит нуль, без учёта самого нулевого элемента).

.
Разбиваем текущее множество всех гамильтоновых циклов на два подмножества: Ω1 - “не включающие дугу (i,j)” и Ω2 – “включающие дугу (i,j)”. Присоединяем соответсвующие вершины к дереву поиска.
Шаг 5. Вычисляем нижнюю границу γ1 = γ + θij для гамильтоновых циклов подмножества Ω1. Строим соответсвующую Ω1 матрицу расстояний C’1. Для этого значение элемента c’ij заменяем на ∞ и приводим полученную матрицу (неприведенными могут быть только i-ая строка и j-ый столбец, поэтому сумма приводящих констант равна θij) .
Шаг 6. Вычисляем нижнюю границу для гамильтоновых циклов подмножества Ω2. Для этого удаляем из матрицы i-ю строку и j-й столбец, сохраняя исходную нумерацию для оставшихся строк и столбцов, и заменяем на ∞ значение элементов, соответствующих дугам, использование каждой из которых с уже включёнными в гамильтонов цикл дугами, приводит к образованию цикла с числом дуг меньше n. Приводим полученную матрицу, обозначаем её C’2 и добавляем сумму приводящих констант к нижней границе γ множества решений . Получаем нижнюю границу γ2 .
Шаг 7. Если в результате шага 6 получаем матрицу C’2 порядка два и её нижняя граница не превышает границ висячих вершин дерева поиска, то процесс заканчивается, решение найдено, переходим к шагу 11. В противном случае переходим к шагу 8.
Шаг 8. Среди висячих вершин построенного дерева поиска выбираем вершину с наименьшей границей (если таких вершин несколько, выбираем любую из них).
Шаг 9. Если выбранная на шаге 8 вершина соответствует свойству “включающие дугу (i,j)”, то соответствующую ей матрицу расстояний C’2, полученную на шаге 6, берём за С’ и переходим к шагу 3. В противном случае переходим к шагу 10.

соответствует свойству “не включающие дугу (i,j)”). Соответствующую ей матрицу расстояний C’1, полученную на шаге 5, берём за С’ и переходим к шагу 3.
Шаг 11. Строим гамильтонов цикл минимальной длины. Для этого включаем в гамильтонов цикл дуги соответствующие нулевым элементам 2x2-матрицы расстояний C’2 , полученной на шаге 7. Далее двигаемся от висячей вершины к корню дерева поиска по единственному обратному пути. При прохождении обратной дуги дерева поиска, соответствующей переходу от множества решений к его подмножеству по свойству “ включающие дугу (i,j)”, дугу (i,j) включаем в гамильтонов цикл.
Пример. Решить задачу коммивояжёра со следующей матрицей расстояний C

α5=1.
Приводим матрицу по столбцам: β1=0, β2=0, β3=0, β4=1, β5=0.
Текущая нижняя граница γ = 11 .
Находим штрафы для нулевых элементов: θ13 = 1 , θ21 = 0 , θ23 = 0 , θ32 = 3 , θ34 = 1 , θ45 = 4 ,
θ51 = 1 . Максимальный штраф θ45 = 4 .

Ω1 - “не включающие дугу (4,5)” и Ω2 - “включающие дугу (4,5)”. Для первого подмножества нижняя граница γ1 = 15, а соответствующую матрицу расстояний C’1 получим из матрицы C’ , положив c’45 = и приведя результат.
Для второго подмножества матрица расстояний C’2 получается из C’ удалением 4-ой строки и пятого столбца, причём для запрещения образования цикла 4->5->4 , полагаем c’54 = , полученный результат приводим.
Сумма приводящих констант равна 0, следовательно, γ2 = 11 .

вычисляем штрафы для нулевых элементов: θ13 = 1 , θ21 = 0 , θ23 = 0 , θ32 = 3 ,
θ34 = 1 , θ51 = 1 . Максимальный штраф θ32 = 3 . Разбиваем множество Ω2 на два подмножества Ω21 - “не включающие дугу (3,2)” и Ω22 - “включающие дугу (3,2)”. Для подмножества Ω21 нижняя граница γ21 = 14 . Матрицу расстояний C’21 получим из матрицы C’2 , положив c’32 = и проведя процедуру приведения.
Для подмножества Ω22 матрицу расстояний C’22 получаем из C’2 , удаляя третью строку и второй столбец, затем для запрещения образования цикла 3->2->3 , полагаем c’23= , полученный результат приводим.
Сумма приводящих констант равна 1, следовательно, γ22 = 12 .

Задача коммивояжёра Алгоритм Литтла

. Минимальную нижнюю границу имеет множество Ω22 . Поэтому в матрице C’22 вычисляем штрафы для нулевых элементов: θ13 = 1 , θ14 = 0 , θ21 = 0 , θ24 = 0 , θ51 = 1 . В результате сравнения мы получили два одинаковых максимальных штрафа равных 1.
Возьмём θ13 = 1 . Разбиваем множество Ω22 на два подмножества Ω221 - “не включающие дугу (1,3)” и Ω222 - “включающие дугу (1,3)”. Для подмножества Ω221 нижняя граница γ221 = 13 . Матрицу расстояний C’221 получим из матрицы C’22 , положив c’13 = и проведя процедуру приведения.
Для подмножества Ω222 матрицу расстояний C’222 получаем из C’22 , удаляя первую строку и третий столбец, затем для запрещения образования цикла 1->3->2->1 , полагаем c’21= , полученный результат приводим. Сумма приводящих констант равна 0, следовательно,
γ222 = 12.
В дереве поиска висячие вершины соответсвуют подмножествам Ω1, Ω21 , Ω221 , Ω222 . Минимальную нижнюю границу имеет множество Ω222 . Соответсвующая матрица C’222 имеет размерность 2x2. Следовательно, решение найдено.

Задача коммивояжёра Алгоритм Литтла