Динамическое программирование АНАЛОГИИ

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

расстановка»

случае можно подсчетом всех возможных вариантов расстановок скобок в произведении

матриц.
Пусть 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.

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

с. 393], что решением этого рекуррентного уравнения являются так называемые числа

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

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

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

Например, при n = 10
Из лекции про перемножение матриц

bk
bn − k − 1
1
k ∈ 0..(n – 1)

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

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

5 = 14
Решением рекуррентного уравнения являются так называемые числа Каталана

Сn, т. е. bn = Сn.
Ранее (Лекция 13, слайды хх, хх) были приведены: общая формула для чисел Каталана и асимптотическое соотношение

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

рекуррентному соотношению)
Построение оптимального решения

Проиллюстрировать на предыдущих примерах
03.03.2014
Динамическое программирование

многоугольник
Невыпуклый многоугольник
диагонали

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

2

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

1

2

3

4

5

6

7

⎪v1v2⎪+⎪v2v3⎪ +⎪v2v3⎪
Задача: оптимальная триангуляция многоугольника
Требуется найти триангуляцию, для которой сумма

весов Δ-ков будет минимальной

v1

v2

v3

, треуг. = n – 2
n = 4, диаг.

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

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

4, вариантов = 14





5
5
2
2


1
1




d6 = d2d5 + d3d4 + d4d3 +

d5d2

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

Время

≈С1n3, память ≈С2n2

vi-1

vj

vk

и n-3 диагоналей.
Пусть вес треугольника = его площади. Можно ли

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

M4
( M3 M4) M5
(M1 M2) (( M3 M4) M5)

M3 M4) M5
(M1 M2) (( M3 M4) M5)
w(Δvivjvk) = ri

rj rk

1 1

0 0 1 1 0 1

0 0 0 1

1 1

0

1

0 0 1 0 1 1

Коды

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

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

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