Метод ветвей и границ

Существует достаточно большой класс задач, в которых для нахождения оптимального решения необходимо перебрать все возможные варианты решений по какому-либо критерию. Однако такой прямой перебор может занять очень много времени. Например, для выбора оптимальной последовательности проведения маркетинговых исследований группой из т специалистов разного профиля в п объектах рынка необходимо перебрать большое множество вариантов. В задаче коммивояжера для формирования оптимального маршрута объезда п городов необходимо выбрать один лучший из (п- 1)! вариантов по критериям времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева — связного графа, не содержащего циклов и петель. Процесс разбиения множества всех маршрутов на непересекающиеся подмножества в виде дерева представлен на рис. 4.26. Корень этого дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений.

Вершина (i,j) соответствует подмножеству всех маршрутов, содержащих ребро (ij), а вершина (zj) — подмножеству всех маршрутов, где это ребро отсутствует.

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

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

Рис. 4.26

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

  • 1) оценка не должна быть больше (при минимизации) или меньше (при максимизации) минимального (максимального) значения функции для рассматриваемого множества;
  • 2) оценка подмножества нижнего уровня не должна быть меньше (при минимизации) или больше (при максимизации) значения оценки подмножества более высокого уровня;
  • 3) оценка единственного варианта решения на последнем уровне точно совпадает со значением критерия целевой функции решения.

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

Рассмотрим решение задачи коммивояжера с исходными данными, записанными в табл. 4.1.

Для определения нижней границы множества воспользуемся операцией редукции, или приведения матрицы по строкам и столбцам, для чего необходимо в каждой строке матрицы D найти минимальный элемент табл. 4.3.

Таблица 43

i

1

2

3

4

5

di

1

OO

90

80

40

100

40

2

60

oo

40

50

70

40

3

50

30

oo

60

20

20

4

10

70

20

oo

50

10

5

20

40

50

20

oo

20

Затем вычесть его из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице (табл. 4.4) в каждой строке будет как минимум один ноль.

Таблица 4.4

j

i

1

2

3

4

5

1

ОО

50

40

0

60

2

20

ОО

0

10

30

3

30

10

ОО

40

0

4

0

60

10

ОО

40

5

0

20

30

0

ОО

dj

0

10

0

0

0

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

Таблица 4.5

j

i

1

2

3

4

5

d,

1

ОО

40

40

OW

60

40

2

20

ОО

0<20)

10

30

10

3

30

0C0)

ОО

40

0(30

0

4

0(Ю)

50

10

ОО

40

10

5

o<°>

10

30

0<°>

ОО

0

dj

0

10

10

0

30

Таким образом мы получим полностью редуцированную матрицу (табл. 4.5). Величины d, и dj называют константами приведения. Сумма констант приведения определяет нижнюю границу

Элемент матрицы dtj соответствует расстоянию от пункта i до пункта j. Поскольку в матрице п городов, то D является матрицей пХпс неотрицательными элементами dtj > 0. Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город. Длина маршрута определяется выражением

причем каждые строка и столбец входят в маршрут только один раз с элементом dy.

Определяем ребро ветвления, для чего для всех клеток матрицы табл. 4.5 с нулевыми элементами заменяем поочередно нули на °° и определяем для них сумму образовавшихся констант приведения, они приведены в скобках (см. табл. 4.5). Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1, 4), следовательно, множество разбивается на два подмножества {(1, 4)} включающее ребро, и {(1,4)}, не включающее ребро.

Исключение ребра (1,4) проводим путем замены элемента = 0 на после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества {(1, 4)}, в результате получим редуцированную матрицу (табл. 4.6).

Таблица 4.6

j

i

1

2

3

4

5

d,

1

oo

40

40

oo

60

40

2

20

oo

0

10

30

0

3

30

0

oo

40

0

0

4

0

50

10

oo

40

0

5

0

10

30

0

oo

0

dj

0

0

0

0

0

40

Нижняя граница гамильтоновых циклов этого подмножества

Включение ребра (1, 4) проводится путем исключения всех элементов первой строки и четвертого столбца табл. 4.6, в которой элемент dA =0 заменяем на °° для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу 4x4 (табл. 4.7), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы

j

i

1

2

3

5

d,

2

20

оо

0

30

0

3

30

0

оо

0

0

4

оо

50

10

40

10

5

0

10

30

оо

0

dj

0

0

0

0

10

После операции приведения сокращенная матрица будет иметь следующий вид (табл. 4.8).

Таблица 4.8

1

2

3

5

di

2

20

оо

0(20)

30

20

3

30

0<10>

оо

0(30)

0

4

оо

40

0(3°)

30

30

5

0(зо)

10

30

оо

10

dj

20

10

0

30

Нижняя граница подмножества {(1,4)} равна

