:: алгоритмы  и методы ::
:: олимпиадные задачи ::
:: связь ::
:: форум ::
:: о сайте ::
:: ссылки ::

Path: Разное » Динамическое программирование
  Динамическое программирование



Кантор И. по статье Бразгалова Е.

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


  Задача:



Числа Фибоначчи.

Вычислить N чисел в последовательности Фибоначчи, — 1, 1, 2, 3, 5, 8, … — в которой первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих. N меньше 100.

Самый очевидный способ 'решения' задачи состоит в написании рекурсивной функции примерно следующего вида:

    Function F(X:integer):longint;
    Begin
          if (X=1) or (X=2) then F:=1 else F := F(X-1) + F(X-2)
    end;

При этом на шестом-седьмом десятке программа 'подвесит' самый быстрый компьютер. Попробуем разобраться, почему так происходит?

Для вычисления F(40) мы сперва вычисляем F(39) и F(38). Причем F(38) мы считаем “по новой”, “забывая”, что уже вычислили его, когда считали F(39).

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

Var D : Array [1..100] of LongInt;

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

Функция принимает следующий вид (не верьте, пожалуйста, книгам, утверждающим, что искать числа Фибоначчи рекурсивно нельзя в принципе — можно, если отсечение делать с умом):

    Function F(X : integer) : LongInt;
    Begin
      if D[X] = 0 then
            if (X=1) or (X=2)
            then D[X] := 1
            else D[X] := F(x-1) + F(x-2);
      F := D[X]
    End;

Этот подход динамического программирования называется подходом 'сверху вниз'. Он запоминает решенные задачи, но очередность решения задач все равно контролирует рекурсия.

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

        D[1] := 1; D[2] := 1;
        For i := 3 to X do
                  D[i] := D[i-1] + D[i-2];

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

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

Общий совет таков: ишите и тестируйте рекурсивную форму, а переделыванием занимайтесь, если ваша программа превышает отведенное ей время на 'больших' тестах.

Обсудить на форуме »


  Комментарии для веб-мастера






Автор: Sergey
Время: 23-11-03 03:33


Ребята, статейку - то уберите, не портите авторитет ресурса.  

  




Автор: Лара
Время: 18-12-03 08:57


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

  




Автор: Сергей
Время: 12-01-04 09:09


  Похоже веб-мастер этого сайта давно забил на вас всех, и вообще на этот 
сайт, так что все ваши распинания, и понты бесполезны.
  УВЫ!
  

  




Автор: Юрий
Время: 13-02-04 08:50


Не знаю что вы так набросились на автора замечательная статья для 
чайников! Сложный пример брать не стоит, т.к. это должно было быть очень 
простое не замысловатое! Очень простой пример, ярко показывает, основную 
идею динамического программирования - запоминание результатов предыдущих 
действий вместо вычисления их заново! А то что многие слышали про Белмана 
и что это из области оптимизации всего лишь показуха, какие они крутые! 
 
Особенно видно их крутость, что они один за одним показывают 
"оптимальные" варианты вычисления чисел Фибонночи, видимо, даже 
не подозревая, что на самом деле они вычисляются совсем без цикла! Читайте 
теорию алгебры!  

  




Автор: dimka
Время: 19-02-04 03:25


A nicego tupee ne mog pridumati????  

  




Автор: Куат
Время: 28-02-04 01:07


Грамотно  

  




Автор: Куат
Время: 28-02-04 01:11


Конечно пример примитивный но я думаю все поймут...  

  




Автор: Куат
Время: 28-02-04 01:12


Отстой я соглашаюсь с Ларой  

  





Автор: Yurik
Время: 22-03-04 12:04


I sink then it more better
  

 var
  a,b: longint;
  i,n: byte;
 begin
  readln(n);
  a:= 1;
  b:= 
1;
  if n>2 then
    for i:= 3 to n do
    begin
      a:= 
a+b;
      b:= a-b;
    end;
  writeln(a);
 end.  

  




Автор: Yurik
Время: 22-03-04 12:04


Web master lamaka!!!
  

  




Автор: Без имени
Время: 31-03-04 11:55


  

  

Ваши комментарии. Вопросы будут удалены: для них есть форум.
Имя:
E-mail:
  


Copyright 2000-2002 © Ilia Kantor, при поддержке проекта MANUAL.RU

АлгоЛист на CD