Решение задачи о Коммивояжере методом ветвей и границ

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

    Первый  шаг. Фиксируем множество всех обходов  коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо непусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через G, то сумму констант приведения матрицы весов обозначим через j(G). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M1; таким образом, итог первого шага: множеству G всех обходов коммивояжера сопоставлено число j(G) и матрица M1.

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

    Сопоставим  множеству  следующую матрицу M1,1: в матрице M1 заменим на ¥ число в клетке . Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M1,1; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в дальнейшем через j( ), сопоставим множеству .

    Теперь  множеству  тоже сопоставим некую матрицу M1,2. Для этого в матрице M1 заменим на ¥ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j( ), сопоставим множеству .

    Теперь  выберем между множествами  и то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j( ) и j( ).

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

    К выбранному множеству с сопоставленными  ему матрицей и числом j повторим все то же самое и так далее, пока это возможно.

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

    После этого осуществляется улучшение  рекорда вплоть до получения окончательного ответа.

 

РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ  ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ

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

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

    Таблица 2

 

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

    Подсчитаем j(G) в нашем примере. Для этого выполним приведение матрицы весов; сначала - по строкам:

    Таблица 3

 

 

результат приведения по строкам:

    Таблица 4

 

    Определим константы приведения по столбцам:

    Таблица 5

 

результат приведения матрицы:

    Таблица 6

 

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

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

 

     Таблица 7