Основные определения (подробно) Многие задачи практического программирования являются задачами на перебор вариантов и выбор среди этих вариантов допустимого. - презентация

1

2 Основные определения (подробно) Многие задачи практического программирования являются задачами на перебор вариантов и выбор среди этих вариантов допустимого или наилучшего по тому или иному критерию. Однако рассмотреть все варианты, в силу чрезвычайно большого их количества, зачастую не представляется возможным. Для ряда задач, сходных по формулировке с проблемами, действительно требующими полного перебора вариантов, можно найти гораздо более эффективное решение. Чаще всего в таких случаях решение сводится к нахождению решений подзадач меньшей размерности, которые запоминаются в таблице и никогда более не пересчитываются, а подзадачи большей размерности используют эти уже найденные решения. Такой метод называется динамическим программированием, еще его называют табличным методом. В общей же форме под динамическим программированием понимают процесс пошагового решения задачи оптимизации, при котором на каждом шаге из множества допустимых решений выбирается одно, которое оптимизирует заданную целевую или критериальную функцию. Как правило, связь задач и подзадач формулируется в виде некоторого принципа оптимальности и выражается системой уравнений (рекуррентных соотношений). Основы теории динамического программирования были заложены Р. Беллманом (Беллман Ричард. Динамическое программирование). Заметим, что слово «программирование» в приведенном названии (dynamic programming), также как и в линейном программировании (linear programming) не означает составление программ для компьютера.

3 Основные определения (коротко) Динамическое программирование это способ решения сложных задач путем сведения их к более простым задачам того же типа. Такой подход впервые систематически применил американский математик Ричард Беллман при решении сложных многошаговых задач оптимизации. Его идея состояла в том, что оптимальная последовательность шагов оптимальна на любом участке. Например, пусть нужно перейти из пункта А в пункт Е через один из пунктов В, С или D (числами обозначена "стоимость" маршрута): Пусть уже известны оптимальные маршруты из пунктов В, С и D в пункт Е (они обозначены сплошными линиями) и их "стоимость". Тогда для нахождения оптимального маршрута из А в Е нужно выбрать вариант, который даст минимальную стоимость по сумме двух шагов. В дан- ном случае это маршрут А-В-Е, стоимость которого равна 25. Как видим, такие задачи решаются "с конца».

4 Задача. Найти количество K N цепочек, состоящих из N нулей и единиц, в которых нет двух стоящих подряд единиц. При больших N решение задачи методом перебора потребует огромного времени вычисления. Для того, чтобы использовать метод динамического программирования, нужно: 1) выразить K N через предыдущие значения последовательности K 1, К 2,..., K N-1, K N ; 2) выделить массив для хранения всех предыдущих значений K i (i= 1,..., N-1). Самое главное вывести рекуррентную формулу, выражающую К N через решения аналогичных задач меньшей размерности. Рассмотрим цепочку из N бит, первый элемент которой N-1N 0…

5 Продолжение решения: Поскольку дополнительный 0 не может привести к появлению двух соседних единиц, подходящих последовательностей длиной N с нулем в начале существует столько, сколько подходящих последовательностей длины N-1, то есть K N-1. Если же первый символ 1, то вторым обязательно должен быть 0, а остальная цепочка из N-2 битов должна быть любой "правильной". Поэтому подходящих последовательностей длиной N с единицей в начале существует столько, сколько подходящих последовательностей длины N-2, то есть К N-2. В результате получаем K N = K N-1 + K N-2. Значит, для вычисления очередного числа нам нужно знать два предыдущих. 123N-1N 10…

6 Рассмотрим простые случаи. Очевидно, что есть две последовательности длиной 1 (0 и 1), то есть К 1 2. Далее, есть три подходящих последовательности длины 2 (00, 01 и 10), поэтому К = 3. Задача. Найти количество K N цепочек, состоящих из 10 нулей и единиц, в которых нет двух стоящих подряд единиц. Ответ:144

7 Задача С3 ЕГЭ Что нужно знать: динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов: «подсчитайте количество вариантов…» «как оптимально распределить…» «найдите оптимальный маршрут…» динамическое программирование позволяет ускорить выполнение программы за счет использования дополнительной памяти; полный перебор не требуется, поскольку запоминаются решения всех задач с меньшими значениями параметров

8 Пример задания (ЕГЭ 2012) У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1 2. умножь на 3 Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? Ответ обоснуйте.

9 Решение 1. заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться) 2. начнем с простых случаев, с которых будем начинать вычисления: для чисел 1 и 2, меньших, чем 3, существует только одна программа, состоящая только из команд сложения; если через обозначить количество разных программ для получения числа N из 1, то. 3. теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности, то есть с решениями таких же задач для меньших N 4. если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому 5. если N делится на 3, то последней командой может быть как сложение, так и умножение, поэтому для получения нужно сложить (количество программ с последней командой сложения) и (количество программ с последней командой умножения). В итоге получаем: если N не делится на 3: если N делится на 3: 6. остается заполнить таблицу для всех значений от 1 до N:

