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

Июль 24, 2022

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

Содержание

2. 16.02.2016 Динамическое программирование АНАЛОГИИ Решение методом динамического программирования Задачи: Перемножение цепочки матриц Оптимальные БДП Задача Х
3. 16.02.2016 Динамическое программирование Оценка количества узлов дерева Оценить количество узлов дерева в общем случае можно подсчётом
4. 16.02.2016 Динамическое программирование Начальное условие p1 = 1. Далее p2 = p1 p1 = 1, p3
5. 16.02.2016 Динамическое программирование Несколько первых чисел Каталана Ср. Сn –1 и (n3 – n)/3 Например, при
6. 16.02.2016 Динамическое программирование Число bn структурно различных бинарных деревьев с n узлами bk bn − k
7. 16.02.2016 Динамическое программирование b2 = b0 b1 + b1 b0 = 2, b3 = b0 b2
8. Решение методом динамического программирования Структура оптимального решения Рекуррентное соотношение Вычисление оптимальной стоимости (по рекуррентному соотношению) Построение
9. 16.02.2016 Динамическое программирование Задача: оптимальная триангуляция выпуклого многоугольника
10. 16.02.2016 Динамическое программирование Триангуляция (диагонали не пересекаются внутри многоугольника) Задача: оптимальная триангуляция выпуклого многоугольника Выпуклый n-угольник
11. 16.02.2016 Динамическое программирование На треугольниках определена весовая функция w(Δvivjvk) Например, w(Δv1v2v3) = ⎪v1v2⎪+⎪v2v3⎪ +⎪v2v3⎪ Задача: оптимальная
12. 16.02.2016 Динамическое программирование Количество способов триангуляции Вершин n, диаг. = n – 3 , треуг. =
13. 16.02.2016 Динамическое программирование Количество способов триангуляции n = 6, диаг. =3, треуг. = 4, вариантов =
14. 16.02.2016 Динамическое программирование Рекуррентная формула для веса оптимальной триангуляции многоугольника (ОТМ), 1 mij – вес ОТМ
15. Динамическое программирование Вычисление таблиц: mi,i+1 = 0, {при i=1..n-1} mi,i+2 = w(Δi,i+1,i+2), {при i=1..n-2} mi,i+3 =…
16. 16.02.2016 Динамическое программирование Рекуррентная формула для веса оптимальной триангуляции многоугольника (ОТМ), 2 mij – вес ОТМ
17. 16.02.2016 Динамическое программирование Упражнения Доказать, что триангуляция n–угольника содержит n-2 треугольника и n-3 диагоналей. Пусть вес
18. 16.02.2016 Динамическое программирование Связь задач 1 2 3 4 5 0 M1 M2 M3 M4 M5
19. 16.02.2016 Динамическое программирование Связь задач 1 2 3 4 5 0 (M1 M2) (( M3 M4)
20. 16.02.2016 Динамическое программирование Триангуляции Деревья
21. 16.02.2016 Динамическое программирование 0 1 0 1 0 1 0 1 0 0 1 1 0
22. Преобразование «Ползущий червь» 16.02.2016 Динамическое программирование 0 1 0 0 1 1 Обход в глубину: от
23. Литература Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ : учеб./ М.: МЦМНО, 1999.
25. Скачать презентацию

Слайд 2

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

подсчёта и задачи оптимизации.
Например:
«Число различных расстановок скобок» и «Оптимальная расстановка»

Слайд 3

16.02.2016
Динамическое программирование
Оценка количества узлов дерева
Оценить количество узлов дерева в общем случае

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

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

т. е. число узлов в дереве перебора есть экспоненциальная функция от n.

Из лекции про перемножение матриц

Слайд 5

16.02.2016
Динамическое программирование
Несколько первых чисел Каталана
Ср. Сn –1 и (n3 – n)/3
Например,

при n = 10

Из лекции про перемножение матриц

Слайд 6

16.02.2016
Динамическое программирование
Число bn структурно различных бинарных деревьев с n узлами

bn − k − 1

k ∈ 0..(n – 1)

Это рекуррентное уравнение с точностью до обозначений совпадает с рекуррентным уравнением, получающимся при подсчёте числа расстановок скобок в произведении n сомножителей
(см. лекцию 16, слайд 16).

Из лекции про БДП

Слайд 7

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

Из лекции про БДП

Слайд 8

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

соотношению)
Построение оптимального решения
Проиллюстрировать на предыдущих примерах

