§ 3. Алгоритм Литтла, Мурти, Суини и Кэрел для задачи коммивояжера

3.1. Как и при изложении метода Лэнд и Дойг, не будем воспроизводить общей схемы метода ветвей и границ, а изложим лишь особенности данного алгоритма.

Задача коммивояжера была описана выше (§ 3 гл. 2). Напомним ее первоначальную постановку. Имеется городов Задана матрица расстояний между ними (считаем, что все разумеется, Матрица расстояний не предполагается симметричной; иначе говоря, возможен случай

Ищется кратчайший замкнутый маршрут, (цикл), проходящий через каждый город ровно по одному разу и минимизирующий суммарное пройденное расстояние

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

3.2 Конкретизируем теперь отдельные этапы общей схемы метода ветвей и границ.

1°. Задание множества Множество состоит из всех циклов.

2°. Задание множеств Каждое из множеств состоит из всех циклов, подчиненных дополнительным условиям следующих двух типов:

1) из следует идти непосредственно в для всех упорядоченных пар входящих в некоторое множество

2) из запрещается идти непосредственно в для всех упорядоченных пар входящих в некоторое множество

3°. Вычисление оценки для Приведение. Рассмотрим некоторый цикл Пройденное по нему расстояние равно

Пусть

Тогда

и

Далее, пусть

Тогда

и

Из (3.2), (3.3) и (3.4) получаем

и полагаем

Заметим, что

Описанное выше преобразование, позволяющее получить из исходной неотрицательной матрицы

новую неотрицательную матрицу называется приведением, а сумма

— суммой приводящих констант.

Отметим, что матрица и оценка однозначно соответствуют матрице С. При этом имеет место следующая простая теорема.

Теорема 1.1. Оптимальный план задачи коммивояжера с матрицей является также оптимальным планом и для задачи коммивояжера с матрицей С. Длина пути соответствующего матрице С, и длина пути соответствующего матрице связаны соотношением

Доказательство непосредственно следует из (3.4) и (3.5). Отметим, что в каждой строке и в каждом столбце матрицы содержится по крайней мере по одному нулю. Любую неотрицательную квадратную матрицу, обладающую указанным свойством, будем называть приведенной. Легко видеть, что процесс приведения, примененный к приведенной матрице, даст ту же самую матрицу; сумма приводящих констант при этом будет равна нулю.

Каждой вершине дерева, которое строится в процессе решения, будет соответствовать своя оценка и своя приведенная матрица

4°. Разбиение на подмножества (ветвление). Множество при ветвлении разбивается ров но на два подмножества. По некоторому способу (указанному ниже) выбирается пара городов не входящая в множества после чего производится ветвление:

Здесь получается из добавлением условия: «из обязательно идти непосредственно в

получается из добавлением условия: запрещается идти непосредственно в Более формально,

Выбор пары при ветвлении основан на следующих соображениях. Постараемся действовать таким образом, чтобы «с наибольшей вероятностью» содержало оптимальный цикл, его не содержало. Естественно для этого выбирать так, чтобы Здесь через обозначен элемент приведенной матрицы (отвечающей множеству стоящий в строке и столбце Тогда есть основание ожидать, что входящим в циклам будет соответствовать малая длина пути.

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

Остается выбрать так, чтобы было наибольшим, т. е.

где максимум берется по всем парам для которых

5°. Вычисление планов (циклов). Если множество состоит ровно из элементов, то тем самым уже задан цикл, элемент которого определен

однозначно. В этом случае оценка совпадает с длиной единственного цикла, входящего в

6°. Преобразование матрицы расстояний при ветвлении. Пересчет оценок. Рассмотрим разветвление

описанное в п. 4°.

а) Рассмотрим сначала множество и укажем правило перехода от матрицы к матрице Матрица содержит те же строки и столбцы, что и Положим

Применяя к матрице описанную выше процедуру приведения, получаем матрицу

При этом сумма приводящих констант равна так что оценкой для будет

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

Далее следует проверить, не состоит ли ровно из одного цикла. Если это так, то следует применить к матрице процесс приведения и, получив сумму приводящих констант А, пересчитать оценку

При этом окажется, что в точности равно длине этого единственного цикла. Если же не состоит в точности из одного цикла, то следует запретить

возможность возникновения подциклов (т. е. замкнутых маршрутов, содержащих меньше чем городов); эта возможность теперь появляется из-за добавления непосредственного перехода Для этого следует найти все такие маршруты, включающие в себя звено возможно, другие элементы множества Обозначим множество таких маршрутов через

Процесс запрещения упомянутых маршрутов (подциклов) связан с переходом от матрицы до, к матрице (включающей те же строки и столбцы). Прежде всего, в входит маршрут Запрещаем его, полагая Далее, если из элементов можно составить маршрут то в 1 входят маршруты вида

Запрещаем все эти маршруты, полагая Если из элементов можно составить маршрут то в входят маршруты вида Запрещаем все эти маршруты, полагая Для всех остальных элементов матрицы полагаем

Теперь следует применить к матрице процесс приведения и, найдя сумму приводящих констант А, пересчитать оценку по прежнему правилу:

3.3. Конечность алгоритма Литтла, Мурти, Суини и Кэрел непосредственно следует из конечности числа всех циклов в рассматриваемой задаче.

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

3.5. Авторы алгоритма в статье освещают также и накопленный ими вычислительный опыт. Экспериментирование велось на машине IBM-7090. При этом задачи с несимметричными матрицами с числом городов до 20 решались за несколько секунд; при увеличении числа городов время счета возрастало весьма быстро (грубо говоря, добавление 10 городов увеличивало время примерно в 10 раз). Среднее (по 100 решенным задачам) время счета для несимметричной задачи с 30 городами составляло около 1 мин.

Задачи с симметричными матрицами обычно считались заметно дольше по сравнению с несимметричными задачами тех же размеров. Например, решение задачи с 25 городами потребовало 4,7 мин. машинного времени.