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

Введение

В последние годы в заданиях части С3 ЕГЭ по информатике часто встречаются задачи, которые решаются методом динамического программирования. Это и явилось основным критерием выбора данной темы для доклада.

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

Для достижения поставленной цели необходимо решить ряд задач:

- рассмотреть понятие «динамическое программирование»;

- показать механизм решения задач части С3 ЕГЭ по информатике и ИКТ при помощи динамического программирования;

 - сделать выводы по результатам работы.

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

Решение задач математического программирования, которые могут быть представлены в виде многошагового (многоэтапного) процесса, составляет предмет динамического программирования. Вместе с этим динамическим программированием называют особый математический метод оптимизации решений, специально приспособленный к многошаговым процессам. Многошаговым обычно считают процесс, развивающийся во времени и распадающийся на ряд «шагов», или «этапов». Однако метод динамического программирования используется и для решения задач, в которых время не фигурирует. Некоторые процессы распадаются на шаги естественно (например, процесс планирования хозяйственной деятельности предприятия на отрезок времени, состоящий из нескольких лет); многие процессы можно разделить на этапы искусственно.

Одна из особенностей метода динамического программирования состоит в том, что принятие решения по отношению к многошаговым процессам рассматривается не как единичный акт, а как целый комплекс взаимосвязанных решений. Эту последовательность взаимосвязанных решений называют стратегией. Цель оптимального планирования – выбрать стратегию, обеспечивающую получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной.

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

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

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

При решении оптимизационной задачи методом динамического программирования необходимо учитывать на каждом шаге последствия, к которым приведет в будущем решение, принимаемое в данный момент. Исключением является последний шаг, которым процесс заканчивается. Здесь процесс можно планировать таким образом, чтобы последний шаг сам по себе приносил максимальный эффект. Спланировав оптимальным образом последний шаг, можно к нему «пристраивать» предпоследний так, чтобы результат этих двух шагов был оптимальным, и т. д. Именно так – от конца к началу – и можно развернуть процедуру принятия решений. Но чтобы принять оптимальное решение на последнем шаге, надо знать, чем мог закончиться предпоследний шаг. Значит, надо сделать разные предположения о том, чем мог закончиться предпоследний шаг и для каждого из предположений найти решение, при котором эффект на последнем шаге был бы наибольшим. Такое оптимальное решение, найденное при условии, что предыдущий шаг закончился определенным образом, называют условно – оптимальным.

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

Таким образом, На каждом шаге в соответствии с принципом оптимальности ищется решение, обеспечивающее оптимальное продолжение процесса относительно состояния, достигнутого в данный момент. Если при движении от конца к началу оптимизируемого процесса определены условно – оптимальные решения для каждого шага и вычислен соответствующий эффект (эту стадию рассуждений называют иногда условной оптимизацией), то остается «пройти» весь процесс в прямом направлении (стадия безусловной оптимизации) и «прочитать» оптимальную стратегию, которая нас интересует.

В принципе динамическое планирование может разворачиваться и в прямом направлении, т. е. от первого шага процесса к последнему.

Практическое применение динамического программирования

Типовой алгоритм решения задач методом динамического программирования:

Описать строение оптимальных решений.

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

Двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач.

Пользуясь полученной информацией, построить оптимальное решение.

 Рассмотрим задания С3 ЕГЭ по информатике и ИКТ.

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

1. прибавь 1

2. умножь на 3

Первая из них увеличивает число на экране на 1, вторая – утраивает его Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? Ответ обоснуйте.

Весь материал - смотрите документ.

МР «Хангаласский район»

МБОУ «Покровская средняя общеобразовательная школа №1»

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

Выполнила : учитель информатики

и математики Кузьмина С.Е.

2013 г.

Оглавление

Введение…………………………………………………………………….. 3

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

2. Практическое применение динамического программирования………. 7

Заключение…………………………………………………………………… 12

Список литературы…………………………………………………………....13

Введение

