Построение и анализ алгоритмов
Метод ветвей и границ Branch-and-Bound Method
Метод ветвей и границ
Метод ветвей и границ Branch-and-Bound Method
Некоторое решение
Лучшее решение
Лучшее решение
Условия применимости метода ветвей и границ (МВГ)
Общий алгоритм МВГ
Задача коммивояжёра (ЗК) The Traveling Salesman Problem (TSP)
Пример (n = 5)
Метод ветвей и границ в ЗК
Ветвление
Операция «приведения матрицы»
Пример Вычитание по строкам
Вычитание по столбцам
Результат операции приведения матрицы
Включение дуги i-j (левая ветвь дерева) Например, 3-5
Вычёркивание 3-й строки и 5-го столбца (размер матрицы уменьшается : 44 вместо 55)
Исключение дуги i-j (правая ветвь дерева) Например, 3-5
После ветвления по дуге (3,5)
Какое ветвление сделать на первом шаге ?
Кандидаты на ветвление (включение-исключение)
Эвристика*: выбор дуги для ветвления
Эвристика: выбор дуги для ветвления
Эвристика:
Итак, в примере, следуя указанной эвристике, выбирается ребро (2, 1) Левая ветвь (включая (2, 1))
После ветвления по дуге (2,1)
Правая ветвь (исключая (2, 1))
Поддерево от ветки (2, 1)
Левая ветвь (включая (4, 5))
Правая ветвь (исключая (4, 5))
Поддерево от ветки (4, 5)
Запрет (4, 1) ???
К этому моменту
Ветвление узла (2,1)
Поддерево от ветки (2, 1)
(4,1) – левая ветвь узла (2,1)
Ветвление узла (4,1)
(2, 3) – левая ветка узла (4,1)
Ветвление узла (2,3)
Ветвление узла (2,3)
Итак
Сложность алгоритма
Приближённые решения (не минимальной стоимости)
Приближённые решения (не минимальной стоимости)
Примеры обходов АБС
Ещё пример: n = 6 Оптимальное решение 1 – 4 – 3 – 5 – 6 – 2 – 1. Стоимость = 16+25+5+5+5+7 = 63
Б: 3 – 6 – 5 – 1 – 4 – 2 – 3 : стоимость = 0+5+12+16+16+16 = 65 (см. 1)
Оценка степени приближения алгоритма ближайшего соседа (АБС)
2. Алгоритм включения ближайшего города (АВБГ)
Пример: n = 6 Оптимальное решение 1 – 4 – 3 – 5 – 6 – 2 – 1. Стоимость = 16+25+5+5+5+7 = 63
Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2
Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2
Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2
Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2
Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2
Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2
Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2
Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3
Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3
Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3
Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3
Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3
Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3
Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3
Оценка степени приближения АВБГ
Сложность приближённых алгоритмов
5.02M
Categories: mathematicsmathematics programmingprogramming

Метод ветвей и границ. Задача коммивояжёра. (Лекция 2)

1. Построение и анализ алгоритмов

Лекция 2
Метод ветвей и границ
1. Общая схема
2. Задача коммивояжёра
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
1

2. Метод ветвей и границ Branch-and-Bound Method

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

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

С>0
Все решения
С>5
1 группа решений
2 группа решений
С>8

С>30
Группу
плохих
решений
можно не
исследовать
Получено
относительно
хорошее
решение С=20
09.02.2016
3 группа решений
Метод ветвей и границ
Задача коммивояжёра
3

4. Метод ветвей и границ Branch-and-Bound Method

Пример:
задача об оптимальном маршруте коня
на шахматной доске
Найти путь коня из одного заданного поля в другое,
содержащий минимальное число шагов
4
5
2
6
1
7
09.02.2016
3
8
Метод ветвей и границ
Задача коммивояжёра
4

5. Некоторое решение

Финиш
6
7
10
5
4
9
8
Старт
3
1
2
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
5

6. Лучшее решение

4
3
2
1
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
6

7. Лучшее решение

4
3
2
1
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
7

8. Условия применимости метода ветвей и границ (МВГ)

1.Для каждого частичного решения должна быть
определена стоимость Cost(a1, a2, …, ak)
2.Для всех частичных решений и их расширений должно
быть выполнено
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.
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
8