16.02.2016

Динамическое программирование

Слайд 9

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

Слайд 10

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

n-угольник
Число диагоналей: n – 3
Число треугольников: n – 2

7-угольник
Диагоналей: 4
Треугольников: 5

Слайд 11

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

+⎪v2v3⎪

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

Требуется найти триангуляцию, для которой сумма весов Δ-ков будет минимальной

Слайд 12

16.02.2016
Динамическое программирование
Количество способов триангуляции
Вершин n, диаг. = n – 3 ,

треуг. = n – 2

n = 4, диаг. =1, треуг. = 2, вариантов = 2

n = 5, диаг. =2, треуг. = 3, вариантов = 5

Слайд 13

16.02.2016
Динамическое программирование
Количество способов триангуляции
n = 6, диаг. =3, треуг. = 4, вариантов

= 14

d6 = d2d5 + d3d4 + d4d3 + d5d2

Слайд 14

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

вес ОТМ (vi,vi+1,…,vj)
m1n – вес ОТМ (v1,v2,…,vn)
Для двуугольника mi,i+1 = w(vi-1,vi)=0

Mij = многоугольник (vi, vi+1,…, vj), iТ.е. M1n = многоугольник (v1, v2,…, vn)

Слайд 15

Динамическое программирование
Вычисление таблиц:
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

16.02.2016

Динамическое программирование

Слайд 16

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

вес ОТМ (vi-1,vi,…,vj)
m1n – вес ОТМ (v0,v1,…,vn)
Для двуугольника mii = w(vi-1,vi)=0
Время ≈С1n3, память ≈С2n2

Mij = многоугольник (vi-1, vi,…, vj), iТ.е. M1n = многоугольник (v0, v2,…, vn), т.е. это (n+1)-углнк

В таком виде почти полное сходство с прежними примерами!

Слайд 17

16.02.2016
Динамическое программирование
Упражнения
Доказать, что триангуляция n–угольника содержит n-2 треугольника и n-3 диагоналей.
Пусть

вес треугольника = его площади. Можно ли упростить алгоритм поиска ОТМ?
Весовая функция определена на множестве диагоналей многоугольника. ОТМ — сумма весов диагоналей минимальна. Как свести эту задачу к рассмотренной?

Задание. Рассмотрите полностью какой-либо пример с 5- или 6-угольниками.
(для тренировки к ТК)

Слайд 18

16.02.2016
Динамическое программирование
Связь задач
1
2
3
4
5
0
M1
M2
M3
M4
M5
(M1 M2) (( M3 M4) M5)
M1
M2
M3
M4
M5
M1 M2
M3 M4
(

M3 M4) M5

(M1 M2) (( M3 M4) M5)

Слайд 19

16.02.2016
Динамическое программирование
Связь задач
1
2
3
4
5
0
(M1 M2) (( M3 M4) M5)
M1
M2
M3
M4
M5
M1 M2
M3 M4
( M3

M4) M5

(M1 M2) (( M3 M4) M5)

w(Δvivjvk) = ri rj rk

Слайд 20

16.02.2016
Динамическое программирование
Триангуляции
Деревья

Слайд 21

16.02.2016
Динамическое программирование
0 1 0 1 0 1
0 1 0 0 1

0 0 1 1 0 1

0 0 0 1 1 1

0 0 1 0 1 1

Коды

Пути в решётке

Слоистая сеть (спец. вида)

Слайд 22

Преобразование «Ползущий червь»
16.02.2016
Динамическое программирование
0 1 0 0 1 1
Обход в глубину:

от узла влево – 0; вправо - 1

Слайд 23

Литература
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ :

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

16.02.2016

Динамическое программирование

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

