32. Задача коммивояжера и ее решение методом ветвей и границ

 

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

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

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

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

                Дано: матрица С, каждый элемент которой сij равен стоимости (обычно в единицах времени, денег или расстояния) прямого проезда из города i в город  j. Задача наз. симметричной, если сij=сji для всех i и j, т.е. если стоимость проезда между каждыми двумя городами не зависит от направления. Чтобы решать задачу методом ветвей и границ, необходимо положить сii= бескон. для всех i.

                Пример*. Задача о деревенском почтальоне

                Почта расположена в деревне 1. Почтальон, выйдя из этой деревни, должен разнести корреспонденцию жителям деревней 2, 3, 4 и вернуться обратно. Под стоимостью ребра будем понимать количество километров, которые почтальон вынужден пройти пешком. Из всех замкнутых маршрутов надо выбрать такой, в котором пройденное пешком расстояние минимально. Автобусные маршруты соединяют деревни 1 и 3, а также деревни 2 и 4. Поскольку автобусы ходят всего 2 раза в сутки, то почтальону удобно  из 1 в 3 добраться автобусом, а обратно проще идти пешком, аналогично: из 4 в 2 - автобусом, а обратно - пешком. Отсюда - несимметричность задачи

Таблица стоимостей

для несимметричной задачи

 

1

2

3

4

1

бескон.

5

0

2

2

5

бескон.

1

6

3

8

1

бескон.

9

4

2

0

9

бескон.

 

 

                Рис.

 

               

Ветвление

 

               

 

 

 

Корень поискового дерева будет соответствовать множеству “всех возможных туров”, т.е. эта вершина представляет множество R всех 3! возможных туров в задаче с четырьмя населенными пунктами. Ветви, выходящие из корня, определяются выбором одного ребра, например, (i, j). Это ребро разделяет R на два множества Rij и неRij . В множество Rij входят циклы из R, содержащие ребро  (i, j), а в неRij - циклы, не содержащие (i, j).

                В нашем примере будем производить ветвление по ребру (1,3), имеющем наименьшую стоимость во всей матрице. Затем разделяем множество R1,3. Такое же по дешевизне ребро в матрице - это ребро (4,2). Поэтому можно разделить множество R3,5 на множество циклов R4,2, включающих ребро (4,2), и множество циклов неR4,2, это ребро не включающих. Заметим, что оптимальный ГЦ вовсе не обязательно будет содержать два самых коротких ребра, т.е. попадет в множество R4,2. Легко убедиться, что в нашем примере ГЦ (1-3-2-4-1) с минимальной стоимостью 9 принадлежит множеству неR4,2.

                Корень и первые два уровня дерева решений представлены на рис. Корню соответствует множество R, включающее все варианты:

R={1-2-3-4-1, 1-2-4-3-1, 1-3-2-4-1, 1-3-4-2-1, 1-4-2-3-1, 1-4-3-2-1},

остальным показанным на рис. вершинам соответствуют множества

R1,3={1-3-2-4-1, 1-3-4-2-1}, неR1,3={1-3-2-4-1, 1-3-4-2-1}, неR4,2={1-3-4-2-1}, R4,2={1-3-2-4-1}.

 

                Вообще, если Х - вершина дерева, а (i, j) - ребро ветвления, то обозначим вершины, непосредственно следующие за Х, через Y и неY. Множество Y обозначает подмножество циклов из Х с ребром (i, j), а множество неY - подмножество Х без ребра (i, j).

 

                Во-вторых, поясним, что подразумевается под вычислением границ.

                С каждой вершиной дерева мы связываем нижнюю границу стоимости цикла из множества, представленного вершиной (нижняя граница w вершины v характеризуется тем, что стоимость ГЦ, проходящего через эту вершину, не может оказаться меньше, чем w). Вычисление этих нижних границ - основной фактор, дающий экономию усилий в любом алгоритме типа ветвей и границ. Предположим, что, двигаясь по одной из веток дерева решений, мы уже нашли цикл со стоимостью m. Тогда в другой ветке, попав в вершину с нижней границей M³m, мы уже не будем рассматривать эту вершину и все следующие за ней. Основной шаг при вычислении нижних границ известен как приведение. Оно основано на следующих соображениях:

                1. В связи с тем, что каждый город нужно посетить ровно один раз, каждый гамильтонов цикл (ГЦ) содержит только один элемент из каждого столбца и каждой строки матрицы C. Заметим, что обратное утверждение не всегда верно. Например, множество {(1,4),(4,1),(2,3),(3,2)} не образует ГЦ.

                2. Если вычесть константу h из каждого элемента какой-то строки или столбца матрицы C, то стоимость любого ГЦ при новой матрице C’ ровно на h меньше стоимости того же ГЦ при матрице C. Поскольку любой ГЦ должен содержать ребро из данной строки или данного столбца, стоимость всех ГЦ уменьшается на h. Это вычитание наз. приведением строки (или столбца).

                Пусть t - оптимальный ГЦ при матрице стоимостей C. Тогда его стоимость равна

