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

 

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

      Сначала рассмотрим задачу в общей постановке. Если обозначить количество вопросов типа і через k_i, то задача принимает следующий вид:

      

      при ограничениях

      

      k_i-неотрицательные числа.

     Если  отбросить требования целочисленности  k_i, то решение задачи нетрудно найти с помощью симплекс-метода (см. Приложение В). В самом деле, так как остается лишь одно ограничение, базисной будет только одна переменная, и задача сводится к выбору типа і, для которого величина v_iW/w_i принимает максимальное значение. Исходная задача не является задачей линейного программирования, и для ее решения необходимо использовать метод динамического программирования. Следует отметить, что рассматриваемая задача может быть также решена с помощью методов целочисленного программирования.

     Каждый  из трех основных элементов модели ДП определяется следующим образом.

1. Этап  j ставится в соответствии типу j, j=1,2,…,N.
2. Состояние y_j на этапе j выражает суммарный вес вопросов, количество ответов на которые приняты на этапах j,j+1,…,N; при этом y₁=W и y_j=0,1,…,W при j=2,3,…,N.
3. Варианты решения k_j на этапе j описываются количеством вопросов типа j. Значение k_j заключено в пределах от нуля до [W/w_j], где [W/w_j]-целая часть числа (W/w_j).

      Пусть f_i(y_i)-максимальный суммарный вес вопросов, ответы на которые приняты на этапах j,j+1,…,N при заданном состоянии y_j.

      Рекуррентное  соотношение (для процедуры обратной прогонки) имеет следующий вид: 

      

      

 

      Заметим, что максимальное допустимое значение k_j ограничено величиной [y_j/w_j]. Это позволяет автоматически исключать все не являющиеся допустимыми варианты при заданном значении переменной состояния y_j.

      Решение исходной задачи:

         Этап 1.

      

        Этап 2.

      

      Этап 3.

           

      Этап 4.

           

      Этап 5.

           

      Этап 6.

      

      Этап 7.

      

      Этап 8.

           

      Оптимальное решение определяется теперь следующим  образом. Из условия W=30 следует, что первый этап решения задачи при y₁=30 дает оптимальное решение k₁=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут даны ответы. Далее находим:

        

      Соответственно оптимальным решением задачи является (0,0,4,1,0,0,5,7), соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 46.

 

    Заключение

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

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СПИСОК  ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 

1. Таха Х. Введение в исследование операций.–М.: Мир,1998.
2. Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1999г.
3. Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988.
4. Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
5. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,2000г.
6. Муну М. Математическое программирование. Теория алгоритмов. –М.: Наука,1999.
7. http://ru.wikipedia.orgЗ/wiki/   интернет-сайт.

 

ПРИЛОЖЕНИЕ  А

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

Паровозики

 

N локомотивов,  имеющих номера от 1 до N и установленных  на железнодорожную колею, начинают двигаться в одну сторону, причем локомотив номер k изначально движется со скоростью k км/ч. Если локомотив, движущийся с большей скоростью, нагоняет более медленный локомотив, дальше они движутся один за другим со скоростью впереди идущего локомотива. Очевидно, через некоторое время после начала движения локомотивы разобьются на несколько групп, движущихся с разной скоростью.

Программа, определяющая, сколько начальных расстановок s из N! Возможных дадут в результате p групп движущихся локомотивов.

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

Два числа  — 0 < N < 17 и 0 < p < N + 1.

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

Одно  число — s.

Рассмотрим  функцию от трех переменных F(X, Y, Z), которая показывает число расстановок при которых Y паровозиков образуют Z групп, причем самый первый паровозик имеет номер X. Для ответа достаточно просуммировать эту функцию по первой переменной. Разберем, чему наша функция равна. Возможны два варианта — первый паровозик образует отдельную группу или тормозит хотя бы один локомотив за собой. В первом случае необходимо суммировать выражения вида F(I, Y – 1, Z – 1) при I < X (действительно, если “наш паровоз вперед летит”, то лидер хвоста должен иметь меньший номер и при этом образуется на одну группу меньше). Во втором случае — F(I, Y – 1, Z) при I > X (лидер имеет больший номер и при этом образуется столько же групп).