10 N Заметим, что количество вариантов меняется только в тех столбцах, где N делится на 3, поэтому из всей таблицы можно оставить только эти столбцы: N заданное число 20 попадает в последний интервал (от 18 до 21), поэтому … ответ – 12.

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

12 Классические задачи динамического программирования Задача 1. «МАРШРУТ» В таблице NхN, клетки заполнены случайным образом цифрами от 0 до 9. Найти маршрут из клетки A(1,1) в клетку A(N, N) такой, что: 1) он будет состоять из отрезков, соединяющих центры клеток, имеющих общую сторону 2) длина маршрута минимально возможная 3) из всех маршрутов, удовлетворяющих условиям (1) и (2), искомый маршрут тот, сумма цифр в клетках которого максимальна.

13 Указания к решению: Пусть клетка (1, 1) это левый верхний угол таблицы, а (N, N), соответственно, правый нижний угол. Из условия (2) задачи следует, что за каждый шаг мы будем продвигаться по таблице либо на шаг вправо, либо на шаг вниз, что сразу нам гарантирует минимальность в длине пути и избавляет от анализа вариантов по данному критерию. Рассмотрим произвольную клетку таблицы (i, j). В нее мы можем прийти или из клетки (i- 1, j), или из (i, j-1). Тогда, если мы уже знаем оптимальные маршруты из клетки (1, 1) в каждую из этих двух клеток, то оптимальным маршрутом в клетку (i, j) будет под маршрут с максимальной из двух сумм суммой плюс отрезок, соединяющий (i, j) с концом выбранного под маршрута. Оптимальные маршруты из (1, 1) в (1, 2) и (2, 1) определены однозначно. Зная их, по указанному выше способу мы найдем оптимальные маршруты в (1, 3), (2, 2), (3, 1) и запишем их в соответствующих клетках таблицы (записывать нужно только сумму цифр маршрута и направление его последнего отрезка). Этот процесс можно продолжить пока вся таблица не будет заполнена, причем заполнять ее можно по строчкам слева направо. В клетке (N, N) мы в итоге получим значение суммы цифр искомого маршрута и последний его отрезок. По такой таблице легко восстановить и весь маршрут, начиная с клетки (N, N). Рассмотрим любую часть оптимального маршрута, например, между клетками (i1, j1) и (i2, j2). Докажем, что эта часть маршрута является решением исходной задачи для указанных клеток. Пусть это не так и существует маршрут с большей суммой, соединяющий эти клетки и имеющий такую же длину. Тогда и для клеток (1, 1) и (N, N) мы можем построить лучший маршрут, используя отрезки, соединяющие (1, 1) и (i1, j1), а также (i2, j2) и (N, N) из старого маршрута плюс улучшенный маршрут из (i1, j1) в (i2, j2), а это противоречит тому, что мы изначально рассматривали часть из уже оптимального маршрута. Значит, любая часть оптимального маршрута в свою очередь является оптимальной.

14 Поиск оптимального решения Задача. В цистерне N литров молока. Есть бидоны объемом 1, 5 и 6 литров. Нужно разлить молоко в бидоны так, чтобы все бидоны были заполнены и количество используемых бидонов было минимальным. Решение: Задача решается перебором вариантов для любого введенного числа N. Самый простой подход заполнять сначала бидоны самого большого размера (6 л), затем меньшие и т.д. Алгоритм, который мы применили, называется "жадным". Он состоит в том, чтобы на каждом шаге многоходового процесса выбирать наилучший в данный момент вариант, не думая о том, что впоследствии этот выбор может привести к худшему решению. «Жадный» алгоритм не всегда приводит к оптимальному решению. Например, для N 10 «жадный» алгоритм дает решение всего 5 бидонов, в то время как можно обойтись двумя (5 + 5).

15 Как и в любом решении, использующем динамическое программирование, главная проблема составить рекуррентную формулу. Сначала определим оптимальное число бидонов К, а потом подумаем, как определить, какие именно бидоны нужно использовать. Выбираем бидоны постепенно. Тогда последний выбранный бидон может иметь объем 1 л, 5 л, 6 л. Если 1 л, то К N = 1 + К N-1. Если последний бидон имеет объем 5 л, то K N = 1 + K N _ 5, а если 6 л K N = 1 + K N _ 6. Так как нам нужно выбрать минимальное значение, то K N = 1 + min(K N-1,K N _ 5, K N _ 6 ). Вариант, выбранный при поиске минимума, определяет последний добавленный бидон, его нужно сохранить в отдельном массиве Р. Этот массив будет использован для определения количества выбранных бидонов каждого типа. В качестве начального значения берем K 0 = 0. Полученная формула применима при N > =6. Например, К 3 = 1+K2=3, K 5 = 1 + min(K 4,K 0 ) = 1.

16 массивы для N 10.