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

Июль 22, 2022

Главная
Информатика
Динамическое программирование

Содержание

7. Числа Фибоначчи Решение методом «динамического программирования» предполагает запоминание каждого числа в массиве. Тогда N-е число Фибоначчи
8. Задача об n – битных двоичных числах Найти количество F всех n – битных двоичных чисел,
9. F[N] = F[N-1] + F[N-2], при N > 2. Задача об n – битных двоичных числах
10. Зайчик на лесенке На вершине лесенки, содержащей N ступенек, находится зайчик, который начинает прыгать по ним
11. Зайчик на лесенке Пусть зайчик находится на ступеньке с номером X. По условию он может спрыгнуть
12. Программа на С++ #include using namespace std; int main() { int N; long long F[31]; cin>>N;
13. Задача о фишке Фишка может двигаться по полю длины N только вперед. Длина хода фишки не
14. Задача о фишке Пусть S[i] - количество различных путей, по которым фишка может пройти поле от
15. Алгоритм динамического программирования Динамическое программирование – метод оптимизации, приспособленный к задачам, в которых требуется построить решение
16. Задача о черепашке Сколько вариантов пройти с левого нижнего угла в правый верхний угол?
17. Формулировка задачи динамического программирования Дано: множество состояний в том числе начальное и конечное множество возможных переходов
18. Пример 0 18 1 2 3 5 7 6 8 10 12 11 13 4 14
19. Математическая запись /9
20. Принцип оптимальности Беллмана Если вершины A и B лежат на оптимальном пути между вершинами 0 и
21. Алгоритм решения задач динамического программирования 0 18 1 2 3 5 7 6 8 10 12
22. Алгоритм решения задач динамического программирования 0 18 1 2 3 5 7 6 8 10 12
23. Экономические приложения /9
25. Скачать презентацию

Слайд 2

Слайд 3

Слайд 4

Слайд 5

Слайд 6

Слайд 7

Числа Фибоначчи
Решение методом «динамического программирования» предполагает запоминание каждого числа в массиве.
Тогда

N-е число Фибоначчи легко можно найти по следующей формуле:
F[N] = F[N-1] + F[N-2], при N > 2.

Слайд 8

Задача об n – битных двоичных числах
Найти количество F всех

n – битных двоичных чисел, у которых в двоичной записи нет подряд идущих двух единиц. (N≤30).

Слайд 9

F[N] = F[N-1] + F[N-2], при N > 2.
Задача об

n – битных двоичных числах

Слайд 10

Зайчик на лесенке
На вершине лесенки, содержащей N ступенек, находится зайчик,

который начинает прыгать по ним вниз, к основанию.
Зайчик может прыгнуть на следующую ступеньку, на ступеньку через 1 или 2.
Определить число всевозможных “маршрутов” зайчика с вершины на землю.

Слайд 11

Зайчик на лесенке
Пусть зайчик находится на ступеньке с номером X.
По

условию он может спрыгнуть на ступеньки с номерами X - 1, X - 2 и X - 3.
Пусть F(X) - число маршрутов со ступеньки X до земли
F[X] = F[X – 1] + F[X – 2] + F[X – 3]

Слайд 12

Программа на С++
#include
using namespace std;
int main()
{ int N; long long F[31];

cin>>N;
F[1]=1;F[2]=2;F[3]=4;
for(int i=4; i <= N; i++)
F[i]=F[i-1]+F[i-2]+F[i-3];
cout<return 0;
}

Слайд 13

Задача о фишке
Фишка может двигаться по полю длины N
только вперед. Длина

хода фишки не
более K (N, K ≤10).
Найти количество различных путей, по которым фишка может пройти поле от позиции 1 до позиции N.

Слайд 14

Задача о фишке
Пусть S[i] - количество различных путей, по которым фишка

может пройти поле от начала до позиции с номером i. Предположим, что для любого j от 1 до i известны значения величин S[j]. Задача состоит в определении правила вычисления значения S[i+1], используя значения известных величин. Заметим, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k.
S[i+1]=S[i]+S[i-1]+...+S[i-k]
Вычисляя последовательно значения величин S[1], S[2],..., S[N] по правилу, получаем значение S[N] – решение задачи

Слайд 15

Алгоритм динамического программирования
Динамическое программирование – метод оптимизации, приспособленный к задачам, в

которых требуется построить решение с максимизацией или минимизацией, т.е. оптимальным значением некоторого параметра.