.

                Если C’ получается из C приведением строки (или столбца), то t должен остаться оптимальным ГЦ при C’ и

,

где z(t) - стоимость ГЦ t при C’.

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

                За h примем сумму всех вычтенных элементов. Полученную в результате матрицу стоимостей наз. приведенной из С.

Пример.                С                                                             -2         -0        -0          -2                                                                           С

 

1

2

3

4

 

 

1

2

3

4

 

 

1

2

3

4

1

бескон.

5

0

2

-0

1

бескон.

5

0

2

 

1

бескон.

5

0

0

2

5

бескон.

1

6

-1

2

4

бескон.

0

5

 

2

2

бескон.

0

3

3

8

1

бескон.

9

-1

3

7

0

бескон.

8

 

3

5

0

бескон.

6

4

2

0

9

бескон.

-0

4

2

0

9

бескон.

 

4

0

0

9

бескон.

                Общее приведение составляет 2+4=6 единиц. Следовательно, нижняя граница стоимости любого ГЦ из R также равна 6, т.е. >= h=6. Укажем эту границу около корня дерева.

                Рассмотрим нижние границы для вершин уровня 1, т.е. для множеств R1,3 и неR1,3. Будем работать с приведенной матрицей (не забывая про 6, которые надо будет добавить к стоимости оптимального ГЦ при С).

множество R1,3

                Ребро (1,3)Î R1,3; поэтому исключаем из дальнейшего рассмотрения строку 1 и столбец 3 (из них уже взято по элементу). Кроме того, ребро (3,1) НЕ_ПРИНАДЛЕЖИТ R1,3 (иначе возникнет “короткий” цикл); поэтому исключаем (3,1) из рассмотрения, положив с3,1= бескон.. Остается часть приведенной матрицы стоимостей, представленная в таблице а. Опять выполняем процедуру приведения, получаем матрицу стоимостей, представленную в таблице б (на этом шаге h=3+12=15).

 

               Таблица а                                             -0            -0            -1                                                        Таблица б

 

1

2

4

 

 

1

2

4

 

 

1

2

4

2

2

бескон.

3

-2

2

0

бескон.

1

 

2

0

бескон.

0

3

5

0

6

-0

3

5

0

6

 

3

5

0

5

4

0

0

бескон.

-0

4

0

0

бескон.

 

4

0

0

бескон.

                Нижняя граница для множества R1,3 складывается из обоих h: 6+3=9.

 

множество  неR1,3

                Займемся нижней границей для множества неR1,3. Ребро (1,3) НЕ_СОДЕРЖИТСЯ В неR1,3 (иначе “короткий” цикл); поэтому исключаем (1,3) из рассмотрения, положив с1,3= БЕСКОНЕЧНОСТИ. В любой ГЦ из этого множества будет входить какое-то ребро из города 1 и какое-то ребро к городу 3. Самое дешевое ребро из города 1, исключая (1,3), имеет стоимость 0 (ребро (1,4)), самое дешевое ребро к городу 3 тоже имеет стоимость 0 (ребро (2,3)),. Следовательно, нижняя граница для множества неR1,3 составит 6+0+0=6.

                На данной стадии нам удалось сократить размер матрицы стоимостей, рассматриваемой в вершине R1,3. Кроме того, если нам удастся найти ГЦ из неR1,3 со стоимостью, не превышающей 9, то не придется проводить дальнейшие ветвление и вычисление границ в вершине R1,3. В этом случае принято говорить, что вершина R1,3 в дереве отработана.

 

 

 