В последние годы в заданиях части С3 ЕГЭ по информатике часто встречаются задачи, которые решаются методом динамического программирования. Это и явилось основным критерием выбора данной темы для доклада .

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

Для достижения поставленной цели необходимо решить ряд задач:

- рассмотреть понятие «динамическое программирование»;

- показать механизм решения задач части С3 ЕГЭ по информатике и ИКТ при

помощи динамического программирования;

- сделать выводы по результатам работы.

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

Решение задач математического программирования, которые могут быть представлены в виде многошагового (многоэтапного) процесса, составляет предмет динамического программирования. Вместе с этим динамическим программированием называют особый математический метод оптимизации решений, специально приспособленный к многошаговым процессам. Многошаговым обычно считают процесс, развивающийся во времени и распадающийся на ряд «шагов», или «этапов». Однако метод динамического программирования используется и для решения задач, в которых время не фигурирует. Некоторые процессы распадаются на шаги естественно (например, процесс планирования хозяйственной деятельности предприятия на отрезок времени, состоящий из нескольких лет); многие процессы можно разделить на этапы искусственно.

Одна из особенностей метода динамического программирования состоит в том, что принятие решения по отношению к многошаговым процессам рассматривается не как единичный акт, а как целый комплекс взаимосвязанных решений. Эту последовательность взаимосвязанных решений называют стратегией. Цель оптимального планирования – выбрать стратегию, обеспечивающую получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной.

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

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

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

При решении оптимизационной задачи методом динамического программирования необходимо учитывать на каждом шаге последствия, к которым приведет в будущем решение, принимаемое в данный момент. Исключением является последний шаг, которым процесс заканчивается. Здесь процесс можно планировать таким образом, чтобы последний шаг сам по себе приносил максимальный эффект. Спланировав оптимальным образом последний шаг, можно к нему «пристраивать» предпоследний так, чтобы результат этих двух шагов был оптимальным, и т.д. Именно так – от конца к началу – и можно развернуть процедуру принятия решений. Но чтобы принять оптимальное решение на последнем шаге, надо знать, чем мог закончиться предпоследний шаг. Значит, надо сделать разные предположения о том, чем мог закончиться предпоследний шаг и для каждого из предположений найти решение, при котором эффект на последнем шаге был бы наибольшим. Такое оптимальное решение, найденное при условии, что предыдущий шаг закончился определенным образом, называют условно – оптимальным.

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

Таким образом, На каждом шаге в соответствии с принципом оптимальности ищется решение, обеспечивающее оптимальное продолжение процесса относительно состояния, достигнутого в данный момент. Если при движении от конца к началу оптимизируемого процесса определены условно – оптимальные решения для каждого шага и вычислен соответствующий эффект (эту стадию рассуждений называют иногда условной оптимизацией), то остается «пройти» весь процесс в прямом направлении (стадия безусловной оптимизации) и «прочитать» оптимальную стратегию, которая нас интересует.

В принципе динамическое планирование может разворачиваться и в прямом направлении, т. е. от первого шага процесса к последнему.

Практическое применение динамического программирования

Типовой алгоритм решения задач методом динамического программирования:

1. Описать строение оптимальных решений.

2. Выписать рекуррентное соотношение, связывающие оптимальные значения параметра для подзадач.

3. Двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач.

4. Пользуясь полученной информацией, построить оптимальное решение.

Рассмотрим задания С3 ЕГЭ по информатике и ИКТ .

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

1. прибавь 1

2. умножь на 3

Первая из них увеличивает число на экране на 1, вторая – утраивает его Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? Ответ обоснуйте.

Решение: За  обозначим количество программ для получения числа N, для N1 =1 . Рассмотрим, сколькими способами можно получить из числа 1 числа 2, 3, 4, 5, 6, … и определим рекуррентную формулу определения количества программ для получения числа N.

1. N=2, тогда =1  , 1+1=2

2. N=3, тогда =2 ,K2+1=1+1+1 или 1*3

3. N=4, тогда =2 , +1=1+1+1+1 или 1*3+1

4. N=5, тогда =2 , +1 = 1+1+1+1+1+1 или 1*3+1+1

