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

Разбиение на подзадачи в методе ветвей и границ:

Ω

Наличие перекрывающихся подзадач:

Ω

Принцип оптимальности для подзадач.
Говорят, что для задачи выполнен принцип оптимальности для

Задача о перемножении матриц.
Дано n матриц M1, M2, …, Mn
Матрица Mi

Пример:
M1 10 x 100
M2 100 x 5
M3 5 x 50
((M1 M2) M3)
M1 *M2

Обозначим Mi...j = MiMi+1…Mj
Mi...j = (Mi…Mk)*(Mk+1…Mj) для некоторого i<=kfij – минимальное

Псевдокод алгоритма:
for i = 1 to n do
fii = 0
i =

Перемножение матриц:
MULT (i, j)
if j > i then
X = MULT (i,

Численный пример:
n = 4

Разбиение на подзадачи:

1..4

1..1

2..4

1..2

3..4

1..3

4..4

2..2

3..4

2..3

4..4

1..1

2..2

3..3

4..4

1..1

2..3

1..2

3..3

3..3

4..4

2..2

3..3

2..2

3..3

1..1

2..2