9. Общий алгоритм МВГ

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);
if (((a1,…, ak-1,ak) – решение) && (cost < LowCost)) { LowCost = cost;
/*фиксировать (a1,…, ak-1,ak) как текущий минимум */}
else {
// переход к следующему уровню
k ++;
вычислить Sk;
}
} // end while продвижения вперёд
k --; // backtrack
cost = f_cost (a1,…,ak);
} // последнее сохраняемое решение имеет наименьшую стоимость
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
9

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

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

11. Пример (n = 5)

1
1
27
22
5
25
8
5
9
10
Матрица стоимостей
6
4
25
31
6
17
4
5
25 40 31 27
2 5
4 9
15 5 22
3
3
1
17 30 25
6
1
50 24
6
8
10
3 19 15
40
19
7 50
30
1
24
09.02.2016
2
2
7
Cij – убыток (расходы) при
переезде из i в j
Метод ветвей и границ
Задача коммивояжёра
11

12.

Дано: 1. n – количество городов
2. C = {Cij} i,j=1…n – матрица стоимостей
Найти: маршрут объезда всех городов (каждого по
одному разу) с возвратом в исходный пункт, при этом
стоимость поездки должна быть минимальной.
Permutation(1..n) Перестановка (1..n)
( (1), (2),..., (n)),
i, j {1..n}, i j : (i ) ( j ), (i ) {1..n}
n 1
J ( ) C ( i ), ( i 1) C ( n ), (1)
i 1
J min J ( ); arg min {J ( ' )}
*
Pn
09.02.2016
' Pn
Метод ветвей и границ
Задача коммивояжёра
12

13. Метод ветвей и границ в ЗК

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

14. Ветвление

Yk={(i1, j1), …,(ink, jnk)}
Xk = (Yk, Zk)
Включённая
дуга
(i, j)
(i, j)
YLeft(k) = Yk {(i, j)},
ZLeft(k) = Zk {(j, i)},
Действия:
1) Вычёркивание i-й строки и
j-го столбца (размер
матрицы уменьшается на 1)
2) добавление в текущее
решение (i, j)
3) запрет (j, i)
09.02.2016
Исключённая
дуга
YRight(k) = Yk,
ZRight(k) = Zk {(i, j)}
Yk – множество
включённых в
маршрут дуг;
Zk – множество
исключённых дуг
Метод ветвей и границ
Задача коммивояжёра
14

15. Операция «приведения матрицы»

1)
По строкам:
для i 1..n:
gi = min {Cij: j 1..n}
gi – минимальная сумма, достаточная
для выезда куда-либо из города i
По столбцам:
для j 1..n:
hj = min {(Cij - gi): i 1..n}
hi – минимальная сумма, достаточная
для въезда откуда-либо в город j
i
2)
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
j
15

16.

Приведённая матрица
C*ij = Cij – gi – hj 0
i 1..n gi + j 1..n hj = d
d – нижняя граница стоимости любого решения, не
зависит от , т.к. каждый город
посещается ровно один раз.
Т.о.
n 1
J ( ) C
*
( i ), ( i 1)
C
*
( n ), (1)
d d
i 1
Стоимость по приведённой матрице изменилась, но
оптимальное решение останется тем же (стоимость всех
допустимых маршрутов уменьшена на одну и ту же
величину)
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
16

17. Пример Вычитание по строкам

1
2
3
4
5
1 25 40 31 27 - 25
17 30 25
-5
6
1
-1
4 9
50 24
6
-6
5 22
8
10
-7
2 5
3 19 15
7
- 44
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
17

18. Вычитание по столбцам

1
2
3
4
5
1
0
15
6
2
2 0
12 25 20
3 18 14
5
0
d = 44 + 3 = 47
4 3
44 18
0
5 15
1
Нижняя граница
стоимости
любого решения
0
3
-3
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
18

19. Результат операции приведения матрицы

Результат операции приведения мат рицы
1
2
3
4
5
1
0
15
3
2
2 0
12 22 20
3 18 14
2
0
4 3
44 18
0
5 15
1
0
09.02.2016
0
Метод ветвей и границ
Задача коммивояжёра
В каждой строке
и в каждом
столбце имеется
хотя бы один 0
Нижняя граница
стоимости любого
решения d = 47
19

20. Включение дуги i-j (левая ветвь дерева) Например, 3-5

Действия над матрицей:
1) Вычёркивание i-й
строки и j-го
столбца (размер
матрицы
уменьшается на 1)
2) запрет (j, i): Cji := +
3) Затем новая операция
приведения
09.02.2016
1
2
3
4
5
1
0
15
3
2
2 0
12 22 20
2
0
4 3
44 18
0
5 15
1
0
3 18 14
Метод ветвей и границ
Задача коммивояжёра
0
+
20

21. Вычёркивание 3-й строки и 5-го столбца (размер матрицы уменьшается : 44 вместо 55)

Вычёркивание 3-й строки и 5-го столбца
(размер матрицы уменьшается : 4 4 вместо 5 5)
1
2
3
4
5
1
1
0
15
3
2
1
0 153 3
2 0
12 22 20
2 0
120 22
2
0
4 30 4441 183
4 3
44 18
0
5 15
5 15
1
0
3 18 14
0
2
1
3
- 12
4
-3
0
- 15
Новый шаг операции приведения
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
21

22. Исключение дуги i-j (правая ветвь дерева) Например, 3-5

Действия над
матрицей:
1) запрет (i, j): Cij := +
2) Затем новая
операция
приведения
Новая нижняя
граница стоимости
любого решения
d = 47 + 2 = 49
d = 2
09.02.2016
1
2
3
4
5
1
0
15
3
2
2 0
12 22 20
2
4 3
44 18
0
5 15
1
0
3 18 14
Метод ветвей и границ
Задача коммивояжёра
0
-2
22

23. После ветвления по дуге (3,5)

1
1
2*
3*
4*
5*
(3,5)
1
1
2*
4*
5*
2
*
*
*
3
*
*
*
09.02.2016
2
*
*
*
*
3
*
*
*
*
4
*
*
*
*
5
*
*
*
*
62=47+15
47
(3,5)
4
*
*
*
49=47+2
1
1
2*
3*
4*
5*
Метод ветвей и границ
Задача коммивояжёра
2
*
*
*
*
3
*
*
*
*
4
*
*
*
*
5
*
*
*
23

24. Какое ветвление сделать на первом шаге ?

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

25. Кандидаты на ветвление (включение-исключение)

d = 3
d = 15
1
2
3
4
5
1
0
15
3
2
2 0
12 22 20
2
0
d = 2
4 3
44 18
0
d = 3
5 15
1
0
3 18 14
0
d = 12
09.02.2016
d = 2
Метод ветвей и границ
Задача коммивояжёра
25

26. Эвристика*: выбор дуги для ветвления

При переходе в правую ветвь новая нижняя граница
стоимости любого решения в этой ветви есть d + d.
В нашем примере для нулевых элементов матрицы
рассматриваются варианты:
(i, j)
d
Максимум
09.02.2016
(1,2) (2,1) (3,5) (4,5) (5,3) (5,4)
3
15
2
3
12
2
Если Cij 0, то d = 0 (!).
Метод ветвей и границ
Задача коммивояжёра
26

27. Эвристика: выбор дуги для ветвления

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

28. Эвристика:

Рассмотрим множество пар ( , ), таких, что 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 – индексы матрицы
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
28

29. Итак, в примере, следуя указанной эвристике, выбирается ребро (2, 1) Левая ветвь (включая (2, 1))

1
2
3
4
5
2
3
4
5
1
0
15
3
2
1
15
3
2
2 0
12 22 20
3 14
2
0
2
0
4 44 18
0
4 3
44 18
0
5 1
0
5 15
1
0
-1
3 18 14
09.02.2016
0
Метод ветвей и границ
Задача коммивояжёра
0
-2
-3
29

30. После ветвления по дуге (2,1)

1
1
2*
3*
4*
5*
(2,1)
1
3
4
5
2
*
*
*
3
*
*
*
4
*
*
*
5
*
*
*
2
*
*
*
*
3
*
*
*
*
4
*
*
*
*
5
*
*
*
*
50=47+3
47
(2,1)
Рассмотрим
продолжение
левой ветви
62=47 + 15
1
1
2
3*
4*
5*
2
*
*
*
*
3
*
*
*
*
4
*
*
*
*
5
*
*
*
*
(через слайд)
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
30

