Такой метод называется




НазваниеТакой метод называется
Дата конвертации11.03.2013
Размер445 b.
ТипЗадача



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

  • Многие задачи практического программирования являются задачами на перебор вариантов и выбор среди этих вариантов допустимого или наилучшего по тому или иному критерию. Однако рассмотреть все варианты, в силу чрезвычайно большого их количества, зачастую не представляется возможным .

  • Для ряда задач, сходных по формулировке с проблемами, действительно требующими полного перебора вариантов, можно найти гораздо более эффективное решение.

  • Чаще всего в таких случаях решение сводится к нахождению решений подзадач меньшей размерности, которые запоминаются в таблице и никогда более не пересчитываются, а подзадачи большей размерности используют эти уже найденные решения.

  • Такой метод называется динамическим программированием, еще его называют табличным методом.

  • В общей же форме под динамическим программированием понимают процесс пошагового решения задачи оптимизации, при котором на каждом шаге из множества допустимых решений выбирается одно, которое оптимизирует заданную целевую или критериальную функцию.

  • Как правило, связь задач и подзадач формулируется в виде некоторого “принципа оптимальности” и выражается системой уравнений (рекуррентных соотношений).

  • Основы теории динамического программирования были заложены Р. Беллманом (Беллман Ричард. Динамическое программирование).

  • Заметим, что слово «программирование» в приведенном названии (dynamic programming), также как и в “линейном программировании” (linear programming) не означает составление программ для компьютера.



Динамическое программирование — это способ решения сложных задач путем сведения их к более простым задачам того же типа.

  • Динамическое программирование — это способ решения сложных задач путем сведения их к более простым задачам того же типа.

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

  • (они обозначены сплошными линиями)

  • и их "стоимость". Тогда для нахождения оптимального маршрута из А в Е нужно выбрать

  • вариант, который даст минимальную

  • стоимость по сумме двух шагов. В дан-

  • ном случае это маршрут А-В-Е, стоимость которого равна 25. Как видим, такие задачи решаются "с конца».



При больших N решение задачи методом перебора потребует огромного времени вычисления.

  • При больших N решение задачи методом перебора потребует огромного времени вычисления.

  • Для того, чтобы использовать метод динамического программирования, нужно:

  • 1) выразить KN через предыдущие значения последовательности K1, К2,..., KN-1, KN;

  • 2) выделить массив для хранения всех предыдущих значений Ki (i= 1,..., N-1).

  • Самое главное — вывести рекуррентную формулу, выражающую КN через решения аналогичных задач меньшей размерности. Рассмотрим цепочку из N бит, первый элемент которой — 0.



Поскольку дополнительный 0 не может привести к появлению двух соседних единиц, подходящих последовательностей длиной N с нулем в начале существует столько, сколько подходящих последовательностей длины

  • Поскольку дополнительный 0 не может привести к появлению двух соседних единиц, подходящих последовательностей длиной N с нулем в начале существует столько, сколько подходящих последовательностей длины

  • N-1, то есть KN-1.

  • Если же первый символ — 1, то вторым обязательно должен быть 0, а остальная цепочка из N-2 битов должна быть любой "правильной". Поэтому подходящих последовательностей длиной N с единицей в начале существует столько, сколько подходящих последовательностей длины N-2, то есть К N-2.

  • В результате получаем KN = KN-1 + KN-2. Значит, для вычисления очередного числа нам нужно знать два предыдущих.



Очевидно, что есть две последовательности длиной 1 (0 и 1), то есть К1 — 2. Далее, есть три подходящих последовательности длины 2 (00, 01 и 10), поэтому К = 3.

  • Очевидно, что есть две последовательности длиной 1 (0 и 1), то есть К1 — 2. Далее, есть три подходящих последовательности длины 2 (00, 01 и 10), поэтому К = 3.

  • Задача. Найти количество KN цепочек, состоящих из 10 нулей и единиц, в которых нет двух стоящих подряд единиц.



Что нужно знать:

  • Что нужно знать:

  • динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа

  • с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов:

    • «подсчитайте количество вариантов…»
    • «как оптимально распределить…»
    • «найдите оптимальный маршрут…»
  • динамическое программирование позволяет ускорить выполнение программы за счет использования дополнительной памяти; полный перебор не требуется, поскольку запоминаются решения всех задач с меньшими значениями параметров



У исполнителя Утроитель две команды, которым присвоены номера:

  • У исполнителя Утроитель две команды, которым присвоены номера:

  • 1. прибавь 1

  • 2. умножь на 3

  • Первая из них увеличивает число на экране на 1, вторая – утраивает его.

  • Программа для Утроителя – это последовательность команд.

  • Сколько есть программ, которые число 1 преобразуют в число 20?

  • Ответ обоснуйте.



заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)

  • заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)

  • начнем с простых случаев, с которых будем начинать вычисления: для чисел 1 и 2, меньших, чем 3, существует только одна программа, состоящая только из команд сложения; если через обозначить количество разных программ для получения числа N из 1, то .

  • теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N

  • если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому

  • если N делится на 3, то последней командой может быть как сложение, так и умножение, поэтому для получения нужно сложить (количество программ с последней командой сложения) и (количество программ с последней командой умножения). В итоге получаем:

  • если N не делится на 3:

  • если N делится на 3:

  • остается заполнить таблицу для всех значений от 1 до N:





Ограничение по времени: 3 сек

  • Ограничение по времени: 3 сек

  • Имеется калькулятор, который выполняет три операции:

  • Прибавить к числу X единицу.

  •  Умножить число X на 2.

  • Умножить число X на 3.

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

  • Формат входных данных

  • Программа получает на вход одно число, не превосходящее 106.

  •  Формат выходных данных

  • Одно число: наименьшее количество искомых операций.

  • Пример



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

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

  • 1) он будет состоять из отрезков, соединяющих центры клеток, имеющих общую сторону

  • 2) длина маршрута минимально возможная

  • 3) из всех маршрутов, удовлетворяющих условиям (1) и (2), искомый маршрут тот, сумма цифр в клетках которого максимальна.



Пусть клетка (1, 1) это левый верхний угол таблицы, а (N, N), соответственно, правый нижний угол. Из условия (2) задачи следует, что за каждый шаг мы будем продвигаться по таблице либо на шаг вправо, либо на шаг вниз, что сразу нам гарантирует минимальность в длине пути и избавляет от анализа вариантов по данному критерию.

  • Пусть клетка (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), а это противоречит тому, что мы изначально рассматривали часть из уже оптимального маршрута. Значит, любая часть оптимального маршрута в свою очередь является оптимальной.



Задача. В цистерне N литров молока. Есть бидоны объемом 1, 5 и 6 литров. Нужно разлить молоко в бидоны так, чтобы все бидоны были заполнены и количество используемых бидонов было минимальным.

  • Задача. В цистерне N литров молока. Есть бидоны объемом 1, 5 и 6 литров. Нужно разлить молоко в бидоны так, чтобы все бидоны были заполнены и количество используемых бидонов было минимальным.

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



Выбираем бидоны постепенно. Тогда последний выбранный бидон может иметь объем 1 л, 5 л, 6 л.

  • Выбираем бидоны постепенно. Тогда последний выбранный бидон может иметь объем 1 л, 5 л, 6 л.

  • Если 1 л, то КN = 1 + КN-1. Если последний бидон имеет объем 5 л, то KN= 1 + KN_5, а если 6 л — KN = 1 + KN_ 6.

  • Так как нам нужно выбрать минимальное значение, то

  • KN = 1 + min(KN-1,KN_5, KN_6).

  • Вариант, выбранный при поиске минимума, определяет последний добавленный бидон, его нужно сохранить в отдельном массиве Р. Этот массив будет использован для определения количества выбранных бидонов каждого типа. В качестве начального значения берем K0 = 0.

  • Полученная формула применима при N > =6. Например,

  • К3= 1+K2=3, K5= 1 + min(K4,K0) = 1.





Похожие:

Такой метод называется iconМетод А. Качественный гель-тромб тест. Метод В. Количественный гель-тромб тест
Точность определения содержания эндотоксина этим методом не очень высокая. Поэтому в Европейской фармакопее метод называется полуколичественным...
Такой метод называется iconЛекция Творческие методы дизайна Метод инверсии. Метод деконструкции. Метод аналогии. Метод эмпатии. Метод фантазии. Метод мозгового штурма. Метод комбинаторики
Творческие методы дизайна Метод инверсии. Метод деконструкции. Метод аналогии. Метод эмпатии. Метод фантазии. Метод мозгового штурма....
Такой метод называется iconЗадача научиться правильно дышать. Правильным является такое дыхание, при котором наиболее активно работают межреберные мышцы нижних стенок живота и диафрагмы. Такой тип дыхания называется диафрагменным
В начале обучения главная ваша задача научиться правильно дышать. Правильным является такое дыхание, при котором наиболее активно...
Такой метод называется iconЗащита прав собственности
Защита права собственности осуществляется путём иска собственника, направленного на истребования своего имущества из чужого незаконного...
Такой метод называется iconАнтропогенные воздействия
По большому счету, нет такой потребности, которую можно было бы удовлетворить без участия природы. В результате окружающая природная...
Такой метод называется iconЛекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1
Аналогично, если  = , то а называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминальный символ,...
Такой метод называется iconХирургическая тактика при осложненных грыжах
Грыжей называется такой врожденный или приобретенный дефект мышечно -апоневротической целостности брюшной стенки, который дает возможность...
Такой метод называется iconМетод Монте-Карло
Для определения доверительного интервала времени и оценки надежности выполнения заказа может применяться имитационное моделирование...
Такой метод называется iconГибридологический метод. Гибридологический метод
Гибридизация скрещивание 2-х организмов, различающихся альтернативными признаками
Такой метод называется iconГрафический метод решения системы уравнений
Графический метод решения систем, как и графический метод решения уравнений, красив, но ненадежен
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница