это оптимизационная задача.
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Методы решения оптимизационных задач презентация
Содержание
- 1. Методы решения оптимизационных задач
- 2. Методы решения оптимизационных задач Формула Жадный
- 3. Методы решения оптимизационных задач Перебор Бинарный поиск
- 4. Динамическое программирование Задача №2963: Имеется калькулятор, который
- 5. Динамическое программирование Прибавить к числу X единицу.
- 6. Динамическое программирование Прибавить к числу X единицу.
- 7. Динамическое программирование Прибавить к числу X единицу.
- 8. Динамическое программирование Прибавить к числу X единицу.
- 9. Динамическое программирование Прибавить к числу X единицу.
- 10. Динамическое программирование Прибавить к числу X единицу.
- 11. Динамическое программирование Прибавить к числу X единицу.
- 12. Динамическое программирование Прибавить к числу X единицу.
- 13. Динамическое программирование Прибавить к числу X единицу.
- 14. Динамическое программирование Прибавить к числу X единицу.
- 15. Динамическое программирование Прибавить к числу X единицу.
- 16. Динамическое программирование Прибавить к числу X единицу.
- 17. Динамическое программирование Прибавить к числу X единицу.
- 18. Динамическое программирование Прибавить к числу X единицу.
- 19. Динамическое программирование Прибавить к числу X единицу.
- 20. Динамическое программирование Прибавить к числу X единицу.
- 21. Динамическое программирование Прибавить к числу X единицу.
- 22. Динамическое программирование Прибавить к числу X единицу.
- 23. Динамическое программирование Прибавить к числу X единицу.
- 24. Как найти ответ? Прибавить к числу X
- 25. http://informatics.mccme.ru Кружки и уроки Новосибирская область ДИО-ГЕН Модуль «Динамическое программирование. Часть 1» 1. Знакомство
Методы решения оптимизационных задач Формула Жадный алгоритм Перебор Бинарный поиск по ответу Динамическое программирование
Слайд 2Методы решения оптимизационных задач
Формула
Жадный алгоритм
Перебор
Бинарный поиск по ответу
Динамическое программирование
Слайд 3Методы решения оптимизационных задач
Перебор
Бинарный поиск по ответу
Динамическое программирование
- это когда
разбиваем исходную задачу над подзадачи и выражаем более сложные через простые, записывая ответы в таблицу.
Слайд 4Динамическое программирование
Задача №2963:
Имеется калькулятор, который выполняет три операции:
Прибавить к числу X
единицу.
Умножить число X на 2.
Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Умножить число X на 2.
Умножить число X на 3.
Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N.
Слайд 5Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
Слайд 6Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
Слайд 7Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
Слайд 8Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
Слайд 9Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1 *2
Слайд 10Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1 *2
Слайд 11Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
*3
+1
3 можем получить из единицы или из двойки
Из 1 за 0+1 действие
Из 2 за 1+1 действие
Слайд 12Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
*3
+1
3 можем получить из единицы или из двойки
Из 1 за 0+1 действие
Из 2 за 1+1 действие
Выгоднее из 1
Слайд 13Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
*2
+1
4 можем получить из тройки или из двойки
Из 3 за 1+1 = 2 действия
Из 3 за 1+1 = 2 действие
Ответ: 2
Слайд 14Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
*2
+1
4 можем получить из тройки или из двойки
Из 3 за 1+1 = 2 действия
Из 3 за 1+1 = 2 действие
Ответ: 2
Слайд 15Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Будем последовательно решать задачу для N = 1, 2, 3, …
+1
5 можем получить только из 4 за 2 + 1 действие
Слайд 16Динамическое программирование
Прибавить к числу 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
Слайд 17Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ?
Слайд 18Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ? В Answer[N]
Слайд 19Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Последовательно заполняем массив ответов слева направо.
Где находится ответ? В Answer[N]
Можно не заполнять массив, а написать рекурсивную функцию.
Слайд 20Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Последовательно заполняем массив ответов слева направо.
Нам повезло, что все операции только увеличивают число. В противном случае метод применить было бы нельзя.
Слайд 21Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Последовательно заполняем массив ответов слева направо.
Нам повезло, что все операции только увеличивают число. В противном случае метод применить было бы нельзя.
Слайд 22Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Последовательно заполняем массив ответов слева направо.
Но есть и более общий подход:
Слайд 23Динамическое программирование
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить число
X на 3.
Последовательно заполняем массив ответов слева направо.
Но есть и более общий подход: Поиск в ширину (BFS)
Слайд 24Как найти ответ?
Прибавить к числу X единицу.
Умножить число X на 2.
Умножить
число X на 3.
Массив Parent[i] – число, которое было на калькуляторе перед i (как вариант – последняя операция)
Слайд 25http://informatics.mccme.ru
Кружки и уроки
Новосибирская область
ДИО-ГЕН
Модуль «Динамическое программирование. Часть 1»
1. Знакомство