Содержание

16.02.2016Динамическое программированиеОценка количества узлов дереваОценить количество узлов дерева в общем случае

16.02.2016Динамическое программированиеНачальное условие p1 = 1. Далее p2 = p1 p1 = 1, p3 = p1 p2 + p2 p1 = 2, p4 = p1 p3 + p2 p2 + p3 p1 = 5. Оказывается [7, с. 393],

16.02.2016Динамическое программированиеНесколько первых чисел КаталанаСр. Сn –1 и (n3 – n)/3 Например,

16.02.2016Динамическое программированиеЧисло bn структурно различных бинарных деревьев с n узлами

16.02.2016Динамическое программирование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

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

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

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

16.02.2016Динамическое программированиеКоличество способов триангуляцииВершин n, диаг. = n – 3 ,

16.02.2016Динамическое программированиеКоличество способов триангуляцииn = 6, диаг. =3, треуг. = 4, вариантов

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

Динамическое программированиеВычисление таблиц:mi,i+1 = 0, {при i=1..n-1}mi,i+2 = w(Δi,i+1,i+2), {при i=1..n-2}

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

16.02.2016Динамическое программированиеУпражненияДоказать, что триангуляция n–угольника содержит n-2 треугольника и n-3 диагоналей.Пусть

16.02.2016Динамическое программированиеСвязь задач123450M1M2M3M4M5 (M1 M2) (( M3 M4) M5)M1M2M3M4M5M1 M2M3 M4(

16.02.2016Динамическое программированиеСвязь задач123450(M1 M2) (( M3 M4) M5)M1M2M3M4M5M1 M2M3 M4( M3

16.02.2016Динамическое программированиеТриангуляцииДеревья

16.02.2016Динамическое программирование0 1 0 1 0 10 1 0 0 1

Преобразование «Ползущий червь» 16.02.2016Динамическое программирование0 1 0 0 1 1Обход в глубину:

ЛитератураКормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ :

Похожие презентации

16.02.2016
Динамическое программирование
Оценка количества узлов дерева
Оценить количество узлов дерева в общем случае

16.02.2016
Динамическое программирование
Начальное условие p1 = 1. Далее
p2 = p1 p1 = 1,
p3 = p1 p2 + p2 p1 = 2,
p4 = p1 p3 + p2 p2 + p3 p1 = 5.
Оказывается [7, с. 393],

16.02.2016
Динамическое программирование
Несколько первых чисел Каталана
Ср. Сn –1 и (n3 – n)/3
Например,

16.02.2016
Динамическое программирование
Число bn структурно различных бинарных деревьев с n узлами

16.02.2016
Динамическое программирование
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

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

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

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

16.02.2016
Динамическое программирование
Количество способов триангуляции
Вершин n, диаг. = n – 3 ,

16.02.2016
Динамическое программирование
Количество способов триангуляции
n = 6, диаг. =3, треуг. = 4, вариантов

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

Динамическое программирование
Вычисление таблиц:
mi,i+1 = 0, {при i=1..n-1}
mi,i+2 = w(Δi,i+1,i+2), {при i=1..n-2}

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

16.02.2016
Динамическое программирование
Упражнения
Доказать, что триангуляция n–угольника содержит n-2 треугольника и n-3 диагоналей.
Пусть

16.02.2016
Динамическое программирование
Связь задач
1
2
3
4
5
0
M1
M2
M3
M4
M5
(M1 M2) (( M3 M4) M5)
M1
M2
M3
M4
M5
M1 M2
M3 M4
(

16.02.2016
Динамическое программирование
Связь задач
1
2
3
4
5
0
(M1 M2) (( M3 M4) M5)
M1
M2
M3
M4
M5
M1 M2
M3 M4
( M3

16.02.2016
Динамическое программирование
Триангуляции
Деревья

16.02.2016
Динамическое программирование
0 1 0 1 0 1
0 1 0 0 1

Преобразование «Ползущий червь»
16.02.2016
Динамическое программирование
0 1 0 0 1 1
Обход в глубину:

Литература
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ :