Если в задаче надо найти наибольший (максимальный), наименьший (минимальный) вариант – это оптимизационная задача.

134.37K

Category: $mathematics$ mathematics

Методы решения оптимизационных задач

1. Если в задаче надо найти наибольший (максимальный), наименьший (минимальный) вариант – это оптимизационная задача.

2. Методы решения оптимизационных задач

1. Формула
2. Жадный алгоритм
3. Перебор
4. Бинарный поиск по ответу
5. Динамическое программирование

3. Методы решения оптимизационных задач

1. Перебор
2. Бинарный поиск по ответу
3. Динамическое программирование
- это когда разбиваем исходную задачу над
подзадачи и выражаем более сложные
через простые, записывая ответы в
таблицу.

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

Задача №2963:
Имеется калькулятор, который выполняет три операции:
1. Прибавить к числу X единицу.
2. Умножить число X на 2.
3. Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для
того, чтобы получить из числа 1 заданное число N.

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
1
0
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
1
2
0
?
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1 *2
1
2
0
?
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1 *2
1
2
3
0
0+1
?
4
5
6
7
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1
*3
1
2
3
0
1
0+1
или
1+1
4
5
6
7
8
9
10
11
3 можем получить из единицы или из двойки
• Из 1 за 0+1 действие
• Из 2 за 1+1 действие
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1
*3
1
2
3
0
1
0+1
или
1+1
4
5
6
7
8
9
10
3 можем получить из единицы или из двойки
Из 1 за 0+1 действие
Из 2 за 1+1 действие
Выгоднее из 1
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1
*2
1
2
3
4
0
1
1
?
5
6
7
8
9
10
4 можем получить из тройки или из двойки
Из 3 за 1+1 = 2 действия
Из 3 за 1+1 = 2 действие
Ответ: 2
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1
*2
1
2
3
4
5
0
1
1
2
?
6
7
8
9
10
4 можем получить из тройки или из двойки
Из 3 за 1+1 = 2 действия
Из 3 за 1+1 = 2 действие
Ответ: 2
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1
1
2
3
4
5
0
1
1
2
3
6
7
8
9
10
11
12
5 можем получить только из 4 за 2 + 1 действие
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1
*3
*2
1
2
3
4
5
6
0
1
1
2
3
2
7
6 можем получить из 2, 3, 5
Из 2 за 1+1 = 2 действия
Из 3 за 1+1 = 2 действие
Из 5 за 3 + 1 = 4 действия
Выгодно за 2
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ?
1
2
3
4
5
6
0
1
1
2
3
2
7
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ? В Answer[N]
1
2
3
4
5
6
0
1
1
2
3
2
7
8
9
10
11
12
13
14
15

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

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Нам повезло, что все операции только увеличивают число. В противном
случае метод применить было бы нельзя.
1
2
3
4
5
6
0
1
1
2
3
2
7
8
9
10
11
12
13
14
15

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

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Но есть и более общий подход:
1
2
3
4
5
6
0
1
1
2
3
2
7
8
9
10
11
12
13
14
15

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

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Но есть и более общий подход: Поиск в ширину (BFS)
1
2
3
4
5
6
0
1
1
2
3
2
7
8
9
10
11
12
13
14
15

24. Как найти ответ?

1.
2.
3.
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Массив Parent[i] – число, которое было на калькуляторе перед i (как
вариант – последняя операция)
1
2
3
4
5
6
0
1
1
2
3
2
1
2
3
4
5
6
-1
1
1
3
4
3
7
8
9
10
11
12
13
14
15
7
8
9
10
11
12
13
14
15

25.

http://informatics.mccme.ru
Кружки и уроки
Новосибирская область
ДИО-ГЕН
Модуль «Динамическое
программирование. Часть 1»
• 1. Знакомство

English Русский Rules