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

      Далее мы будем о говорить об одномерном, двумерном и многомерном динамическом программировании при k = 1, k = 2, k > 2, соответственно.

      Следующая задача одномерного  динамического программирования  встречается в различных вариациях.

    Задача 1. Посчитать число последовательностей  нулей и единиц длины n, в которых  не встречаются две идущие подряд единицы.

      При n < 32 полный перебор потребует  нескольких секунд, а при n = 64 полный  перебор не осуществим в принципе. Для решения задачи методом  динамического программирования  сведем исходную задачу к подзадачам.

      При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли K_n – 1, K_n – 2 — число таких последовательностей длины n – 1 и n – 2.

      Посмотрим, какой может быть  последовательность длины n. Если  последний ее символ равен  0, то первые n – 1 — любая правильная последовательность длины

    n – 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего K_n – 1. Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые n – 2 символа — любая правильная последовательность длины n – 2, число таких последовательностей равно K_n – 2.

    

     .

    Таким образом, K₁ = 2, K₂ = 3, K_n = K_{n – 1} + K_{n – 2} при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

    5 Двумерное динамическое программирование.

      Классической задачей двумерного  динамического программирования  является задача о маршрутах  на прямоугольном поле.

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

      Приведем пару формулировок таких  задач:

    Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть  из левой верхней клетки в правую нижнюю.

    Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное  число. Необходимо попасть из верхней  левой клетки в правую нижнюю. Вес  маршрута вычисляется как сумма  чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным  весом.

    

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

      Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху  или слева, то есть из клеток  с координатами (i – 1, j) и (i, j – 1):

     .

    Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно 

     A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

      Теперь мы можем пройти последовательно  по строкам (или по столбцам) массива A, находя число маршрутов  для текущей клетки по приведенной  выше формуле. Предварительно  в A[0][0] необходимо поместить число  1.

      В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток  с координатами  (i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],

    

     W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке:

      W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j];

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

      На следующем рисунке приведен  пример исходных данных и одного  из шагов алгоритма.

     .

    В каждую из уже пройденных клеток ведет  ровно одна стрелка. Эта стрелка  показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке.

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

    

    

     Раздел 2. Практическая часть.  
 
 
 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 

 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СПИСОК  ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

Интернет-ресурсы:

   1) Bestreferat.ru

1.  Таха Х.  Введение в исследование операций.–М.: Мир,1985.

2.  Кузнецов  Ю. Н. Математическое программирование. –М.: Наука,1976.

3.  Вентцель  Е. С. Исследование операций. –М.: Наука,1976.

4.  Вентцель  Е. С. Элементы динамического  программирования. –М.: Наука,1987.

5.  Акоф Р., Сасиени  М. Основы исследования операций. –М.: Мир,1971.

6.  Вентцель  Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988.

7.  Карманов  В. Т. Математическое программирование. –М.:Наука,1986.

8.  Зайченко  Ю. П. Исследование операций. –К.: Высшая школа,1985.

9.  Аоки М.  Введение в методы оптимизации. –М.: Наука,1977.

10.    Беллман  Р., Дрейфус С. Прикладные задачи  динамического программирования. –М.: Наука,1965.

11.    Муну  М. Математическое программирование. Теория алгоритмов. –М.: Наука,1990.

   2) Bankreferatov.ru

   3) Wikipedia.ru

1. Беллман Р. Динамическое программирование. — М.: Изд-во иностранной литературы, 1960.
2. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
3. Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms = Algorithms — 1-е изд. — McGraw-Hill Science/Engineering/Math, 2006. — С. 336. — ISBN 0073523402.

4. Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в  примерах и задачах — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..
5. Bertele U., Brioshi F. Nonserial dynamic programming. — N.Y.: Academic Press, 1972. — 235 pp.
6. Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19.
7. Щербина О. А. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22. — c.21-36.
8. Габасов Р., Кириллова Ф. М. Основы динамического программирования. — Мн.: Изд-во БГУ, 1975. — 262 с.