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

Сентябрь 3, 2022

Главная
Алгебра
Метод ветвей и границ

Содержание

2. 17.02.2014 Метод ветвей и границ Задача коммивояжера Метод ветвей и границ Branch-and-Bound Method Вариант поиска с
3. 17.02.2014 Метод ветвей и границ Задача коммивояжера Метод ветвей и границ Branch-and-Bound Method Пример: задача об
4. 17.02.2014 Метод ветвей и границ Задача коммивояжера Некоторое решение Старт Финиш
5. 17.02.2014 Метод ветвей и границ Задача коммивояжера Лучшее решение
6. 17.02.2014 Метод ветвей и границ Задача коммивояжера Лучшее решение
7. 17.02.2014 Метод ветвей и границ Задача коммивояжера Условия применимости метода ветвей и границ (МВГ) Для каждого
8. 17.02.2014 Метод ветвей и границ Задача коммивояжера Общий алгоритм МВГ S1 = А1; k = 1;
9. 17.02.2014 Метод ветвей и границ Задача коммивояжера Задача коммивояжёра (ЗК) The Traveling Salesman Problem (TSP) Коммивояжер
10. 17.02.2014 Метод ветвей и границ Задача коммивояжера Пример (n = 5) 25 27 5 22 10
11. 17.02.2014 Метод ветвей и границ Задача коммивояжера Дано: 1. n – количество городов 2. C =
12. 17.02.2014 Метод ветвей и границ Задача коммивояжера Метод ветвей и границ в ЗК Основные идеи: Ветвление
13. 17.02.2014 Метод ветвей и границ Задача коммивояжера Ветвление YLeft(k) = Yk ∪ {(i, j)}, ZLeft(k) =
14. 17.02.2014 Метод ветвей и границ Задача коммивояжера Операция «приведения матрицы» По строкам: для ∀i∈1..n: gi =
15. 17.02.2014 Метод ветвей и границ Задача коммивояжера Приведенная матрица C*ij = Cij – gi – hj
16. 17.02.2014 Метод ветвей и границ Задача коммивояжера Пример Вычитание по строкам - 25 - 5 -
17. 17.02.2014 Метод ветвей и границ Задача коммивояжера Вычитание по столбцам - 3 d = 44 +
18. 17.02.2014 Метод ветвей и границ Задача коммивояжера Результат операции приведения матрицы В каждой строке и в
19. 17.02.2014 Метод ветвей и границ Задача коммивояжера Включение дуги i-j (левая ветвь дерева) Например, 3-5 Действия
20. 17.02.2014 Метод ветвей и границ Задача коммивояжера Вычеркивание 3-й строки и 5-го столбца (размер матрицы уменьшается
21. 17.02.2014 Метод ветвей и границ Задача коммивояжера Исключение дуги i-j (правая ветвь дерева) Например, 3-5 Действия
22. 17.02.2014 Метод ветвей и границ Задача коммивояжера После ветвления по дуге (3,5) (3,5) (3,5) 47 62=47+15
23. 17.02.2014 Метод ветвей и границ Задача коммивояжера Какое ветвление сделать на первом шаге ? Дуга (3,5)
24. 17.02.2014 Метод ветвей и границ Задача коммивояжера Кандидаты на ветвление (включение-исключение) Δd = 3 Δd =
25. 17.02.2014 Метод ветвей и границ Задача коммивояжера Эвристика*: выбор дуги для ветвления При переходе в правую
26. 17.02.2014 Метод ветвей и границ Задача коммивояжера Эвристика: выбор дуги для ветвления Выбрать в приведенной матрице
27. 17.02.2014 Метод ветвей и границ Задача коммивояжера Эвристика: Рассмотрим множество пар (ν,λ), таких, что C*ν,λ= 0:
28. 17.02.2014 Метод ветвей и границ Задача коммивояжера Итак, в примере, следуя указанной эвристике, выбирается ребро (2,
29. 17.02.2014 Метод ветвей и границ Задача коммивояжера После ветвления по дуге (2,1) (2,1) (2,1) 47 50=47+3
30. 17.02.2014 Метод ветвей и границ Задача коммивояжера Правая ветвь (исключая (2, 1)) - 12 - 3
31. 17.02.2014 Метод ветвей и границ Задача коммивояжера Поддерево от ветки (2, 1) (2, 1) Δd =
32. 17.02.2014 Метод ветвей и границ Задача коммивояжера Левая ветвь (включая (4, 5)) - 1 - 2
33. 17.02.2014 Метод ветвей и границ Задача коммивояжера Правая ветвь (исключая (4, 5)) - 18 68=50+18
34. 17.02.2014 Метод ветвей и границ Задача коммивояжера (2, 1) (4, 5) (4, 5) 50 68=50+18 53=50+3
35. 17.02.2014 Метод ветвей и границ Задача коммивояжера Поддерево от ветки (4, 5) (4, 5) (1, 4)
36. 17.02.2014 Метод ветвей и границ Задача коммивояжера Запрет (4, 1) ??? Частичное решение (2,1), (4,5), (1,4)
37. 17.02.2014 Метод ветвей и границ Задача коммивояжера К этому моменту 47 Все решения (2,1) (4,5) (1,4)
38. 17.02.2014 Метод ветвей и границ Задача коммивояжера Ветвление узла (2,1) Δd = 3 Δd = 8
39. 17.02.2014 Метод ветвей и границ Задача коммивояжера Поддерево от ветки (2, 1) (2, 1) (4, 1)
40. 17.02.2014 Метод ветвей и границ Задача коммивояжера (4,1) – левая ветвь узла (2,1) Δd = 0
41. 17.02.2014 Метод ветвей и границ Задача коммивояжера Ветвление узла (4,1) (4, 1) (2, 3) (2, 3)
42. 17.02.2014 Метод ветвей и границ Задача коммивояжера (2, 3) – левая ветка узла (4,1) Δd =
43. 17.02.2014 Метод ветвей и границ Задача коммивояжера Ветвление узла (2,3) (2, 3) (3, 5) (3, 5)
44. 17.02.2014 Метод ветвей и границ Задача коммивояжера Ветвление узла (2,3) (2, 3) (3, 5) (3, 5)
45. 17.02.2014 Метод ветвей и границ Задача коммивояжера Итак 47 Все решения (2,1) (4,5) (1,4) (5,3) (3,2)
46. 17.02.2014 Метод ветвей и границ Задача коммивояжера Сложность алгоритма Сложность точного алгоритма ЗК (методом ВиГ) в
47. 17.02.2014 Метод ветвей и границ Задача коммивояжера Приближенные решения (не минимальной стоимости) Зачем нужны приближенные решения?
48. 17.02.2014 Метод ветвей и границ Задача коммивояжера Приближенные решения (не минимальной стоимости) Алгоритм ближайшего соседа (АБС)
49. 17.02.2014 Метод ветвей и границ Задача коммивояжера 2 – 1 – 5 – 3 – 4
50. 17.02.2014 Метод ветвей и границ Задача коммивояжера Ещё пример: n = 6 Оптимальное решение 1 –
51. 17.02.2014 Метод ветвей и границ Задача коммивояжера Б: 3 – 6 – 5 – 1 –
52. 17.02.2014 Метод ветвей и границ Задача коммивояжера Оценка степени приближения алгоритма ближайшего соседа (АБС) Nn –
53. 17.02.2014 Метод ветвей и границ Задача коммивояжера 2. Алгоритм включения ближайшего города (АВБГ) Если есть цепочка
54. 17.02.2014 Метод ветвей и границ Задача коммивояжера Пример: n = 6 Оптимальное решение 1 – 4
55. 17.02.2014 Метод ветвей и границ Задача коммивояжера Оценка степени приближения АВБГ In – маршрут АВБГ, ⏐In⏐
56. 17.02.2014 Метод ветвей и границ Задача коммивояжера Сложность приближенных алгоритмов АБС ≈ C1n2 АВБГ ≈ C2n2,
58. Скачать презентацию

Слайд 2

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

с возвращением.
Каждое решение имеет стоимость.
Требуется найти решение минимальной стоимости.

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

Слайд 3

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

об оптимальном маршруте коня на шахматной доске
Найти путь коня из одного заданного поля в другое, содержащий минимальное число шагов

Слайд 4

17.02.2014
Метод ветвей и границ Задача коммивояжера
Некоторое решение
Старт
Финиш

Слайд 5

17.02.2014
Метод ветвей и границ Задача коммивояжера
Лучшее решение

Слайд 6

17.02.2014
Метод ветвей и границ Задача коммивояжера
Лучшее решение

Слайд 7

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

(МВГ)

Для каждого частичного решения должна быть определена стоимость 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.

Слайд 8

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

1; cost = 0; LowCost = + ∞;
while (k>0) { //пока не все решения найдены
while ((Sk != ∅) && (cost < LowCost) ) { // продвижение вперед:
ak = элемент из Sk; //выбор очередного элемента из Sk
Sk = Sk − {ak};
cost = f_cost (a1,…, ak-1,ak);
f (((a1,…, ak-1,ak) – решение) && (cost < LowCost)) { LowCost = cost; /*фиксировать (a1,…, ak-1,ak) как текущий минимум */}
else {
// переход к следующему уровню
k ++;
вычислить Sk;
}
} // end while продвижения вперед
k --; // backtrack
cost = f_cost (a1,…,ak);
} // последнее сохраняемое решение имеет наименьшую стоимость

Слайд 9

17.02.2014
Метод ветвей и границ Задача коммивояжера
Задача коммивояжёра (ЗК) The Traveling Salesman Problem

(TSP)

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

Слайд 10

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

убыток (расходы) при переезде из i в j

Слайд 11

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

2. C = {Cij} i,j=1…n – матрица стоимостей
Найти: маршрут объезда всех городов (каждого по одному разу) с возвратом в исходный пункт, при этом стоимость поездки должна быть минимальной.

Слайд 12

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

идеи:
Ветвление – бинарное: на каждом шаге маршруты разбиваются на две группы – включающие дугу (i, j) и запрещающие дугу (i, j)
2. Операция «приведения матрицы»
3. Эвристика в выборе дуги маршрута для ветвления в дереве вариантов

Слайд 13

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

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

Xk = (Yk, Zk)

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

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

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

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

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

Слайд 14

17.02.2014
Метод ветвей и границ Задача коммивояжера
Операция «приведения матрицы»
По строкам:
для ∀i∈1..n:

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

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

Слайд 15

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

gi – hj ≥ 0
Σi∈1..n gi + Σj∈1..n hj = d
d – нижняя граница стоимости любого решения, не зависит от π, т.к. каждый город
посещается ровно один раз.
Т.о.

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

Слайд 16

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

- 7

- 44

Слайд 17

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

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

Слайд 18

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

и в каждом столбце имеется хотя бы один 0

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

Слайд 19

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

3-5

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

+∞

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

Слайд 20

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

(размер матрицы уменьшается : 4×4 вместо 5×5)

- 3

- 12

- 15

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

Слайд 21

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

3-5

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

- 2

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

Слайд 22

17.02.2014
Метод ветвей и границ Задача коммивояжера
После ветвления по дуге (3,5)
(3,5)
(3,5)
47
62=47+15
49=47+2

Слайд 23

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

Дуга (3,5) была рассмотрена в качестве примера возможного выбора.
Каковы «хорошие» варианты для выбора?

Слайд 24

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

= 15

Δd = 12

Δd = 2

Δd = 3

Δd = 2

Слайд 25

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

в правую ветвь новая нижняя граница стоимости любого решения в этой ветви есть d + Δd.
В нашем примере для нулевых элементов матрицы рассматриваются варианты:

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

Максимум

Слайд 26

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

приведенной матрице такой нулевой элемент, который после замены на ∞ и
последующего приведения матрицы
даст максимальную нижнюю границу
стоимости любого решения
(т.е. максимальное Δd и, следовательно, d)
Метафора: самый тяжелый ноль!

Слайд 27

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

C*ν,λ= 0:
I = {(ν,λ): C*ν,λ= 0, ν∈I1,λ∈ I2},
где I1, I2 – множество городов для выбора по строкам и по столбцам, соответственно.
Пусть для (ν,λ)∈I имеем
Δd(ν,λ)=min {C*ν,ρ: ρ≠λ} + min {C*σ, λ: σ≠ν}.
Выбираем (i, j) = arg max {Δd(ν,λ): (ν,λ)∈ I}.
При этом Δd = Δd(i,j)
Примечание: более точно везде использовать num(i), num(j) – номера городов, а i, j – индексы матрицы

Слайд 28

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

выбирается ребро (2, 1) Левая ветвь (включая (2, 1))

- 2

- 1

- 3

Слайд 29

17.02.2014
Метод ветвей и границ Задача коммивояжера
После ветвления по дуге (2,1)
(2,1)
(2,1)
47
50=47+3
62=47 +

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

Слайд 30

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

- 15

Слайд 31

17.02.2014
Метод ветвей и границ Задача коммивояжера
Поддерево от ветки (2, 1)
(2, 1)
Δd

= 1

Δd = 2

Δd = 18

Δd = 13

(4, 5)

68=50+18

Слайд 32

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

53=50+3

Слайд 33

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

Слайд 34

17.02.2014
Метод ветвей и границ Задача коммивояжера
(2, 1)
(4, 5)
(4, 5)
50
68=50+18
53=50+3
Кандидаты на ветвление

узла (4, 5):
(1, 4) : Δd = 12
(5, 3) : Δd = 12

Слайд 35

17.02.2014
Метод ветвей и границ Задача коммивояжера
Поддерево от ветки (4, 5)
(4, 5)
(1,

(1, 4)

65=53+12

53=50+3

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

Слайд 36

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

(4,5), (1,4) или
2 – 1 – 4 – 5
Запретить нужно (5, 2) !

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

Слайд 37

17.02.2014
Метод ветвей и границ Задача коммивояжера
К этому моменту
47
Все решения
(2,1)
(4,5)
(1,4)
(5,3)
(3,2)
50
53
64
64
2 – 1

– 4 – 5 – 3 – 2

75=64+11

(5,3)

(1,4)

(4,5)

(2,1)

Слайд 38

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

Δd = 2

Δd = 0

Δd = 2

Δd = 0

Δd = 12

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

- 12

74 = 62 + 12

Слайд 39

17.02.2014
Метод ветвей и границ Задача коммивояжера
Поддерево от ветки (2, 1)
(2, 1)
(4,

(4, 1)

74=62+12

62
см.

Слайд 40

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

= 0

Слайд 41

17.02.2014
Метод ветвей и границ Задача коммивояжера
Ветвление узла (4,1)
(4, 1)
(2, 3)
(2, 3)
62
Δd

= 3

Δd = 8

Δd = 0

Δd = 2

Δd = 4

70=62+8

Слайд 42

17.02.2014
Метод ветвей и границ Задача коммивояжера
(2, 3) – левая ветка узла

(4,1)

Δd = 0
d = 62

Слайд 43

17.02.2014
Метод ветвей и границ Задача коммивояжера
Ветвление узла (2,3)
(2, 3)
(3, 5)
(3, 5)
62
Δd

= 3

Δd = 3

Δd = 4

66=62+4

Слайд 44

17.02.2014
Метод ветвей и границ Задача коммивояжера
Ветвление узла (2,3)
(2, 3)
(3, 5)
(3, 5)
62
66=62+4
Решение

+ (1,2) + (5,4)
Т.о. (4,1), (2,3), (3,5), (1,2), (5,4) или
1 – 2 – 3 – 5 – 4 – 1

Слайд 45

17.02.2014
Метод ветвей и границ Задача коммивояжера
Итак
47
Все решения
(2,1)
(4,5)
(1,4)
(5,3)
(3,2)
50
53
64
64
2 – 1 – 4

– 5 – 3 – 2

75=64+11

(5,3)

(1,4)

(4,5)

(2,1)

1 – 2 – 3 – 5 – 4 – 1

(4,1)

(2,3)

(3,5)

Слайд 46

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

ВиГ) в среднем (при «случайных» матрицах стоимостей)
Cn, где C≅1.26
Эмпирический результат (опытным путем)

Слайд 47

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

решения?
1) «Быстрые» решения
2) Для оценки границ при поиске точного решения!

Слайд 48

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

соседа (АБС)
Начиная с любого города, выбираем на каждом шаге следующий город, стоимость проезда в который из данного города минимальна

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

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

Слайд 49

17.02.2014
Метод ветвей и границ Задача коммивояжера
2 – 1 – 5

– 3 – 4 – 2 : стоимость = 5+27+7+6+50= 95
3 – 5 – 2 – 1 – 4 – 3 : стоимость = 1+8+5+31+24= 69

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

Слайд 50

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

1 – 4 – 3 – 5 – 6 – 2 – 1. Стоимость = 16+25+5+5+5+7 = 63

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

Слайд 51

17.02.2014
Метод ветвей и границ Задача коммивояжера
Б: 3 – 6 –

5 – 1 – 4 – 2 – 3 : стоимость = 0+5+12+16+16+16 = 65 (см. 1)

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

Слайд 52

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

(АБС)

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

Слайд 53

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

есть цепочка vi(1) – vi(2) – … – vi(k-1) – vi(k),
то следующим выбирается город vj,
ближайший к этой цепочке,
т.е. имеющий минимальную из стоимостей Ci(q),j (для q=1,…,k), и этот город
вставляется в текущий маршрут
вслед за городом vi(q).
vi(1) – vi(2) – … – vi(q) – vj –vi(q+1) – …– vi(k-1) – vi(k),

Слайд 54

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

– 4 – 3 – 5 – 6 – 2 – 1. Стоимость = 16+25+5+5+5+7 = 63

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 !!

Слайд 55

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

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

Слайд 56

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

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

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

Содержание

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

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

17.02.2014Метод ветвей и границ Задача коммивояжераНекоторое решениеСтартФиниш

17.02.2014Метод ветвей и границ Задача коммивояжераЛучшее решение

17.02.2014Метод ветвей и границ Задача коммивояжераЛучшее решение

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

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

17.02.2014Метод ветвей и границ Задача коммивояжераЗадача коммивояжёра (ЗК) The Traveling Salesman Problem

17.02.2014Метод ветвей и границ Задача коммивояжераПример (n = 5)252752210152417662585030931171940Матрица стоимостейCij –

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

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

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

17.02.2014Метод ветвей и границ Задача коммивояжераОперация «приведения матрицы»По строкам: для ∀i∈1..n:

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

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

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

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

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

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

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

17.02.2014Метод ветвей и границ Задача коммивояжераПосле ветвления по дуге (3,5)(3,5)(3,5)4762=47+1549=47+2

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

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

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

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

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

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

17.02.2014Метод ветвей и границ Задача коммивояжераПосле ветвления по дуге (2,1)(2,1)(2,1)4750=47+362=47 +

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

17.02.2014Метод ветвей и границ Задача коммивояжераПоддерево от ветки (2, 1)(2, 1)Δd

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

17.02.2014Метод ветвей и границ Задача коммивояжераПравая ветвь (исключая (4, 5))- 1868=50+18

17.02.2014Метод ветвей и границ Задача коммивояжера(2, 1)(4, 5)(4, 5)5068=50+1853=50+3Кандидаты на ветвление

17.02.2014Метод ветвей и границ Задача коммивояжераПоддерево от ветки (4, 5)(4, 5)(1,

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

17.02.2014Метод ветвей и границ Задача коммивояжераК этому моменту47Все решения(2,1)(4,5)(1,4)(5,3)(3,2)505364642 – 1

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

17.02.2014Метод ветвей и границ Задача коммивояжераПоддерево от ветки (2, 1)(2, 1)(4,

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

17.02.2014Метод ветвей и границ Задача коммивояжераВетвление узла (4,1)(4, 1)(2, 3)(2, 3)62Δd

17.02.2014Метод ветвей и границ Задача коммивояжера(2, 3) – левая ветка узла

17.02.2014Метод ветвей и границ Задача коммивояжераВетвление узла (2,3)(2, 3)(3, 5)(3, 5)62Δd

17.02.2014Метод ветвей и границ Задача коммивояжераВетвление узла (2,3)(2, 3)(3, 5)(3, 5)6266=62+4Решение

17.02.2014Метод ветвей и границ Задача коммивояжераИтак47Все решения(2,1)(4,5)(1,4)(5,3)(3,2)505364642 – 1 – 4

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

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

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

17.02.2014Метод ветвей и границ Задача коммивояжера 2 – 1 – 5

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

17.02.2014Метод ветвей и границ Задача коммивояжера Б: 3 – 6 –

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

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

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

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

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

Похожие презентации

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

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
Некоторое решение
Старт
Финиш

17.02.2014
Метод ветвей и границ Задача коммивояжера
Лучшее решение

17.02.2014
Метод ветвей и границ Задача коммивояжера
Лучшее решение

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

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
Задача коммивояжёра (ЗК) The Traveling Salesman Problem

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

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

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

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
Операция «приведения матрицы»
По строкам:
для ∀i∈1..n:

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

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

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

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

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

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

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
После ветвления по дуге (3,5)
(3,5)
(3,5)
47
62=47+15
49=47+2

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

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

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

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

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

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
После ветвления по дуге (2,1)
(2,1)
(2,1)
47
50=47+3
62=47 +

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
Поддерево от ветки (2, 1)
(2, 1)
Δd

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

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
(2, 1)
(4, 5)
(4, 5)
50
68=50+18
53=50+3
Кандидаты на ветвление

17.02.2014
Метод ветвей и границ Задача коммивояжера
Поддерево от ветки (4, 5)
(4, 5)
(1,

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
К этому моменту
47
Все решения
(2,1)
(4,5)
(1,4)
(5,3)
(3,2)
50
53
64
64
2 – 1

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
Поддерево от ветки (2, 1)
(2, 1)
(4,

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
Ветвление узла (4,1)
(4, 1)
(2, 3)
(2, 3)
62
Δd

17.02.2014
Метод ветвей и границ Задача коммивояжера
(2, 3) – левая ветка узла

17.02.2014
Метод ветвей и границ Задача коммивояжера
Ветвление узла (2,3)
(2, 3)
(3, 5)
(3, 5)
62
Δd

17.02.2014
Метод ветвей и границ Задача коммивояжера
Ветвление узла (2,3)
(2, 3)
(3, 5)
(3, 5)
62
66=62+4
Решение

17.02.2014
Метод ветвей и границ Задача коммивояжера
Итак
47
Все решения
(2,1)
(4,5)
(1,4)
(5,3)
(3,2)
50
53
64
64
2 – 1 – 4

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

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

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
2 – 1 – 5

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

17.02.2014
Метод ветвей и границ Задача коммивояжера
Б: 3 – 6 –

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

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

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

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

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