Метод ветвей и границ. Задача коммивояжёра. (Лекция 2) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Метод ветвей и границ. Задача коммивояжёра. (Лекция 2). Доклад-сообщение содержит 72 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Метод ветвей и границ Branch-and-Bound Method Вариант поиска с возвращением. Каждое решение имеет стоимость. Требуется найти решение минимальной стоимости.

Слайд 3

Описание слайда:

Метод ветвей и границ Все решения 1 группа решений 2 группа решений 3 группа решений …

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Условия применимости метода ветвей и границ (МВГ) Для каждого частичного решения должна быть определена стоимость 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.

Слайд 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); } // последнее сохраняемое решение имеет наименьшую стоимость$

Описание слайда:

Общий алгоритм МВГ 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); } // последнее сохраняемое решение имеет наименьшую стоимость

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Пример (n = 5)

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

Приведённая матрица Приведённая матрица C*ij = Cij – gi – hj  0 i1..n gi + j1..n hj = d d – нижняя граница стоимости любого решения, не зависит от , т.к. каждый город посещается ровно один раз. Т.о.

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

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

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 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 – индексы матрицы

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

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

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

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

Слайд 41

Описание слайда:

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

Слайд 42

Описание слайда:

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

Слайд 43

Описание слайда:

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

Слайд 44

Описание слайда:

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

Слайд 45

Описание слайда:

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

Слайд 46

Описание слайда:

Итак

Слайд 47

Описание слайда:

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

Слайд 48

Описание слайда:

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

Слайд 49

Описание слайда:

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

Слайд 50

Описание слайда:

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

Слайд 51

Описание слайда:

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

Слайд 52

Описание слайда:

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

Слайд 53

Описание слайда:

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

Слайд 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),

Слайд 55

Описание слайда:

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

Слайд 56

Описание слайда:

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

Слайд 57

Описание слайда:

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

Слайд 58

Описание слайда:

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

Слайд 59

Описание слайда:

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

Слайд 60

Описание слайда:

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

Слайд 61

Описание слайда:

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

Слайд 62

Описание слайда:

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