Блок-схема алгоритма ветвей и границ

 

                Символ z0 обозначает стоимость самого дешевого ГЦ, известного на данный момент. Вначале полагаем z0=БЕСКОНЕЧНОСТИ.

                1. Инициализация переменных, считывание данных

                2. Приведение матрицы С. Установка корня, X=R

                3. Выбор ребра (k,l) для следующего ветвления

                4. Процесс ветвления. Установка вершины неY и вычисление ее нижней границы w(неY)

                5. Процесс ветвления. Установка вершины Y и вычисление ее нижней границы w(Y)

                6. Проверка условия: достаточно ли мала матрица стоимостей С?

                               если “нет”, то перейти к 9

                7. Проведение исчерпывающей оценки для Y

                8. Если w(Y)<z0, полагаем z0=w(Y), ГЦ запоминаем

                9. Выбор следующей вершины Х

                10. Проверка условия: z0<=w(Х)?

                               если “да”, то остановка.

                11. Корректировка матрицы С для текущей вершины Х и переход к 3.

               

                Рассмотрим подробнее некоторые из блоков на примере несимметричной задачи с пятью городами.

   Матрица С                                                                                                          Матрица С’

 

1

2

3

4

5

 

 

1

2

3

4

5

1

бескон.

25

40

31

27

 

1

бескон.

0

15

3

2

2

5

бескон.

17

30

25

 

2

0

бескон.

12

22

20

3

19

15

бескон.

6

1

 

3

18

14

бескон.

2

0

4

9

50

24

бескон.

6

 

4

3

44

18

бескон.

0

5

22

8

7

10

бескон.

 

5

15

1

0

0

бескон.

 

                Блок 2. В нашей задаче с пятью городами из приведенной матрицы C’ видно, что первое значение Х (корень R) имеет w(X)=(25+5+1+6+7)+(0+0+0+3+0)=47.

 

                Блок 3. В приведенной матрице стоимостей С’, связанной с Х, каждая строка и столбец имеют хотя бы по одному нулевому элементу. Можно предположить, что ребра, соответствующие этим нулевым стоимостям, скорее всего войдут в оптимальный ГЦ.  Встает вопрос: какое же из этих ребер выбрать в качестве  (k,l)? Ребро  (k,l) нужно выбирать так, чтобы попытаться получить возможно большую по величине нижнюю границу для множества неY. (Идея проста: в Y пытаться оставлять варианты получше, а варианты похуже скидывать в неY).

                Пусть ребро (i,j) имеет сij=0 в С’. Вспомнив процедуру нахождения нижней границей для множества неR1,3 из предыдущего примера, получим, что в общем случае для неY эта граница задается в виде

                w(неY)=w(X)           + (наименьшая стоимость в строке i, не включая сij)+

                                               +  (наименьшая стоимость в столбце j, не включая сij).

                Чтобы эта оценка была возможно большей, надо из всех ребер (i,j) с сij=0 в текущей матрице С’ мы выбираем то, которое дает наибольшую “добавку” к w(X) в выражении для w(неY).

                Распишем блок 3 более подробно:

                3.1. Пусть S - множество ребер (i,j), таких, что сij=0 в текущей матрице С

                3.2. Вычисляем Dij=(наименьшая стоимость в строке i, не включая сij)+

+  (наименьшая стоимость в столбце j, не включая сij)                          для всех элементов из S.

                3.3.Выбираем следующее ребро ветвления  (k,l) из условия Dkl=max(Dij) по всем  (i,j) из S.

                Пример. Выбираем ребро  (k,l)=(2,1), т.к. D21=15=max(Dij) по всем  (i,j) из S.

   Dij                                                                                          Матрица С

 

1

2

3

4

5

 

 

1

2

3

4

5

1

 

2+1=3

 

 

 

 

1

бескон.

0

15

3

2

2

12+3=15

 

 

 

 

 

2

0

бескон.

12

22

20

3

 

 

 

 

2+0=2

 

3

18

14

бескон.

2

0

4

 

 

 

 

3+0=0

 

4

3

44

18

бескон.

0

5

 

 

0+12=12

0+2=2

 

 

5

15

1

0

0