31. Правая ветвь (исключая (2, 1))

1
2
3
4
5
1
2
3
4
5
1
0
15
3
2
1
0
15
3
2
2
12 22 20 - 12
2
0
10
8
2
0
3 15 14
2
0
4 3
44 18
0
4 0
44 18
0
5 15
1
0
5 12
1
0
3 18 14
-3
09.02.2016
0
0
- 15
Метод ветвей и границ
Задача коммивояжёра
31

32. Поддерево от ветки (2, 1)

(2, 1)
50
(4, 5)
d = 13
09.02.2016
(4, 5)
68=50+1
8
2
3
4
5
1
13
1
0
d = 1
3 13
2
0
d = 2
4 43 18
0
d = 18
5 0
0
0
Метод ветвей и границ
Задача коммивояжёра
32

33. Левая ветвь (включая (4, 5))

2
3
4
3
4
5
1 13
1 -1
1 13
1
0
3 13
2 -2
3 13
2
0
5 0
0
4 43 18
0
2
3
4
5 0
1 12
0
3 11
0
5 0
0
2
09.02.2016
0
0
Метод ветвей и границ
Задача коммивояжёра
53=50+3
33

34. Правая ветвь (исключая (4, 5))

2
3
4
5
2
3
4
5
1 13
1
0
1
13
1
0
3 13
2
0
3 13
2
0
4 43 18
- 18
4 25
0
5 0
5 0
0
0
0
0
68=50+18
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
34

35.

(2, 1)
50
(4, 5)
(4, 5)
53=50+3
2
3
4
1 12
0
3 11
0
5 0
0
09.02.2016
68=50+1
8
Кандидаты на ветвление узла (4, 5):
(1, 4) : d = 12
(5, 3) : d = 12
Метод ветвей и границ
Задача коммивояжёра
35

36. Поддерево от ветки (4, 5)

(4, 5)
53
(1, 4)
(1, 4)
65=53+12
53=50+3
2
3
4
2
3
4
1 12
0
1
0
3 11
0
5 0
0
3 11
0 + запрет (4, 1)
5 0
0
09.02.2016
???
Метод ветвей и границ
Задача коммивояжёра
36

37. Запрет (4, 1) ???

Частичное решение (2,1), (4,5), (1,4) или
2–1–4–5
Запретить нужно (5, 2) !
2
3
2
3
3 11
3 0
5
0
5
0
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
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
37

38. К этому моменту

Все решения
47
(2,1)
50
(4,5)
53
(1,4)
(5,3)
(1,4)
64
(2,1)
62
(4,5)
68
65
(5,3)
75=64+11
1
2
3
4
5
1
0
*
*
*
2
0
*
*
3 *
*
*
0
4 0
*
*
0
5 *
*
0
0
(3,2)
64
2–1–4–5–3–2
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
38

39. Ветвление узла (2,1)

d = 3
d = 8
Правая ветвь ((4,1))
1
2
3
4
5
1
2
3
4
5
1
0
15
3
2
1
0
15
3
2
2
0
10
8
2
0
10
8
3 15 14
2
0 d = 2
3 15 14
2
0
4 0
44 18
0 d = 0
4 44 18
0
5 12
1
0
5 12
0
0
d = 12 d = 0
09.02.2016
d = 2
Метод ветвей и границ
Задача коммивояжёра
1
0
- 12
74 = 62 + 12
39

40. Поддерево от ветки (2, 1)

(2, 1)
62
(4, 1)
(4, 1)
62
см.
09.02.2016
74=62+12
Метод ветвей и границ
Задача коммивояжёра
40

41. (4,1) – левая ветвь узла (2,1)

1
2
3
4
5
2
1
0
15
3
2
2
0
10
3 15 14
4
5
1 0
15
2
8
2
0
10
8
2
0
3 14
2
0
4 0
44 18
0
5 1
0
5 12
1
09.02.2016
0
0
Метод ветвей и границ
Задача коммивояжёра
3
0
d = 0
41

42. Ветвление узла (4,1)