Поскольку нижняя граница этого подмножества {(1, 4)} меньше, чем нижняя граница подмножества {(1, 4)}, то ребро (1, 4) включаем в маршрут.

Затем опять определяем ребро ветвления. С этой целью определяем сумму констант приведения (указаны в скобках, табл. 4.8) для нулевых клеток, заменяя их поочередно на °°. Максимальная сумма констант dA + = 30 + 0 = 30 принадлежит и ребру (4, 3). Следовательно, разбиваем множество маршрутов {(1,4)} на два подмножества {(1,4); (4,3)} и {(1,4); (4,з)}:

Исключение ребра (4, 3) проводим путем замены элемента матрицы з = 0 на оо (табл. 4.9).

Определяем константы приведения и нижнюю границу

Включение ребра (4, 3) в матрицу проводим путем исключения элементов третьей строки и третьего столбца (табл. 4.10).

j

i

1

2

3

5

d,

2

20

ОО

0

30

0

3

30

0

ОО

0

0

4

ОО

40

ОО

30

30

5

0

10

30

ОО

0

dj

20

10

0

0

30

Таблица 4.10

j

i

1

2

5

d,

2

20

ОО

30

20

3

30

0

0

0

5

0

10

ОО

0

dj

20

10

0

20

Определим константы приведения и нижнюю границу подмножества:

Поскольку эта граница меньше, то ребро (4, 3) включаем в маршрут. Затем проводим операцию приведения и получим редуцированную матрицу (табл. 4.11).

Таблица 4.11

j

i

1

2

5

2

0

ОО

10

3

30

0

0

5

0

10

ОО

Определяем ребро ветвления, для чего поочередно нулевые элементы матрицы табл. 4.11 заменяем на оо и определяем для них сумму констант приведения (указаны в скобках табл. 4.12).

Таблица 4.12

7

1

2

5

2

0<|°)

ОО

10

3

30

Ооо)

ООО)

5

0<ю)

10

ОО

Выбираем ребро ветвления (2, 1).

Исключаем ребро (2, 1) путем замены 2,i = 0 на °° (табл. 4.13).

Таблица 4.13

1

2

5

d,

2

оо

оо

10

10

3

30

0

0

0

5

0

10

оо

0

dj

0

0

0

10

Вычислим нижнюю границу:

//(2, 1)= 170 + 10 = 180.

Включаем ребро (2,1) путем исключения первой строки и первого столбца, получим сокращенную матрицу (табл. 4.14).

11(2, 1)= 170 + 10= 180.

Таблица 4.14

2

5

d;

3

0

0

0

5

10

оо

10

dj

0

0

Для исключения образования негамильтонова цикла заменяем d$t2 = 0 на оо.

В конечном счете получаем сокращенную матрицу (табл. 4.15).

Таблица 4.15

j

i

2

5

3

oo

0

5

10

oo

В соответствии с этой матрицей включаем в гамильтонов маршрут (рис. 4.27) ребра (3, 5) и (5, 2). В результате но дереву ветвлений гамильтонов цикл образуют ребра (1,4), (4,3), (3, 5), (5, 2), (2, 1) (рис. 4.28) Последовательность объезда городов коммивояжером 1—4 — 3 — 5 — 2 — 1 представлена матрицей смежности в табл. 4.16. Длина маршрута равна F(M^) = = 180 совпадает с нижней границей подмножества.

Таблица 4.16

1

2

3

4

5

1

0

0

0

1

0

2

1

0

0

0

0

3

0

0

0

0

1

4

0

0

1

0

0

5

0

1

0

0

0

Рис. 4.27

Рис. 4.28

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

1. Проводим операцию редукции матрицы расстояний по строкам и столбцам, находим нижнюю границу всего множества маршрутов

  • 2. В каждой клетке, в которых dl} = 0, поочередно заменяем нули на °°, затем находим новые суммы констант приведения dj + dp которые записываем в клетках рядом с нулем в скобках (см. табл. 4.5, 4.8).
  • 3. Выбираем ребро ветвления (i,j) по максимальной величине суммы констант приведения. Затем исключаем его из множества путем замены элемента матрицы dy = °°. В результате будет образовано подмножество маршрутов {(г,/)}.
  • 4. Редуцируем полученную матрицу расстояний и определяем нижнюю границу этого подмножества маршрутов H(i,j).
  • 5. Включаем дугу (t,j) в маршрут путем исключения i-й строки и j-то столбца из матрицы и замены симметричного элемента матрицы dp = °° для исключения образования негамильтонова цикла.
  • 6. Редуцируем сокращенную_матрицу и определяем нижнюю границу подмножества

^Сравниваем нижние границы подмножеств Я{(/‘, ])} и H{(iyj)} и подвергаем подмножество, имеющее меньшее значение нижней границы, ветвлению.

8. Определяем гамильтонов цикл при получении матрицы 2x2.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >