Метод ветвей и границ - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

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

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

Общий алгоритм МВГ 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

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

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

Слайд 10

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

Пример (n = 5)

Слайд 11

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

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

Слайд 12

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

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

Слайд 13

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

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

Слайд 14

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

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

Слайд 15

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

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

Слайд 16

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

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

Слайд 17

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

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

Слайд 18

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

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

Слайд 19

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

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

Слайд 20

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

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

Слайд 21

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

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

Слайд 22

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

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

Слайд 23

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

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

Слайд 24

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

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

Слайд 25

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

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

Слайд 26

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

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

Слайд 27

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

Эвристика: Рассмотрим множество пар (,), таких, что 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

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

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

Слайд 29

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

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

Слайд 30

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

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

Слайд 31

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

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

Слайд 32

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

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

Слайд 33

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

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

Слайд 34

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

Слайд 35

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

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

Слайд 36

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

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

Слайд 37

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

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

Слайд 38

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

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

Слайд 39

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

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

Слайд 40

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

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

Слайд 41

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

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

Слайд 42

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

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

Слайд 43

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

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

Слайд 44

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

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

Слайд 45

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

Итак

Слайд 46

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

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

Слайд 47

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

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

Слайд 48

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

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

Слайд 49

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

Слайд 50

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

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

Слайд 51

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

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

Слайд 52

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

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

Слайд 53

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

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

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

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

Слайд 55

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

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

Слайд 56

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

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