бескон.

 

                Блок 4. В нашей задаче множество всех ГЦ, не содержащих ребро (2,1), получит нижнюю оценку, равную w(неY)=w(неR2,1)= w(X)+ D21=47+15=62.

                               Блок 5. При вычислении w(Y) выполняются следующие действия:

                5.1. В качестве матрицы С для множества Y берем матрицу C’ для Х.

                5.2. Из матрицы С исключаем строку k и столбец l.

                5.3. При построении ГЦ (проходящего через все вершины графа) мы должны воспрепятствовать формированию цикла, проходящего только через некоторые вершины графа и поэтому имеющего длину, меньшую, чем N. Для этого все ребра (p,q), включение которых в маршрут может привести к возникновению такого “короткого” цикла, исключаются из дальнейшего рассмотрения: сp,q= бескон..

                5.4. Приводим рассматриваемую матрицу С. Пусть h - сумма констант приведения.

                5.5. Вычисляем w(Y) по формуле w(Y)=w(X)+h.

                Пример. Из матрицы СX=CY вычеркиваем строку 2 и столбец 1. Так как ребро (2,1) - пока единственное выбранное ребро, только включение в маршрут ребра (1,2) может привести к возникновению “короткого” цикла. Поэтому принимаем с1,2= бескон.. В результате получается матрица, представленная в табл. а. Затем выполняем приведение матрицы (табл. б).

                w(Y)=w(X)+h=47+2+1=50.

  Матрица С                                                                                                          Матрица С’

 

2

3

4

5

 

 

2

3

4

5

1

бескон.

15

3

2

 

1

бескон.

13

1

0

3

14

бескон.

2

0

 

3

13

бескон.

2

0

4

44

18

бескон.

0

 

4

43

18

бескон.

0

5

1

0

0

бескон.

 

5

0

0

0

бескон.

                Блок 6. В конце концов мы должны прийти к множествам, содержащим так мало ГЦ, что мы сможем рассмотреть каждый из них и провести оценку для этой вершины без дальнейшего ветвления. Каждое ребро, про которое нам известно, что оно содержится во всех ГЦ из Y, сокращает размер матрицы С на одну строку и один столбец. Блок 6 проверяет, имеет ли текущая матрица С размер 2´2? Это означает, что текущее множество Y содержит всего 1 вариант, который и проверяется в блоке 7.

 

                Блоки 7 и 8. Блок 7 работает, только если С - матрица размером 2´2. В этом блоке генерируется содержащийся в Y ГЦ, а его вес обозначается через w(Y). В блоке 8 проверяется, лучше ли данный ГЦ, чем лучший из уже найденных ГЦ. Если нет, то новый ГЦ отбрасывается. Если да, то лучшим становится новый ГЦ.

 

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

                9.1. Определяем множество S конечных вершин текущего дерева решений.

                9.2. Вершина Х выбирается так, чтобы w(X)=min(w(v))) по всем v из S.

                Пример. S={ R2,1,неR2,1}; w( R2,1)=50 < w(неR2,1)=62. Поэтому Х=R2,1.

 

                Блок 10. Если нижняя граница текущей вершины w(Х) меньше уже найденной стоимости z0 ГЦ, то имеет смысл продолжать ветвление. В противном случае процесс заканчивается.

                Пример. В нашей задаче z0= бескон. > w(Х)=50; поэтому ветвление продолжается.

 

                Блок 11. Матрица стоимостей С для текущей вершины Х корректируется в следующем порядке:

                11.1. Проверяем, равно ли текущее множество Х предыдущему множеству Y, последний раз образованному в блоке 5? Если да, то это означает, что мы продолжаем двигаться вниз по одной и той же ветке дерева решений. В этом случае матрицу С корректировать не нужно; просто переходим в блок 3. На втором уровне дерева решений обычно так и происходит. Иначе переходим к п. 11.2, что означает переход к вершине, принадлежащей другой ветке дерева решений, и продолжение ветвления из этой вершины.

                11.2. В качестве С берем исходную матрицу стоимостей.

                11.3. В качестве S берем множество всех пар (i,j), которые должны быть ребрами в Х.

                11.4. Вычисляем g - сумму сij по всем  (i,j) из S.

                11.5. Для каждой пары (i,j) из S вычеркиваем строку i и столбец j в С. Для каждого ребра  (i,j) находим ребра (p,q), включение которых в маршрут может привести к возникновению “короткого” цикла, и исключаем их из дальнейшего рассмотрения: сp,q= бескон..

                Легко видеть, что этот шаг сводится к повторению того, что уже делалось раньше. Очевидная альтернатива, осуществление которой требует большого объема памяти, - запоминать матрицы C’ для каждой конечной вершины дерева. Как правило, это непрактично.

                11.6. Приводим матрицу С. Полагаем величину h равной сумме констант приведения.

                11.7. Вычисляем w(X)=g+h.

                Рис.

 

                Пример. В нашей задаче из п. 11.1 мы сразу отправились в блок 3; Х=R2,1,w(Х)=50 и дерево содержит только уровни 0 и 1. В соответствии с алгоритмом блока 3,

  Dij                                                                                                          Матрица С

 

