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

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

Динамическое программирование, слайд №10

Динамическое программирование, слайд №11

Динамическое программирование, слайд №12

Динамическое программирование, слайд №13

Динамическое программирование, слайд №14

Динамическое программирование, слайд №15

Динамическое программирование, слайд №16

Динамическое программирование, слайд №17

Динамическое программирование, слайд №18

Динамическое программирование, слайд №19

Динамическое программирование, слайд №20

Динамическое программирование, слайд №21

Динамическое программирование, слайд №22

Динамическое программирование, слайд №23

Динамическое программирование, слайд №24

Динамическое программирование, слайд №25

Динамическое программирование, слайд №26

Динамическое программирование, слайд №27

Динамическое программирование, слайд №28

Динамическое программирование, слайд №29

Динамическое программирование, слайд №30

Динамическое программирование, слайд №31

Динамическое программирование, слайд №32

Динамическое программирование, слайд №33

Динамическое программирование, слайд №34

Динамическое программирование, слайд №35

Динамическое программирование, слайд №36

Динамическое программирование, слайд №37

Динамическое программирование, слайд №38

Динамическое программирование, слайд №39

Динамическое программирование, слайд №40

Динамическое программирование, слайд №41

Динамическое программирование, слайд №42

Динамическое программирование, слайд №43

Динамическое программирование, слайд №44

Содержание ▲

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

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

Слайд 1

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

Построение и анализ алгоритмов Лекция 3 Динамическое программирование

Слайд 2

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

Динамическое программирование Пример 1: путь минимальной стоимости в слоистой сети (дорог)

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

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

В общем случае

Слайд 8

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

Основные особенности метода ДП Рекуррентное соотношение Хранение таблиц Принцип оптимальности: Часть (например, f i – 1 (v)) оптимального решения fi(u) должна быть оптимальна

Слайд 9

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

Решение методом ветвей и границ

Слайд 10

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

Решение методом ветвей и границ

Слайд 11

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

Динамическое программирование. Пример 2: Задача о порядке перемножения матриц Рассмотрим произведение матриц M1  M2  M3  ...  Mn 1  Mn. Каждая матрица Mi имеет размер ri 1  ri. M1 (r0;r1)M2(r1;r2)M3(r2;r3)...Mn 1(rn  2;rn  1)Mn (rn  1;rn). Вычисление произведения двух матриц – размер первой n  p и размер второй p  m – требует n p m умножений их элементов: C (n;m) = A(n;p) × B(p;m) cij = k=1..p (aik * bkj ) для i 1..n, j 1..m

Слайд 12

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

Задача о порядке перемножения матриц Общее количество элементарных операций умножения, требуемое при вычислении произведения цепочки матриц, зависит от порядка, в котором производятся попарные умножения матриц. Требуется найти такой порядок перемножения матриц, который минимизирует общее количество элементарных операций умножения.

Слайд 13

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

Пример: M1  M2  M3  M4, Пример: M1  M2  M3  M4, где размер (M1) = 10  20, размер (M2) = 20  50, размер (M3) = 50  1, размер (M3) = 1  100.

Слайд 14

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

Рекуррентное соотношение Пусть mij – оптимальное количество умножений, требуемое для вычисления произведения цепочки матриц M(i, j) = Mi  Mi +1  ...  Mj 1  Mj, где 1 i  j  n. Очевидно, что M(i, i) = Mi и mii = 0, а m1n – соответствует решению задачи для исходной цепочки M(1, n). При 1 i  j  n справедливо :

Слайд 15

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

1) Заметим, что в правой части равенства разности индексов k – i и j – k –1 у слагаемых mik и mk +1, j меньше, чем разность индексов j – i в mij. 1) Заметим, что в правой части равенства разности индексов k – i и j – k –1 у слагаемых mik и mk +1, j меньше, чем разность индексов j – i в mij. Таким образом, рекуррентное соотношение следует решать, начиная с mii = 0 и последовательно увеличивая разность индексов j – i до тех пор, пока не получим m1n. 2) Удобно представлять результаты вычислений в виде таблицы. В этой таблице строка с номером l состоит из ячеек T(i, j), индексы которых связаны соотношением j – i = l. Т.е. j = i + l и T(i, j) = T(i, i + l).

Слайд 16

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

В ячейках таблицы T(i, j) хранятся вычисленные значения mij и те значениея qij = k в диапазоне i  k  j, при которых был получен Min { mik + mk +1, j + ri 1  rk  rj }.

Слайд 17

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

Алгоритм вычисляет оптимальное значение m1n и заполняет таблицу T по строкам сверху вниз: for (i = 1; i < n; i++) m[i, i] = 0; //заполнение первой строки for l := 1 to n –1 do for i := 1 to n – l do begin j := i + l; {заполнение T(i, j):} m[i, j] := +; for k := i to j – 1 do begin s := m[i, k] + m [k +1,j] + ri 1 * rk * rj; if s  m[i, j] then begin m[i, j] := s; q[i, j] := k end { if } end { for k } end { for i }

Слайд 18

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

Алгоритм вычисляет оптимальное значение m1n и заполняет таблицу T по строкам сверху вниз: for (i = 1; i < n; i++) m[i][i] = 0; //заполнение первой строки табл. for (L = 1; L < n; L++) for (i = 1; i < n-L+1; i++) { j = i + L; // заполнение T(i, j): m[i][j] = +; for (k = i; k < j; k++) { s = m[i][k] + m[k+1][j] + r(i-1) * r(k) * r(j); if (s

Слайд 19

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

Характеристики алгоритма Алгоритм требует: порядка n 2/2 элементов памяти для хранения таблицы около n 3/3 выполнений тела внутреннего цикла. Пример см. далее

Слайд 20

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

Пример вычисления M1  M2  M3  M4 (см. слайд 13) Для заполнения строки таблицы при l = 1 вычислим последовательно m1,2 = m1,1 + m2,2 + r0  r1  r2 = 10  20  50 = 10 000, m2,3 = m2,2 + m3,3 + r1  r2  r3 = 20  50  1 = 1000, m3,4 = m3,3 + m4,4 + r2  r3  r4 = 50  1  100 = 5000. Здесь фактически минимум находить не требуется, так как тело цикла по k выполняется лишь один раз (при k = i ). Заполненная строка таблицы есть

Слайд 21

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

Строка таблицы при L= 2 Строка таблицы при L= 2 m1,3 = Min {m1k + mk +1,3 + r0  rk  r3  k = 1, 2} = = Min {m1,1 + m2,3 + r0  r1  r3 , m1,2 + m3,3 + r0  r2  r3} = = Min {0 + 1000 + 200, 10 000 + 0 + 500} = = Min{1200, 10 500} = 1200 (при k = 1), m2,4 = Min {m2k + mk +1,4 + r1 rk  r4 k = 2, 3} = = Min {m2,2 + m3,4 + r1  r2  r4 , m2,3 + m4,4 + r0  r2  r3} = = Min {0 + 5000 + 100 000, 1000 + 0 + 2000} = = Min{105 000, 3000} = 3000 (при k = 3)

Слайд 22

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

Последняя строка таблицы Последняя строка таблицы (из одной ячейки) Т (1, 4): m1,4 = Min { m1k + mk +1,4 + r0  rk  r4  k = 1, 2, 3} = = Min { m1,1 + m2,4 + r0  r1  r4, m1,2 + m3,4 + r0  r2  r4, m1,3 + m4,4 + r0  r3  r4 } = = Min {0 + 3000 + 20 000, 10 000 + 5000 + 50 000, 1200 + 0 + 1000} = = Min {23 000, 65 000, 2200} = 2200 (при k = 3).

Слайд 23

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

Вся таблица вычислена и имеет вид

Слайд 24

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

В общем случае порядок перемножения матриц легко определить рекурсивно. Пусть имеется функция перемножения двух матриц func Mult ( A, B: Matrix): Matrix. «Набросок» функции перемножения цепочки матриц: func MatrixSeqMult ( i, j: Index): Matrix; {i  j} global q: Tab_q; var k: Index; var A, B: Matrix; begin if i  j then begin k := q[i, j]; A := MatrixSeqMult ( i, k); B := MatrixSeqMult ( k +1, j); Return Mult(A, B) end else {i = j} Return Mi end {MatrixSeqMult}

Слайд 25

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

«Набросок» функции перемножения цепочки матриц: // Псевдокод Matrix MatrixSeqMult ( int i, int j) // i

Слайд 26

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

Полезно сравнить решение, полученное методом динамического программирования, с решением методом ветвей и границ. Полезно сравнить решение, полученное методом динамического программирования, с решением методом ветвей и границ. В рассмотренном примере возможны следующие 5 вариантов перемножения матриц M1  M2  M3  M4, а именно: M1  (M2  (M3  M4)), M1  ((M2  M3)  M4), (M1  M2)  (M3  M4), (M1  (M2  M3))  M4, ((M1  M2)  M3)  M4.

Слайд 27

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

Дерево перебора в методе ветвей и границ M(1,4) M1  M(2,4) M(1,2)  M(3,4) M(1,3)  M4 M2  M(3,4) M(2,3)  M4 M1  M2 M3  M4 M1  M(2,3) M(1,2)  M3 M3  M4 M2  M3 M2  M3 M1  M2

Слайд 28

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

Оценка количества узлов дерева Оценить количество узлов дерева в общем случае можно подсчетом всех возможных вариантов расстановок скобок в произведении матриц. Пусть pn – число вариантов расстановок скобок в произведении n сомножителей (включая самые внешние скобки). Например, для трех сомножителей abc имеем два варианта (a(bc)) и ((ab)c), а следовательно, p3 = 2. В общем случае, считая, что «последнее» по порядку умножение может оказаться на любом из n –1 мест, запишем следующее рекуррентное соотношение: pn = p1 pn –1 + p2 pn –2 + … + pn –2 p2 + p n –1 p1.

Слайд 29

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

Начальное условие p1 = 1. Далее Начальное условие p1 = 1. Далее p2 = p1 p1 = 1, p3 = p1 p2 + p2 p1 = 2, p4 = p1 p3 + p2 p2 + p3 p1 = 5. Оказывается [7, с. 393], что решением этого рекуррентного уравнения являются так называемые числа Каталана pn = Сn –1, где Сk =(2 k | k) / (k +1), а запись (n | m) обозначает биномиальный коэффициент (n | m) = n !/(m ! (n – m)!). См. также 1.6.10 и 1.7.4 в книге

Слайд 30

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

Тогда для чисел Каталана при больших значениях n справедливо Тогда для чисел Каталана при больших значениях n справедливо

Слайд 31

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

Слайд 32

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

Далее в следующую лекцию

Слайд 33

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

Пример 3. Оптимальные деревья поиска Ранее при рассмотрении БДП, как правило, предполагалось, что для поиска различные ключи предъявляются с равной вероятностью. Пусть теперь заранее известно, что некоторые ключи предъявляются чаще других. Тогда расположение «частых» ключей ближе к корню дерева сократит время их поиска и, возможно, среднее время поиска (по разным предъявлениям ключей).

Слайд 34

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

Пример дерева поиска из трех элементов a1

Слайд 35

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

Заданы вероятности предъявления элемента x для поиска: P (x = a1) = ; P (x = a2) = ; P (x = a3) = .

Слайд 36

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

Постановка задачи Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена: a1

Слайд 37

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

Постановка задачи (продолжение) Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0

Слайд 38

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

Постановка задачи (продолжение) Тогда среднее число (математическое ожидание) сравнений при поиске можно записать в виде где l (x) – уровень узла x (или длина пути от корня до узла x) в БДП. Здесь уровень узла определен так, что l (корень) = 0.

Слайд 39

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

Постановка задачи (продолжение) Такое дерево называют оптимальным БДП. Есть ли сходство этой задачи с задачей построения оптимального префиксного кода ?

Слайд 40

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

Напоминание Задача построения оптимального префиксного кода есть задача минимизации функции L = i =1..n wi li целочисленных положительных переменных (li)1n при заданном наборе (wi)1n и при условии (здесь не формализованном) выполнения свойства префиксности кода. Набор переменных (li)1n, минимизирующий L, определяет структуру дерева (кода).

Слайд 41

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

Итак, … Есть ли сходство этой задачи с задачей построения оптимального префиксного кода ? В чём сходство, в чём различие? Ответ.

Слайд 42

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

Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных деревьев с n узлами и выборе дерева с наименьшей стоимостью C0,n . Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных деревьев с n узлами и выборе дерева с наименьшей стоимостью C0,n . Однако поскольку (см. лекции про БДП) число bn структурно различных бинарных деревьев с n узлами есть , то этот способ вряд ли будет иметь практическую ценность. Оказывается, приемлемое по количеству вычислений решение данной задачи может быть получено методом динамического программирования.