(4, 1)
62
(2, 3)
??
d = 3
d = 8
09.02.2016
d = 0
(2, 3)
70=62+8
2
3
4
5
1 0
15
2
2
0
10
8
3 14
2
0 d = 4
5 1
0
0
Метод ветвей и границ
Задача коммивояжёра
d = 2
42

43. (2, 3) – левая ветка узла (4,1)

2
3
4
5
2
4
5
1 0
15
2
1 0
2
2
0
10
8
3
2
0
3 14
2
0
5 1
0
5 1
0
0
d = 0
d = 62
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
43

44. Ветвление узла (2,3)

(2, 3)
62
(3, 5)
d = 3
(3, 5)
2
4
5
1 0
2
3
2
0
5 1
0
66=62+4
d = 4
d = 3
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
44

45. Ветвление узла (2,3)

(2, 3)
62
(3, 5)
(3, 5)
66=62+4
62
2
4
5
1 0
2
3
2
0
5 1
0
09.02.2016
Решение + (1,2) + (5,4)
Т.о. (4,1), (2,3), (3,5), (1,2), (5,4)
или
1–2–3–5–4–1
Метод ветвей и границ
Задача коммивояжёра
45

46. Итак

Все решения
47
(2,1)
50
(4,5)
53
(1,4)
(5,3)
(1,4)
64
(5,3)
75=64+11
(3,2)
64
2–1–4–5–3–2
09.02.2016
(2,1)
65
(4,5)
62
(4,1)
68 (2,3)
62
(3,5)
62
62
74
70
66
62
1–2–3–5–4–1
Метод ветвей и границ
Задача коммивояжёра
46

47. Сложность алгоритма

Сложность точного алгоритма ЗК (методом ВиГ)
в среднем (при «случайных» матрицах
стоимостей)
Cn, где C 1.26
Эмпирический результат (опытным путём)
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
47

48. Приближённые решения (не минимальной стоимости)

Зачем нужны приближённые решения?
1) «Быстрые» решения
2) Для оценки границ при поиске
точного решения!
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
48

49. Приближённые решения (не минимальной стоимости)

1. Алгоритм ближайшего соседа (АБС)
Начиная с любого города, выбираем на каждом шаге следующий
город, стоимость проезда в который из данного города минимальна
1
2
3
4
5
1
25 40 31 27
2 5
3 19 15
17 30 25 совпадает со стоимостью
оптимального решения (!).
6
1
4 9
50 24
6
5 22
8
09.02.2016
1) 1 – 2 – 3 – 5 – 4 – 1: стоимость
= 25+17+1+10+9 = 62
7
10
Если элемент матрицы (4,1)
заменить на 9+x, то стоимость
решения АБС станет 62+x, где x
любое число (!)
Метод ветвей и границ
Задача коммивояжёра
49

50. Примеры обходов АБС

2) 2 – 1 – 5 – 3 – 4 – 2 : стоимость = 5+27+7+6+50= 95
3) 3 – 5 – 2 – 1 – 4 – 3 : стоимость = 1+8+5+31+24= 69
1
2
3
4
5
1
25 40 31 27
2 5
17 30 25
6
1
4 9
50 24
6
5 22
8
10
3 19 15
09.02.2016
7
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

51. Ещё пример: n = 6 Оптимальное решение 1 – 4 – 3 – 5 – 6 – 2 – 1. Стоимость = 16+25+5+5+5+7 = 63

1
2
3
4
5
6
1
27 43 16 30 26
2 7
16
3 20 13
1
30 25 2) 2 – 4 – 5 – 6 – 3 – 1 – 2 :
35 5 0 Стоимость = 1+18+5+5+20+27
18 18 = 76
5 12 46 27 48
5
6 23
5
09.02.2016
Стоимость = 16+16+16+0+5+12
= 65
4 21 16 25
5
1) 1 – 4 – 2 – 3 – 6 – 5 – 1 :
5
9
3) А: 3 – 6 – 2 – 4 – 5 – 1 – 3 :
Стоимость = 0+5+1+18+12+43
= 79
Метод ветвей и границ
Задача коммивояжёра
51

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