function F(x, y, z : byte) : Tcal;

      var i : byte; s : Tcal;

      begin

            if D[x, y, z] = -1 then

            begin

                  s := 0;

                  for i := 1 to x - 1 do s := s + F(i, y - 1, z - 1);

                  for i := x + 1 to y do s := s + F(x, y - 1, z);

                  D[x, y, z] := s

            end;

            F := D[x, y, z]

      end;

Обратите  внимание на тип Tcal. Дело в том, что  типа LongInt недостаточно, поэтому требуется использование иных средств. В данном случае положение спасает тип Comp (Double тоже подходит).

ПРИЛОЖЕНИЕ B

Робот

В исследовательской  лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.

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

Во входном  файле находятся три числа  K, X и Y (0 <= K <= 16, |X|, |Y| <= 16), разделенные пробелами.

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

В выходной файл ваша программа должна поместить одно число — количество программ для робота.

В этой задаче мы впервые сталкиваемся с  функцией трех переменных: F(X, Y, Z) - показывает количество маршрутов длины Z, приводящих в клетку (X, Y). К сожалению, такая структура данных как

      Array [-16..16, -16..16, 0..16] of LongInt;

в память не помещается. Забудем пока об этой трудности и  напишем рекурсивную часть. Для ответа на поставленный в задаче вопрос можно посчитать число маршрутов длины Z - 1 в четыре клетки, смежных с заданной, а результаты сложить, не забывая случаи клеток на границе. Граничными условиями будут F(X, Y, 0) = 0, если хотя бы одна из координат X или Y отлична от нуля, и F(0, 0, 0) = 1. Действительно, если робота не двигать, то он может оказаться только в начале координат. Теперь вспомним о проблеме хранения данных. Выхода существует два. Первый, чисто программистский, заключается в разбиении большой структуры на несколько меньших и размещении их в динамической памяти. Сделать это можно, например, так

      Type  T1 = array[-16..16, -16..16] of LongInt;

            T2 = array [0..16] of ^T1;

      Var  D : T2;

Тогда наша функция будет записана так (предполагается, что память выделена, граничные условия введены, а для не вычисленных значений функции в массиве хранится "-1"):

Function F(X, Y, Z : integer) : longint;

      var s : longint;

      begin

            if D[Z]^[X, Y] = -1 then

            begin

               s := 0;

               if X <> -16 then s := s + F(X - 1, Y, Z - 1);

               if X <> 16 then s := s + F(X + 1, Y, Z - 1);

               if Y <> -16 then s := s + F(X, Y - 1, Z - 1);

               if Y <> 16 then s := s + F(X, Y + 1, Z - 1);

               D[Z]^[X, Y] := s

         end;

         F := D[Z]^[X, Y]

      end;

Для вычислений в некий момент времени необходимы данные только за предыдущий, что же происходило ранее, нас не интересует - с этим мы уже справились. Значит, достаточно хранить только 2 квадратные матрицы размером 3X1, - одна несет данные в предыдущий момент времени, а вторая вычисляется для текущего с использованием первой матрицы. После окончания расчета данные первой уже не нужны, ей присваиваем значение второй матрицы, увеличиваем счетчик времени и т.д. Ясно, что такую идею можно реализовать только итеративно.

for z := 1 to k do

  begin

   Way2 := Way1;

   for i := -16 to 16 do

    for j := -16 to 16 do

      begin

            s := 0;

            if i <> -16 then s := s + Way2[i - 1, j];

            if i <> 16 then  s := s + Way2[i + 1, j];

            if j <> -16 then s := s + Way2[i, j - 1];

            if j <> 16 then  s := s + Way2[i, j + 1];

            Way1[i, j] := s

      end

  end;