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

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

2.

2

3.

14.1 Основные принципы
динамического программирования
на примере задачи о кратчайшем пути

4. Пример

4

5. Принцип многошаговости

1
Принцип многошаговости
5

6. Принцип погружения

2
Принцип погружения
6

7. Принцип оптимальности

3
11
5
6
15
0
6
2
7

8. Функция Беллмана

4
Функция Беллмана
8

9. Уравнение Беллмана

5
Уравнение Беллмана
Уравнение
Беллмана для
нашей задачи
9

10. Уравнение Беллмана

5
Уравнение Беллмана
10

11. Пример

6
Пример
11

12.

14.2 Задача об инвестициях

13. Постановка задачи

1
Постановка задачи
13

14. Функция и уравнение Беллмана

2
Функция и уравнение Беллмана
14

15. Пример

3
6
5
4
3
2
1
0
0
1
Торговля
2
3
Производство
4
5
Инновации
15

16. Пример

3
Пример
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
0
1
0
2
0
0
0
1
1
1
0
1
2
0
2
0
2
0
3
0
0
0
1
2
1
0
1
2
1
2
0
2
3
0
3
0
3
0
4
0
0
0
1
3
1
0
1
2
2
2
0
2
3
1
3
0
3
4
0
4
0
4
0
5
0
0
0
1
4
1
0
1
2
3
2
0
2
3
2
3
0
3
4
1
4
0
4
5
0
5
0
16
5
2
3
4
5

17. Пример

3
Пример
0
0
0
0
0
0
1
0
1
0
1
1
1
0
2
0
2
0
2
0
2
2
1
1
2
1
3
2
0
3
0
3
0
3
0
3
3
1
2
2
2
4
2
1
3
1
4
3
0
3
0
3
0
4
0
4
4
1
3
2
3
5
2
2
3
2
5
3
1
3
1
4
4
0
3
0
3
0
5
0
5
5
1
4
2
4
6
2
3
3
3
6
3
2
3
2
5
4
1
3
1
4
5
0
3
0
17
3
2
3
4
5

18. Пример

3
Пример
0
0
0
0
0
0
1
0
1
0
2
2
1
0
0
0
0
0
2
0
3
3
1
1
0
2
2
2
0
2
0
2
0
3
0
4
4
1
2
0
3
3
2
1
2
2
4
3
0
4
0
4
0
4
0
5
5
1
3
0
4
4
2
2
2
3
5
3
1
4
2
6
4
0
6
0
6
0
5
0
6
6
1
4
0
5
5
2
3
2
4
6
3
2
4
3
7
4
1
6
2
2
3
4
5
5
0
6
0
8
18
6

19. Пример

3
6
5
4
3
2
1
0
0
1
Торговля
2
3
Производство
4
Инновации
5
19