Его алгоритм можно сформулировать так:
Выделить и описать подзадачи, через решение которых будет выражаться искомое решение;
Выписать рекуррентные соотношения (уравнения), связывающие оптимальные значения параметра для всех подзадач;
Вычислить оптимальное значение параметра для всех подзадач;
Построить само оптимальное решение.

В задачах на подсчет количеств допустимых вариантов (задачи рассмотрены выше) пункт 4 не нужен

Слайд 16

Задача о черепашке
Сколько вариантов пройти с левого нижнего угла в правый

верхний угол?

Слайд 17

Формулировка задачи динамического программирования
Дано:
множество состояний
в том числе начальное и конечное
множество

возможных переходов из одного состояния в другое
с каждым переходом связывается числовой параметр
интерпретируется как затраты, выгода, расстояние, время и т.п.
Найти:
оптимальную последовательность переходов (путь) из начального состояния в конечное
максимум или минимум суммы числовых параметров
предполагается, что хотя бы один путь из начального состояния в конечное существует

Слайд 18

Пример
0
18
1
2
3
5
7
6
8
10
12
11
13
4
14
15
16
9
17
3
8
5
4
4
7
4
12
7
6
9
1
1
4
2
16
0
7
9
10
8
5
5
11
12
9
3
8
4
-2
4
4
/9

Слайд 19

Математическая запись
/9

Слайд 20

Принцип оптимальности Беллмана
Если вершины A и B лежат на оптимальном

пути между вершинами 0 и X, то часть оптимального пути от 0 до X между вершинами A и B непременно является оптимальным путём от A до B.
Следствие
Чтобы найти оптимальный путь от 0 до A, достаточно исследовать продолжения к A всех оптимальных путей до вершин, предшествующих A
Продолжения неоптимальных путей к предшествующим вершинам можно не просчитывать: они никогда не дадут оптимального пути к A
Принцип Беллмана позволяет построить простую и эффективную вычислительную процедуру для решения задач динамического программирования

Слайд 21

Алгоритм решения задач динамического программирования
0
18
1
2
3
5
7
6
8
10
12
11
13
4
14
15
16
9
17
3
8
5
4
4
7
4
12
7
6
9
1
1
4
2
16
0
7
9
10
8
5
5
11
12
9
3
8
4
-2
4
4
0
3
11
15
15
19
35
5
9
4
18
14
18
28
23
34
4
27
37
45
максимум
/9

Слайд 22

Алгоритм решения задач динамического программирования
0
18
1
2
3
5
7
6
8
10
12
11
13
4
14
15
16
9
17
3
8
5
4
4
7
4
12
7
6
9
1
1
4
2
16
0
7
9
10
8
5
5
11
12
9
3
8
4
-2
4
4
0
4
5
11
3
7
11
15
17
15
16
13
4
19
16
11
12
12
14
23
минимум
/9

Слайд 23

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

Содержание

Числа ФибоначчиРешение методом «динамического программирования» предполагает запоминание каждого числа в массиве.Тогда

Задача об n – битных двоичных числах Найти количество F всех

F[N] = F[N-1] + F[N-2], при N > 2. Задача об

Зайчик на лесенке На вершине лесенки, содержащей N ступенек, находится зайчик,

Зайчик на лесенке Пусть зайчик находится на ступеньке с номером X.По

Программа на С++#include using namespace std;int main(){ int N; long long F[31];

Задача о фишкеФишка может двигаться по полю длины Nтолько вперед. Длина

Задача о фишкеПусть S[i] - количество различных путей, по которым фишка

Алгоритм динамического программированияДинамическое программирование – метод оптимизации, приспособленный к задачам, в

Задача о черепашкеСколько вариантов пройти с левого нижнего угла в правый

Формулировка задачи динамического программирования Дано:множество состоянийв том числе начальное и конечноемножество

Пример 01812357681012111341415169173854474127691142160791085511129384-244/9

Математическая запись /9

Принцип оптимальности Беллмана Если вершины A и B лежат на оптимальном

Алгоритм решения задач динамического программирования 01812357681012111341415169173854474127691142160791085511129384-2440311151519355941814182823344273745максимум/9

Алгоритм решения задач динамического программирования 01812357681012111341415169173854474127691142160791085511129384-2440451137111517151613419161112121423минимум/9

Экономические приложения/9

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