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

Задача коммивояжера
Построение и анализ алгоритмов
Лекция 2




Метод ветвей

Задача коммивояжера
Метод ветвей и границ Branch-and-Bound Method
Вариант поиска

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

Задача коммивояжера
Метод ветвей и границ Branch-and-Bound Method
Пример:

Задача коммивояжера
Некоторое решение
Старт
Финиш

Задача коммивояжера
Лучшее решение

Задача коммивояжера
Лучшее решение

Задача коммивояжера
Условия применимости метода ветвей и границ

Для каждого частичного решения должна быть определена стоимость Cost(a1, a2, …, ak)
Для всех частичных решений и их расширений должно быть выполнено
Cost(a1, a2, …, ak-1) ≤ Cost(a1, a2, …, ak-1, ak)
Тогда частичное решение (a1, a2, …, ak-1, ak) может быть отброшено, если его стоимость ≥ стоимости ранее вычисленных решений
В большинстве случаев Cost(a1, a2, …, ak) ≥ 0 и даже
Cost(a1, a2, …, ak) = Cost(a1, a2, …, ak-1) + С(ak),
где С(ak) ≥ 0 для всех ak.

Задача коммивояжера
Общий алгоритм МВГ
S1 = А1; k =

Задача коммивояжера
Задача коммивояжёра (ЗК) The Traveling Salesman Problem

Коммивояжер – бродячий торговец – коробейник
Коммивояжёр [ фр. commis voyageur ] – разъездной агент торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам, каталогам и т.п.
Условия задачи
Множество городов = множество вершин графа.
Количество городов – n.
Ребра (дуги) графа соединяют вершины, между которыми разрешены поездки.
Стоимость поездки из одного города в другой – вес ребра графа.

Задача коммивояжера
Пример (n = 5)
25
27
5
22
10
15
24
17
6
6
25
8
50
30
9
31
1
7
19
40
Матрица стоимостей
Cij –

Задача коммивояжера
Дано: 1. n – количество городов

Задача коммивояжера
Метод ветвей и границ в ЗК
Основные

Задача коммивояжера
Ветвление
YLeft(k) = Yk ∪ {(i, j)},
ZLeft(k)

Xk = (Yk, Zk)

YRight(k) = Yk,
ZRight(k) = Zk ∪ {(i, j)}

Yk – множество
включенных в маршрут дуг;
Zk – множество
исключенных дуг

Yk={(i1, j1), …,(ink, jnk)}

Включенная дуга

Исключенная дуга

Задача коммивояжера
Операция «приведения матрицы»
По строкам:
для

По столбцам:
для ∀j∈1..n:
hj = min {(Cij - gi): i∈1..n}
hi – минимальная сумма, достаточная для въезда откуда-либо в город j

i

j

Задача коммивояжера
Приведенная матрица
C*ij = Cij –

Стоимость по приведенной матрице изменилась, но оптимальное решение останется тем же (стоимость всех допустимых маршрутов уменьшена на одну и ту же величину)

Задача коммивояжера
Пример Вычитание по строкам
- 25
- 5
- 1
-

- 7

- 44

Задача коммивояжера
Вычитание по столбцам
- 3
d = 44

Задача коммивояжера
Результат операции приведения матрицы
В каждой строке

Нижняя граница стоимости любого решения d = 47

Задача коммивояжера
Включение дуги i-j (левая ветвь дерева) Например,

Действия над матрицей:
Вычеркивание i-й строки и j-го столбца (размер матрицы уменьшается на 1)
запрет (j, i): Cji := +∞

+∞

3) Затем новая операция приведения

Задача коммивояжера
Вычеркивание 3-й строки и 5-го столбца

- 3

- 12

- 15

Новый шаг операции приведения

Задача коммивояжера
Исключение дуги i-j (правая ветвь дерева) Например,

Действия над матрицей:
запрет (i, j): Cij := +∞
Затем новая операция приведения

- 2