5. N=6, тогда =3 , +1 = 1+1+1+1+1+1 или 1*3+1+1+1 или 1*3 +1*3

6. N=7 , тогда =+1 =1+1+1+1+1+1+1+1+1 или 1*3+1+1+1+1 или 1*3+1*3+1

7. N=8, тогда =3 , +1 =1+1+1+1+1+1+1+1 или 1*3+1+1+1+1+1 или 1*3+1*3+1+1

8. N=9, тогда =5, =1+1+1+1+1+1+1+1+1 или 1*3 +1+1+1+1+1+1 или 1*3+1*3+1*3 или 1*3+1*3+1+1+1 или 1*3*3 и.т.д .

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

1. Если N - любое число, не делящееся на 3, то =

2. Если N - число, делящееся на 3, то =+

По данной рекуррентной формуле построим таблицу для всех значений от 1 до N:

Ответ : 12

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

1. прибавь 1

2. умножь на 2

3. умножь на 3

Сколько есть программ, которые число 1 преобразуют в число 18? Ответ обоснуйте.

получения числа N, для N1 =1

Запишем рекуррентную формулу для получения любого натурального числа N:

1. Если N - любое число, не делящееся на 2 и не делящееся на 3, то =

2. Если N - число, делящееся на 2, но не делящееся на 3, то =+

3. Если N - число, делящееся на 3, но не делящееся на 2, то =+

4. Если N - число, делящееся на 2  и на 3, то =+

Выполним по этим формулам вычисления:
+

+

+

=5

+

=10

+

+

+

=23

+

=38

+

+

+

=68

+

Ответ : 96

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

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

Решение : получения числа N, для N1 =1

Запишем рекуррентную формулу для получения любого натурального числа N:

1. Если N не делится на 3 =+

2. Если N делится на 3 =++

Выполним по этим формулам вычисления:

+

+

+= 4+3 =7

+

+= 12+7=19

+

+

+

+= 84+53=137

+

Ответ : 225

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

1. Прибавь 1

2. Умножь на 2

3. Возведи в квадрат

Сколько есть программ, которые число 2 преобразуют в число 38 Решение : Запишем рекуррентную формулу для получения любого натурального числа N: если N не делится на 2 и не является квадратом целого числа:

если N не делится на 2 и является квадратом целого числа:

если N делится на 2 и не является квадратом целого числа:

если N делится на 2 и является квадратом целого числа:

По данной рекуррентной формуле построим таблицу для всех значений от 2 до N:

Ответ : 266

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

1. Прибавь 1

2. Прибавь 3

3. Возведи в квадрат.

Сколько есть программ, которые число 2 преобразуют в число 19? Ответ обоснуйте.

Решение: Запишем рекуррентную формулу для получения любого натурального числа N:

если N не является квадратом целого числа: +

если N является квадратом целого числа: ++. По данной рекуррентной формуле построим таблицу для всех значений от 1 до N:

Ответ : 627

Заключение

В данной работе приводится разбор и решение задач (части С) ЕГЭ по информатике методом динамического программирования. Динамическое программирование является одним из методов решения задач, в которых задачу большой размерности можно решать, опираясь на уже решенные задачи меньшего размера. Динамическое программирование может быть применено при выполнении следующих условий:

1) Существует способ выразить решение задачи через решение подзадач меньшей размерности. Этот способ задается рекуррентными соотношениями.

2) Существуют известные решения для задачи малой размерности (задача малой размерности решается просто).

Преимущество метода состоит в том, что раз уж задача решена,  ее ответ хранится и никогда не вычисляется заново.  Можно выделить два класса задач, решаемых методом динамического программирования.

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

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

Использованная литература :

1.Кузнецов А.В., Холод Н.И. Математическое программирование: [ Учеб. Пособие для эконом. спец. вузов]. – Мн.: Выш. шк., 1984. – 221 с.

2.Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2007. – 400 с

3.Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ,. 2-е издание, - М.: Издательский дом "Вильямс", 2005. - 1296 с.