2

3

4

5

 

 

2

3

4

5

1

 

 

 

1+0=1

 

1

бескон.

13

1

0

3

 

 

 

2+0=2

 

3

13

бескон.

2

0

4

 

 

 

18+0=18

 

4

43

18

бескон.

0

5

0+13=13

0+13=13

0+1=1

 

 

5

0

0

0

бескон.

                Выбираем ребро  (k,l)=(4,5), т.к. D45=18=max(Dij) по всем  (i,j) из S.

                Используя блок 4, находим нижнюю оценку неY: w(неY)=w(неR4,5)= w(R2,1)+ D45=50+18=68.

                Далее блок 5: рассматриваем вершину Y=R4,5. Из матрицы С вычеркиваем строку 4 и столбец 5. Полагаем с5,4= бескон. и приводим С.

  Матрица С                                                                                                          Матрица С’

 

2

3

4

 

 

2

3

4

1

бескон.

13

1

 

1

бескон.

12

0

3

13

бескон.

2

 

3

11

бескон.

0

5

0

0

бескон.

 

5

0

0

бескон.

                При этом h=3, значит w(Y)=50+h=53.

                В блоке 6 выясняем, что С - матрица  3´3, переходим в блок 9.

                S={неR2,1, неR4,5, R4,5}; w(неR2,1)=62, w(неR4,5)=68, w(R4,5)=53.   Поэтому Х=R4,5.

                Блок 10: z0= бескон.; из 11.1 переходим в блок 3 с Х=R4,5, w(Х)=53. В соответствии с алгоритмом блока 3,

 Dij                                                                                                          Матрица С

 

2

3

4

 

 

2

3

4

1

 

 

12

 

1

бескон.

12

0

3

 

 

11

 

3

11

бескон.

0

5

11

12

 

 

5

0

0

бескон.

                Выбираем ребро  (k,l)=(1,4), т.к. D14=12 (можно было выбрать и (5,3)).

                Используя блок 4, находим нижнюю оценку неY: w(неY)=w(неR1,4)= w(R4,5)+ D14=53+12=65.

                Далее блок 5: рассматриваем вершину Y=R1,4. Из матрицы С вычеркиваем строку 1 и столбец 4. В Y содержатся ребра (2,1), (4,5) и (1,4). К появлению “короткого” цикла может привести оставшееся на этот момент в матрице ребро (5,2); поэтому полагаем с5,2= бескон. и приводим С.

Матрица С                                                                                                          Матрица С’

 

2

3

 

 

2

3

3

11

бескон.

 

3

0

бескон.

5

бескон.

0

 

5

бескон.

0

                Находим, что h=11, значит w(Y)=50+h=64.

                В блоке 6 выясняем, что С - матрица  2´2 -> блок 7.

                По уже имеющимся ребрам (2,1), (4,5) и (1,4) достраиваем единственно возможные ребра - (5,3) и (3,2), получив ГЦ со следующим порядком городов: 3-2-1-4-5-3 и стоимостью z0=64; теперь это текущий лучший ГЦ.

                Оценим ситуацию. Нам не надо продолжать ветвление из вершин неR4,5 и неR1,4, т.к. их нижние границы больше 64. Однако в блоке 10 мы выясняем, что w(неR2,1)=62<64. Значит, из этой вершины надо продолжить ветвление.  Именно здесь и заработают пункты 2-7 блока 11. Ветвление из вершины неR2,1  мы рассмотрим на практическом занятии.