3) Б: 3 – 6 – 5 – 1 – 4 – 2 – 3 :
стоимость =
0+5+12+16+16+16 = 65 (см. 1)
1
2
3
4
5
6
1
27 43 16 30 26
2 7
16
1
30 25
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
4) 4 – 2 – 1 – 6 – 3 – 5 – 4 :
Стоимость = 16+7+26+5+5+48
= 107
5) А: 5 – 6 – 3 – 2 – 4 – 1 – 5 :
Стоимость = 5+5+13+1+21+30
= 75
5) Б: 5 – 6 – 2 – 4 – 1 – 3 – 5 :
Стоимость = 5+5+1+21+43+5
= 80
6) А: 6 – 2 – 4 – 5 – 1 – 3 – 6 :
Стоимость = 5+1+18+12+43+0
= 79 (см. 3А)
6) Б: 6 – 3 – 5 – 1 – 4 – 2 – 6 :
Стоимость = 5+5+12+16+16+25
= 79 (см. 3А)
6) В: 6 – 5 – 1 – 4 – 2 – 3 – 6 :
Стоимость = 5+12+16+16+16+0
= 65 (см. 3Б)
Итак, 65, 75, 76, 79, 80, 107
Метод ветвей и границ
Задача коммивояжёра
52

53. Оценка степени приближения алгоритма ближайшего соседа (АБС)

Nn – маршрут АБС, Nn – его длина (стоимость).
On – оптимальный маршрут,
On – его длина (стоимость).
Утверждение. Если матрица {Cij} – (а) симметрична и
(б) удовлетворяет неравенству треугольника
то
Cij Cik + Ckj , i, j, k,
Nn 1
2 ( log 2 n 1).
On
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
53

54. 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),
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
54

55. Пример: n = 6 Оптимальное решение 1 – 4 – 3 – 5 – 6 – 2 – 1. Стоимость = 16+25+5+5+5+7 = 63

1
Пример: n = 6
Оптимальное решение 1 – 4 – 3 – 5 – 6 – 2 – 1.
Стоимость = 16+25+5+5+5+7 = 63
1) 1 – 4 – 2 – 3 – 6 – 5 – 1 :
2 3 4 5 6 Стоимость = 16+16+16+0+5+12
= 65 (совпадает с АБС !)
27 43 16 30 26 2) 2 – 3 – 6 – 5 – 1 – 4 – 2 :
2 7
16
1
3 20 13
35
4 21 16 25
1
30 25
Стоимость = 16+0+5+12+21+16
= 70
18 18 3) 3 – 6 – 2 – 1 – 4 – 5 – 3 :
5
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
0+5+7+16+18+27= 73
5) 5 – 6 – 3 – 2 – 1 – 4 – 5 :
5+5+13+7+16+18 = 64 !!
Метод ветвей и границ
Задача коммивояжёра
55

56. Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2

Пример получения обхода АВБГ
2–3–6–5–1–4–2
1
2
3
4
5
6
1
27 43 16 30 26
2 7
16
1
30 25
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
56

57. Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2

Пример получения обхода АВБГ
2–3–6–5–1–4–2
1
2
3
4
5
6
0) Стартовый город: 2
Цепочка: 2 -2
1
27 43 16 30 26 Ближайший к цепочке город: 4
2 7
(цена перехода от цепочки до
30 25
города =1)
16
1
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
57

58. Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2

Пример получения обхода АВБГ
2–3–6–5–1–4–2
1
2
3
4
5
6
1) Добавляется город 4.
Цепочка: 2-4 -2
1
27 43 16 30 26 Ближайший к цепочке город: 1
2 7
(цена перехода от цепочки до
30 25
города =7)
16
1
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
58

59. Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2

Пример получения обхода АВБГ
2–3–6–5–1–4–2
1
2
3
4
5
6
2) Добавляется город 1.
Цепочка: 2-1-4 -2
1
27 43 16 30 26 Ближайший к цепочке город: 3
2 7
(цена перехода от цепочки до
30 25
города =16)
16
1
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
59

60. Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2

Пример получения обхода АВБГ
2–3–6–5–1–4–2
1
2
3
4
5
6
3) Добавляется город 3.
Цепочка: 2-3-1-4 -2
1
27 43 16 30 26 Ближайший к цепочке город: 6
2 7
(цена перехода от цепочки до
30 25
города =0)
16
1
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
60

61. Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2