Новая нижняя граница стоимости любого решения
d = 47 + 2 = 49
Δd = 2

Задача коммивояжера
После ветвления по дуге (3,5)



(3,5)
(3,5)
47
62=47+15
49=47+2

Задача коммивояжера
Какое ветвление сделать на первом шаге

Дуга (3,5) была рассмотрена в качестве примера возможного выбора.

Каковы «хорошие» варианты для выбора?

Задача коммивояжера
Кандидаты на ветвление (включение-исключение)
Δd = 3
Δd

Δd = 12

Δd = 2

Δd = 3

Δd = 2

Задача коммивояжера
Эвристика*: выбор дуги для ветвления
При переходе

Если Cij ≠ 0, то Δd = 0 (!).

Максимум

Задача коммивояжера
Эвристика: выбор дуги для ветвления
Выбрать в

Задача коммивояжера
Эвристика:
Рассмотрим множество пар (ν,λ), таких, что

Задача коммивояжера
Итак, в примере, следуя указанной эвристике,

- 2

- 1

- 3

Задача коммивояжера
После ветвления по дуге (2,1)



(2,1)
(2,1)
47
50=47+3
62=47 +

Рассмотрим продолжение левой ветви
(через слайд)

Задача коммивояжера
Правая ветвь (исключая (2, 1))
- 12
-

- 15

Задача коммивояжера
Поддерево от ветки (2, 1)

(2, 1)


Δd

Δd = 2

Δd = 18

Δd = 13

(4, 5)

(4, 5)

50

68=50+18

Задача коммивояжера
Левая ветвь (включая (4, 5))
- 1
-

53=50+3

Задача коммивояжера
Правая ветвь (исключая (4, 5))
- 18
68=50+18

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

(2, 1)


(4, 5)
(4, 5)
50
68=50+18
53=50+3
Кандидаты на ветвление

Задача коммивояжера
Поддерево от ветки (4, 5)

(4, 5)


(1,

(1, 4)

53

65=53+12

53=50+3

+ запрет (4, 1)
???

Задача коммивояжера
Запрет (4, 1) ???
Частичное решение (2,1),

64=53+11

Далее остаются (3, 2) и (5, 3),
т.о. 2 – 1 – 4 – 5, 5 – 3, 3 – 2,
т.е. решение есть маршрут (цикл) 2 – 1 – 4 – 5 – 3 – 2
Стоимость = 64. Легко проверить по матрице:
5 + 31 + 6 + 7 + 15 = 64

Задача коммивояжера
К этому моменту






47
Все решения
(2,1)
(4,5)
(1,4)
(5,3)
(3,2)
50
53
64
64
2 – 1

75=64+11

(5,3)

(1,4)

65

(4,5)

68

(2,1)

62

Задача коммивояжера
Ветвление узла (2,1)
Δd = 3
Δd =

Δd = 2

Δd = 0

Δd = 2

Δd = 0

Δd = 12

Правая ветвь (4,1)

- 12

74 = 62 + 12

Задача коммивояжера
Поддерево от ветки (2, 1)

(2, 1)


(4,

(4, 1)

62

74=62+12

62
см.

Задача коммивояжера
(4,1) – левая ветвь узла (2,1)
Δd

Задача коммивояжера
Ветвление узла (4,1)

(4, 1)


(2, 3)
(2, 3)
62
Δd

Δd = 8

Δd = 0

Δd = 2

Δd = 4

70=62+8

??

Задача коммивояжера
(2, 3) – левая ветка узла

Δd = 0
d = 62

Задача коммивояжера
Ветвление узла (2,3)

(2, 3)


(3, 5)
(3, 5)
62
Δd

Δd = 3

Δd = 4

66=62+4

Задача коммивояжера
Ветвление узла (2,3)

(2, 3)


(3, 5)
(3, 5)
62
66=62+4
Решение

62

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






47
Все решения
(2,1)
(4,5)
(1,4)
(5,3)
(3,2)
50
53
64
64
2 – 1 – 4

75=64+11

(5,3)

(1,4)

65

(4,5)

68

(2,1)

62

1 – 2 – 3 – 5 – 4 – 1

62

62

62

62

(4,1)

(2,3)

(3,5)

74

70

66

Задача коммивояжера
Сложность алгоритма
Сложность точного алгоритма ЗК (методом

Задача коммивояжера
Приближенные решения (не минимальной стоимости)
Зачем нужны приближенные

Задача коммивояжера
Приближенные решения (не минимальной стоимости)
Алгоритм ближайшего

1) 1 – 2 – 3 – 5 – 4 – 1: стоимость = 25+17+1+10+9 = 62
совпадает со стоимостью оптимального решения (!).

Если элемент матрицы (4,1) заменить на 9+x, то стоимость решения АБС станет 62+x, где x любое число (!)

Задача коммивояжера
2 – 1 – 5

4) 4 – 5 – 3 – 2 – 1 – 4: стоимость = 6+7+15+5+31 = 64
5) 5 – 3 – 4 – 1 – 2 – 5: стоимость = 7+6+9+25+25 = 72

Итак АБС: 62, 95, 69, 64, 72

Задача коммивояжера
Ещё пример: n = 6 Оптимальное решение

1 – 4 – 2 – 3 – 6 – 5 – 1 :
Стоимость = 16+16+16+0+5+12
= 65
2 – 4 – 5 – 6 – 3 – 1 – 2 :
Стоимость = 1+18+5+5+20+27
= 76
А: 3 – 6 – 2 – 4 – 5 – 1 – 3 :
Стоимость = 0+5+1+18+12+43
= 79

Задача коммивояжера
Б: 3 – 6 –

4 – 2 – 1 – 6 – 3 – 5 – 4 :
Стоимость = 16+7+26+5+5+48
= 107
А: 5 – 6 – 3 – 2 – 4 – 1 – 5 :
Стоимость = 5+5+13+1+21+30
= 75
Б: 5 – 6 – 2 – 4 – 1 – 3 – 5 :
Стоимость = 5+5+1+21+43+5
= 80
А: 6 – 2 – 4 – 5 – 1 – 3 – 6 :
Стоимость = 5+1+18+12+43+0
= 79 (см. 3А)
Б: 6 – 3 – 5 – 1 – 4 – 2 – 6 :
Стоимость = 5+5+12+16+16+25
= 79 (см. 3А)
В: 6 – 5 – 1 – 4 – 2 – 3 – 6 :
Стоимость = 5+12+16+16+16+0
= 65 (см. 3Б)
Итак, 65, 75, 76, 79, 80, 107

Задача коммивояжера
Оценка степени приближения алгоритма ближайшего

Nn – маршрут АБС, ⏐Nn⏐ – его длина (стоимость).
On – оптимальный маршрут,
⏐On⏐ – его длина (стоимость).
Утверждение. Если матрица {Cij} – (а) симметрична и
(б) удовлетворяет неравенству треугольника
Cij ≤ Cik + Ckj , ∀i, j, k,
то

Задача коммивояжера
2. Алгоритм включения ближайшего города (АВБГ)
Если

Задача коммивояжера
Пример: n = 6 Оптимальное решение 1

1 – 4 – 2 – 3 – 6 – 5 – 1 :
Стоимость = 16+16+16+0+5+12
= 65 (совпадает с АБС !)
2 – 3 – 6 – 5 – 1 – 4 – 2 :

Стоимость = 16+0+5+12+21+16
= 70

3 – 6 – 2 – 1 – 4 – 5 – 3 :
0+5+7+16+18+27= 73

5 – 6 – 3 – 2 – 1 – 4 – 5 :
5+5+13+7+16+18 = 64 !!

Задача коммивояжера
Оценка степени приближения АВБГ
In – маршрут

Задача коммивояжера
Сложность приближенных алгоритмов
АБС ≈ C1n2
АВБГ ≈

Задача коммивояжера
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