Задание 3. Задача о коммивояжёре

Постановка задачи.

Коммивояжёр (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3..n и вернуться в первый город. Стоимости проезда между городами известны. В каком порядке следует объезжать города, чтобы замкнутый путь (тур) коммивояжера был наименее затратным?

Сформулируем задачу в терминах теории графов, введя следующие обозначения: пусть D =[ V, X ] – полный ориентированный граф и f: X ® - весовая функция, V= { v₁, v₂,…, v_n } – множество вершин, X – множество дуг, C= { c_ij }, i, j =1,2… n – весовая матрица данного ориентированного графа, то есть с_ij = f (v_i,v_j), причем для любого i справедливо c_ii =¥. Требуется найти простой остовной ориентированный цикл (или «цикл коммивояжёра») минимального веса.

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

Очевидно, c_ij следует трактовать как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру $5. Это означает, что любой тур подешевеет на $5, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j -го столбца матрицы M на 5. Если бы мэр хотел спровадить коммивояжеров из j -го города и установил награду за выезд в размере $10, это можно было бы выразить вычитанием 10 из всех элементов j -й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

Вычитая любую константу из всех элементов любой строки или столбца матрицы C, мы оставляем минимальный тур минимальным.

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

Привести матрицу по строкам означает, что все строки приводятся. Аналогичный смысл имеют слова «привести матрицу по столбцам ». Приведение матрицы означает сначала приведение этой матрицы по строкам, а затем по столбцам.

Если с помощью приведённой матрицы удастся построить такую последовательность переходов по городам (по вершинам графа), которым соответствует последовательность нулевых элементов приведенной матрицы, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной весовой матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет прибавить все константы приведения. Таким образом, сумма констант приведения играет роль оценки снизу для стоимости всех туров.

Весом элемента матрицы называют сумму констант приведения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на ¥. Следовательно, слова «самый тяжёлый нуль в матрице » означают, что в матрице подсчитан вес каждого нулевого элемента, а затем фиксирован нуль с максимальным весом.

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

Пример3

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

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

Обозначим за Г множество всех обходов коммивояжера (т. е. всех простых ориентированных остовных циклов). Поскольку граф – полный, это множество заведомо не пусто. Сопоставим ему число j(Г), которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов дуг графа и является оценкой снизу для стоимости минимального тура коммивояжёра. Приведённую матрицу весов данного графа следует запомнить, обозначим ее через С ₁.

Подсчитаем j(Г). Для этого выполним приведение матрицы весов.

Сначала – по строкам:

1 2 3 4 5     1 ¥           min в первой строке 2   ¥         min во второй строке 3     ¥       min в третьей строке 4       ¥     min в четвёртой строке 5         ¥   min в пятой строке

1 2 3 4 5 1 ¥         2   ¥       3     ¥     4       ¥   5         ¥

Теперь − по столбцам:

1 2 3 4 5 1 ¥         2   ¥       3     ¥     4       ¥   5         ¥               ↑ min в первом столбце ↑ min во втором столбце ↑ min в третьем столбце ↑ min в четвёртом столбце ↑ min в пятом столбце

1 2 3 4 5 1 ¥         2   ¥       3     ¥     4       ¥   5         ¥   Матрица C 1

Сумма констант приведения j(Г)=4+4+2+1+2+1=14.

Обозначим полученную матрицу через С ₁ и найдём в ней самый тяжёлый нуль. Заметим, что замена нулевого элемента на ¥ приводит к изменению лишь двух слагаемых суммы констант приведения j(Г) – по одному при приведении строк и столбцов. Поэтому вес нуля можно определить суммированием наименьших элементов его строки и столбца. Вообще нуль в клетке (i, j) приведённой матрицы означает, что цена перехода из города i в город j равна 0. А если мы не пойдём из города i в город j? Тогда все равно нужно въехать в город j за минимальную цену, указанные в j -том столбце; и все равно надо будет выехать из города i за минимальную цену, указанную в i -той строке. А это и есть оценка нуля. Например, вес нуля в первой строке и четвёртом столбце складывается из минимума по первой строке, равного 4 (c _1,2= c _1,3=4), и минимума по четвёртому столбцу, равного 0 (c _5,4=0), без учета самого c _1,4.

Итак, запишем приведённую матрицу еще раз, указывая рядом с каждым нулем его вес:

Самым тяжёлым оказывается нуль в клетке (1,4).

Разобьём множество Г на две части: множество (все циклы, проходящие через дугу (1,4)) и (все циклы, не проходящие через дугу (1,4)). Такое ветвление определяет необходимость выбора одного из этих вариантов. Множеству соответствует матрица С _1,1, полученная вычёркиванием соответствующих строки (строку 1) и столбца (столбец 4). У оставшихся строк и столбцов сохраним их исходные номера. Разумеется, вместе с вычёркиванием строки и столбца, в матрице надо заменить на ¥ числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). В данном случае из города 4 мы уже не можем проехать в город 1, поэтому в клетке (1,4) ставим знак ¥.

Сумма констант приведения матрицы С _1,1 здесь равна 1, поэтому j(Г_{(1,4)})=j_{1,4}=14+1=15. Сопоставим результат j(Г_{{( i , j)}}) множеству Г_{{( i , j)}}, (в нашем случае Г_{(1,4)}).

Множеству (в нашем случае ), в свою очередь, соответствует другая матрица – С _1,2, полученная заменой на ¥ элемент с _1,4 в матрице С ₁:

Сумма констант последнего приведения равна 4, так что Теперь выберем между множествами и то, на котором минимальна функция j. В нашем случае из множеств, которому соответствует меньшее из чисел j(Г_{(1,4)})=15 и . Поэтому дальнейшей разработке подвергнется множество Г_{(1,4)}.

Итак, выделена определенная дуга (1,4) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдёт в искомый гамильтонов цикл (цикл коммивояжёра), если данная ветвь будет продолжена до конца и иметь минимальный вес.

В матрице С _1,1 подсчитаем веса нулей (веса нулей указаны в скобках):

Самым тяжёлым является нуль с номером (4,3), так что теперь следует рассматривать множества и .

Обратимся к первому из них. Поскольку, вычеркнув строку 4 и столбец 3 в матрице С _1,1, нужно также заменить на ¥ числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n), то в клетке с номером (3,1) надо поставить символ ¥. Получим матрицу С _1,1,1:

Для оценочной функции .

Матрица С _1,1,2 для множества :

Оценочная функция . Следовательно, дальнейшей разработке подлежит . «Взвешиваем» нули в матрице С _1,1,1:

Поскольку все нули имеют одинаковый вес, выберем любой из них; для определённости – нуль, стоящий в клетке (2,1).

Теперь речь пойдёт о множествах и .

Как и раньше, вычёркивая строку 2 и столбец 1 в матрице С _1,1,1, нужно также заменить на ¥ числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). Так в клетке с номером (3,2) окажется символ ¥.

Получаем для оценочной функции .

Для множества матрица такова:

Для оценочной функции .

Получилось, что для дальнейшей разработки можно брать любое из множеств и . Но в первом случае уже получена матрица размером 2´2. Её нулевые клетки дают те дуги, которые с найденными ранее составляют обход коммивояжёра, причём вес этого обхода равен значению оценочной функции – 18. Вот этот обход:

(1,4)(4,3) (3,5) (5,2) (2,1) или 1®4®3®5®2®1

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