Пример получения обхода АВБГ
2–3–6–5–1–4–2
1
2
3
4
5
6
4) Добавляется город 6.
Цепочка: 2-3-6-1-4 -2
1
27 43 16 30 26 Ближайший к цепочке город: 5
2 7
(цена перехода от цепочки до
30 25
города =5)
16
1
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
61

62. Пример получения обхода АВБГ 2 – 3 – 6 – 5 – 1 – 4 – 2

Пример получения обхода АВБГ
2–3–6–5–1–4–2
1
2
3
4
5
6
1
27 43 16 30 26
2 7
16
1
30 25
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
5) Добавляется город 5.
Цепочка: 2-3-6-5-1-4 -2
Метод ветвей и границ
Задача коммивояжёра
62

63. Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3

Пример получения обхода АВБГ
3–6–2–1–4–5–3
1
2
3
4
5
6
1
27 43 16 30 26
2 7
16
1
30 25
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
63

64. Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3

Пример получения обхода АВБГ
3–6–2–1–4–5–3
1
2
3
4
5
6
0) Стартовый город: 3
Цепочка: 3 -3
1
27 43 16 30 26 Ближайший к цепочке город: 6
2 7
(цена перехода от цепочки до
30 25
города =0)
16
1
3 20 13
35
5
4 21 16 25
18 18
0
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
64

65. Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3

Пример получения обхода АВБГ
3–6–2–1–4–5–3
1
1
2
3
4
5
6
27 43 16 30 26 Ближайшие к цепочке города:
2, 5 (цена перехода от цепочки
30 25
до города =5)
16
1
3 20 13
35
5
4 21 16 25
18 18
2 7
1) Добавляется город 6
Цепочка: 3-6 -3
01
5 12 46 27 48
5
6 23
5
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
65

66. Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3

Пример получения обхода АВБГ
3–6–2–1–4–5–3
1
2
3
4
5
6
2) Добавляется город 5
Цепочка: 3-6-5 -3
1
27 43 16 30 26 Ближайший к цепочке город: 2
2 7
(цена перехода от цепочки до
30 25
города =5)
16
1
3 20 13
35
5
4 21 16 25
18 18
01
5 12 46 27 48
5
6 23
52
5
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
66

67. Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3

Пример получения обхода АВБГ
3–6–2–1–4–5–3
1
2
3
4
5
6
3) Добавляется город 2
Цепочка: 3-6-2-5 -3
1
27 43 16 30 26 Ближайший к цепочке город: 4
2 7
(цена перехода от цепочки до
30 25
города =1)
16
1
3 20 13
35
5
4 21 16 25
18 18
01
5 12 46 27 48
5
6 23 53
52
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
67

68. Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3

Пример получения обхода АВБГ
3–6–2–1–4–5–3
1
2
3
4
5
6
4) Добавляется город 4
Цепочка: 3-6-2-4-5 -3
1
27 43 16 30 26 Ближайший к цепочке город: 1
2 7
(цена перехода от цепочки до
30 25
города =7)
16 14
35
5
4 21 16 25
18 18
3 20 13
01
5 12 46 27 48
5
6 23 53
52
09.02.2016
5
9
Метод ветвей и границ
Задача коммивояжёра
68

69. Пример получения обхода АВБГ 3 – 6 – 2 – 1 – 4 – 5 – 3

Пример получения обхода АВБГ
3–6–2–1–4–5–3
1
2
3
4
5
6
1
27 43 16 30 26
2 75
16 14 30 25
35
5
4 21 16 25
18 18
3 20 13
01
5 12 46 27 48
5
6 23 53
52
09.02.2016
5) Добавляется город 1
Цепочка: 3-6-2-1-4-5 -3
5
9
Метод ветвей и границ
Задача коммивояжёра
69

70. Оценка степени приближения АВБГ

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

71. Сложность приближённых алгоритмов

АБС C1n2
АВБГ C2n2, если для каждого города, не
включённого в маршрут, хранить данные о
ближайшем к нему из уже включённых в
маршрут. На каждом шаге эти данные
корректировать за счёт нового включённого.
Ест ь и другие приближённые решения
(см. след. раздел –
минимальное ост овное дерево графа)
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
71

72.

КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
09.02.2016
Метод ветвей и границ
Задача коммивояжёра
72
English     Русский Rules