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

Методы решения оптимизационных задач
Формула
Жадный алгоритм
Перебор
Бинарный поиск по ответу
Динамическое программирование

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

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

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

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

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

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

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

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

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

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
*3
+1
3 можем получить из единицы или из двойки
Из 1 за 0+1 действие
Из 2 за 1+1 действие
Выгоднее из 1

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
*2
+1
4 можем получить из тройки или из двойки
Из 3 за 1+1 = 2 действия
Из 3 за 1+1 = 2 действие
Ответ: 2

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
*2
+1
4 можем получить из тройки или из двойки
Из 3 за 1+1 = 2 действия
Из 3 за 1+1 = 2 действие
Ответ: 2

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

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

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ?

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ? В Answer[N]

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ? В Answer[N]
Можно не заполнять массив, а написать рекурсивную функцию.

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Нам повезло, что все операции только увеличивают число. В противном случае метод применить было бы нельзя.

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Нам повезло, что все операции только увеличивают число. В противном случае метод применить было бы нельзя.

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Но есть и более общий подход:

Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Последовательно заполняем массив ответов слева направо.
Но есть и более общий подход: Поиск в ширину (BFS)

Как найти ответ?
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число X на 3.
Массив Parent[i] – число, которое было на калькуляторе перед i (как вариант – последняя операция)