Динамическое программирование АНАЛОГИИ - презентация, доклад, проект скачать

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

Динамическое программирование АНАЛОГИИ, слайд №1

Динамическое программирование АНАЛОГИИ, слайд №2

Динамическое программирование АНАЛОГИИ, слайд №3

Динамическое программирование АНАЛОГИИ, слайд №4

Динамическое программирование АНАЛОГИИ, слайд №5

Динамическое программирование АНАЛОГИИ, слайд №6

Динамическое программирование АНАЛОГИИ, слайд №7

Динамическое программирование АНАЛОГИИ, слайд №8

Динамическое программирование АНАЛОГИИ, слайд №9

Динамическое программирование АНАЛОГИИ, слайд №10

Динамическое программирование АНАЛОГИИ, слайд №11

Динамическое программирование АНАЛОГИИ, слайд №12

Динамическое программирование АНАЛОГИИ, слайд №13

Динамическое программирование АНАЛОГИИ, слайд №14

Динамическое программирование АНАЛОГИИ, слайд №15

Динамическое программирование АНАЛОГИИ, слайд №16

Динамическое программирование АНАЛОГИИ, слайд №17

Динамическое программирование АНАЛОГИИ, слайд №18

Динамическое программирование АНАЛОГИИ, слайд №19

Динамическое программирование АНАЛОГИИ, слайд №20

Содержание ▲

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

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

Слайд 1

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

Построение и анализ алгоритмов Лекция 4.3 Динамическое программирование АНАЛОГИИ

Слайд 2

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

АНАЛОГИИ Решение методом динамического программирования Задачи: Перемножение цепочки матриц Оптимальные БДП Задача Х и т.п.

Слайд 3

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

Оценка количества узлов дерева Оценить количество узлов дерева в общем случае можно подсчетом всех возможных вариантов расстановок скобок в произведении матриц. Пусть 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.

Слайд 4

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

Начальное условие 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, где Сn =(2 k | k) / (k +1), а запись (n | m) обозначает биномиальный коэффициент (n | m) = n!/(m! (n – m)!). При больших значениях n справедливо

Слайд 5

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

Слайд 6

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

Слайд 7

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

b2 = b0 b1 + b1 b0 = 2, b2 = b0 b1 + b1 b0 = 2, b3 = b0 b2 + b1 b1 + b2 b0 = 5, b4 = b0 b3 + b1 b2 + b2 b1 + b3 b0 = = 5 + 2 + 2 + 5 = 14 Решением рекуррентного уравнения являются так называемые числа Каталана Сn, т. е. bn = Сn. Ранее (Лекция 13, слайды хх, хх) были приведены: общая формула для чисел Каталана и асимптотическое соотношение

Слайд 8

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

Решение методом динамического программирования Структура оптимального решения Рекуррентное соотношение Вычисление оптимальной стоимости (по рекуррентному соотношению) Построение оптимального решения Проиллюстрировать на предыдущих примерах

Слайд 9

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

Задача: оптимальная триангуляция выпуклого многоугольника

Слайд 10

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

Задача: оптимальная триангуляция выпуклого многоугольника Триангуляция (диагонали не пересекаются внутри многоугольника)

Слайд 11

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

Задача: оптимальная триангуляция многоугольника На треугольниках определена весовая функция w(vivjvk) Например, w(v1v2v3) = v1v2+v2v3 +v2v3

Слайд 12

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

Количество способов триангуляции

Слайд 13

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

Количество способов триангуляции

Слайд 14

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

Рекуррентная формула для веса оптимальной триангуляции многоугольника (ОТМ)

Слайд 15

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

Упражнения Доказать что триангуляция n – угольника содержит n-2 треугольника и n-3 диагоналей. Пусть вес треугольника = его площади. Можно ли упростить алгоритм поиска ОТМ? Весовая функция определена на множестве диагоналей многоугольника. ОТМ – сумма весов диагоналей минимальна. Как свести эту задачу к рассмотренной?