MO_PZ1_Elementy_DP

1. Динамическое программирование Беллмана

Пример :
v
6
8
5
11
7
2
Начало А
Конец Б
2
3
11
10
ИУС 2
4
4
5
3
10
8
h

2. Особенности решения ДП-задач

• Задача решается с конца
• Задача погружается во множество
аналогичных задач
• В результате получаем глобальные
оптимумы для всех
вспомогательных задач
ИУС «читается» от начала к
• Решение
концу
• Многоэтапность и сепарабельность

3. Принцип оптимальности Беллмана

А
Б
Целевое множество
А
ИУС Оптимальная
Начальная точка
траектория

4. Алгоритм решения ДП-задач

14
14
8
8
15
6
15
6
8
21
5
9
23
2
18
4
15
0
2
10
ИУС
16
6
4
4
11
7
6 + 15 = 21
8 + 14 = 22
21 < 22
11
6
2
5
14
11
3
3
8
Глобальный
минимум = 18
Локальная
стратегия дает
10 2+7+10+2+4 =
25 что хуже 18
13
3