Построение и анализ алгоритмов. Динамическое программирование. Аналогии. (Лекция 4.3) презентация

Построение и анализ алгоритмов Лекция 4.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.

Начальное условие 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 справедливо

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. Ранее были приведены общая формула для чисел Каталана и асимптотическое соотношение

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

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

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

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

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

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

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

Динамическое программирование Вычисление таблиц: mi,i+1 = 0, {при i=1..n-1} mi,i+2 = w(i,i+1,i+2), {при i=1..n-2} mi,i+3 =… … mi,i+n-2  m1,n-1 , m2,n {при i=1, 2} mi,i+n-1 = m1n {при i=1} Время С1n3, память С2n2

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

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

Связь задач

Связь задач

Преобразование «Ползущий червь»

Литература Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ : учеб./ М.: МЦМНО, 1999. – 960 с. (Классические учебники: Computer science). (Доп. тираж 2000 г., 2001 г., 2002 г.) [Опт.Трианг.] Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2007, 2009. – 1296 с. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 3-е издание.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2013. – 1328 с.

КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