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

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

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

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

Динамическое программирование позволяет осуществлять оптимальное планирование управляемых процессов. Под «управляемыми» понимаются процессы, на ход которых мы можем в той или другой степени влиять.

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

• · Характеристика системы зависит только от данного состояния системы, а не от того каким путем система пришла в это состояние.
• · Переход системы из одного состояния в другое длится определенное конечное число шагов.
• · Каждый шаг (Выбор определенного решения) связан с определенным эффектом (под экономическим эффектом понимается значение целевой функции задачи). Эффект от принятого решения зависит от текущего состояния, в котором находится объект управления и принятого управленческого решения(воздействия).
• · Общий эффект за несколько шагов складывается из эффектов на каждом шаге.

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

Разбиение задачи на подзадачи меньшего размера.

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

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

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, $F\_3\; =\; F\_2\; +\; F\_1$ и $F\_4\; =\; F\_3\; +\; F\_2$ -- даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали $F\_2$ дважды. Если продолжать дальше и посчитать $F\_5$, то $F\_2$ посчитается ещё два раза, так как для вычисления $F\_5$ будут нужны опять $F\_3$ и $F\_4$. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

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

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

• · перекрывающиеся подзадачи;
• · оптимальная подструктура;
• · возможность запоминания решения часто встречающихся подзадач.

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

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

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme, Common Lisp, Perl), а в некоторых требует дополнительных расширений (C++).

Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных -- просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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

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

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

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

Энциклопедичный YouTube

• 1 / 5

  Словосочетание «динамическое программирование» впервые было использовано в -х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE . Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана , центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

  Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование », которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

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

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

  1. Разбиение задачи на подзадачи меньшего размера.
  2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм .
  3. Использование полученного решения подзадач для конструирования решения исходной задачи.

  Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

  Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , F 3 = F 2 + F 1 {\displaystyle F_{3}=F_{2}+F_{1}} и F 4 = F 3 + F 2 {\displaystyle F_{4}=F_{3}+F_{2}} - даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то F 2 {\displaystyle F_{2}} посчитается ещё два раза, так как для вычисления F 5 {\displaystyle F_{5}} будут нужны опять F 3 {\displaystyle F_{3}} и F 4 {\displaystyle F_{4}} . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

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

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

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

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

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

  Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Clojure , Perl), а в некоторых требует дополнительных расширений (C++).

  Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

  Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных - просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.

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

  Классические задачи динамического программирования

  • Задача о наибольшей общей подпоследовательности : даны две последовательности, требуется найти самую длинную общую подпоследовательность.
  • Задача поиска наибольшей увеличивающейся подпоследовательности : дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
  • Задача о редакционном расстоянии (расстояние Левенштейна) : даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
  • Задача о порядке перемножения матриц : даны матрицы A 1 {\displaystyle A_{1}} , …, A n {\displaystyle A_{n}} , требуется минимизировать количество скалярных операций для их перемножения.
  • Задача о выборе траектории
  • Задача последовательного принятия решения
  • Задача об использовании рабочей силы
  • Задача управления запасами

  ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, раздел оптимального управления, посвящённый теории и методам решения многошаговых задач. В задачах оптимального управления среди возможных управлений ищется то, при котором достигается экстремальное (наименьшее или наибольшее) значение так называемой целевой функции - некоторой числовой характеристики процесса. В динамическом программировании под многошаговостью понимают либо многоступенчатую структуру процесса, либо то, что управление разбивается на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Иногда многошаговость проистекает из существа процесса, но она может вводиться и искусственно для того, чтобы обеспечить возможность применения методов динамического программирования. Под программированием в динамическом программировании понимают принятие решений (планирование), а слово «динамическое» указывает на существенную роль времени и порядка выполнения операций. Методы динамического программирования являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (например, в задачах об оптимальном распределении ресурсов, в теории управления запасами, в задачах замены оборудования) и при решении многих технических проблем (например, в задачах управления последовательными химическими процессами, в задачах оптимальной прокладки дорог).

  Пусть процесс управления некоторой системой Х состоит из m шагов (этапов); на i-м шаге управление y i переводит систему из состояния x i-1 , в котором она находилась после (i - 1)-го шага, в новое состояние x i . При этом задана функция f i (х, у), и новое состояние определяется по этой функции значениями x i-1 , y i так, что x i = f i (x i-1 , y i), i = 1, 2,..., m. Таким образом, управления у 1 , у 2 , ..., у m переводят систему из начального состояния х 0 ∈ Х 0 в конечное состояние х m ∈ Х m , где Х 0 и Х m - совокупности допустимых начальных и конечных состояний системы Х.

  Одна из возможных постановок задач динамического программирования состоит в следующем. При заданном начальном состоянии х 0 требуется выбрать управления у 1 , у 2 , ..., у m таким образом, чтобы система Х перешла в допустимое конечное состояние и при этом заданная целевая функция F(х 0 , у 1 , х 1 ,..., у m , х m) достигла максимального значения F*, т. е.

  где максимум берётся по всем управлениям у 1 , ..., у m , для которых х m ∈ Х m .

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

  

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

  В основе динамического программирования лежит принцип оптимальности, сформулированный Р. Беллманом. Пусть выбраны некоторые управления у 1 , у 2 , ..., y k и тем самым траектория х 0 , х 1 , ...,x k состояний и требуется завершить процесс, т. е. выбрать у k+1 , ..., у m (а значит, и x k+1 , ..., х m).

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

  

  то и весь процесс не будет оптимальным. Пользуясь принципом оптимальности Беллмана, можно получить основное функциональное соотношение динамического программирования, которое состоит в следующем. Пусть ω m (х) = 0,

  k = 1, 2, ..., m, где максимум берётся по всем управлениям у, допустимым на шаге k. Соотношение, определяющее зависимость ω k-1 от ω k , называется уравнением Беллмана. Смысл этих функций достаточно ясен: если система на шаге k-1 оказалась в состоянии х, то ω k-1 (х) есть максимально возможное значение функции F k . Одновременно с построением функций ω k-1 (х) находятся условные оптимальные управления y k (х) на каждом шаге, т. е. значения оптимального управления при всевозможных предположениях о состоянии х системы на шаге k-1. Окончательно оптимальные управления находятся последовательным вычислением величин ω 0 (х 0) = F*, у 1 , х 1 , у 2 , ..., у m , x m .

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

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

  Строгое обоснование динамического программирования следует из результатов Л. С. Понтрягина и его учеников по математической теории управляемых процессов.

  Лит.: Беллман Р. Динамическое программирование. М., 1960; Математическая теория оптимальных процессов. М., 1961; Ховард Р. А. Динамическое программирование и марковские процессы. М., 1964; Хедли Дж. Нелинейное и динамическое программирование. М., 1967; Хедли Дж., Уайтин Т. Анализ систем управления запасами. М., 1969.

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

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

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

  Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

  Последовательности

  Классической задачей на последовательности является следующая.

  Последовательность Фибоначчи F n задается формулами: F 1 = 1, F 2 = 1,
  F n = F n - 1 + F n - 2 при n > 1. Необходимо найти F n по номеру n .

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

  Int F(int n) { if (n < 2) return 1; else return F(n - 1) + F(n - 2); }
  Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n , пока не дойдем до известных значений.

  Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

  Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

  Int F(int n) { if (A[n] != -1) return A[n]; if (n < 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
  Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

  F = 1; F = 1; for (i = 2; i < n; i++) F[i] = F + F;
  Такое решение можно назвать решением «с начала» — мы первым делом заполняем известные значения, затем находим первое неизвестное значение (F 3), потом следующее и т.д., пока не дойдем до нужного.

  Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F i для i < n ), затем, зная решения подзадач, нашли ответ (F n = F n - 1 + F n - 2 , F n - 1 и F n - 2 уже найдены).

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

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

  Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n 1 , n 2 , ..., n k . То есть мы можем говорить о функции T (n 1 , n 2 , ..., n k ), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
  T (i 1 , i 2 , ..., i k ) при i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

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

  При 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 1 = 2, K 2 = 3, K n = K n - 1 + K n - 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

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

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

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

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

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

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

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

  

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

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

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

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

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

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

  

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

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

  Задачи на подпоследовательности

  Рассмотрим задачу о возрастающей подпоследовательности.

  Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

  Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i . Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k - 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k - 1. Если
  A[i] < A[k], то k -ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k - 1:
  L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
  1 <= i < k .

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

  Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

  Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L = 1, а перед ним нет ни одного — N = 0. Далее,
  2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

  

  Меньше A = 5 только элемент A = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
  L = L + 1 = 2, N = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.

  

  Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

  Еще одной классической задачей динамического программирования является задача о палиндромах.

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

  Обозначим данную строку через S, а ее символы — через S[i], 1 <= i <= n . Будем рассматривать возможные подстроки данной строки с i -го по j -ый символ, обозначим их через S (i , j ). Длины максимальных палиндромов для подстрок будем записывать в квадратный массив L: L[i][j] — длина максимального палиндрома, который можно получить из подстроки S (i , j ).

  Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S (i , i )) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S (i , i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

  Пусть теперь нам дана подстрока S (i , j ). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S (i , j - 1) или S (i + 1, j ) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i], L[j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S (i + 1, j - 1):
  L[i][j] = L + 2.

  Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S (i , i ) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S (4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L — 2.

  Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
  L = L + 2. В остальных подстроках первая и последняя буквы различны.

  BAC: L = max(L, L) = 1.
  ACC: L = max(L, L) = 2.
  CCB: L = max(L, L) = 2.
  CBA: L = max(L, L) = 1.

  

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

  

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

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

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

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

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

  Динамическое программирование можно рассматривать как единую теорию благодаря единому набору идей и приемов, которые используются при математическом анализе различных задач. Эти идеи и приемы и составляют сущность динамического программи­рования. Беллман одним из первых понял суть принципа оптимальности и стал применять его ко многим оптимизационным задачам, возникающих в математике, технике, исследовании операций и в других областях.

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

  Характеризуя динамическое программирование, как набор математических процедур для оптимального управления дискретной системой, в общем виде задачу оптимального управления можно сформулировать следующим образом. В дискретные моменты времени t = 1, 2,..., N система находится в одном из множеств s i состояний, характеризуемых вектором состояния x (t) . Переход между последовательными состояниями осуществляется с помощью вектора управления u (t) по закону:

  x ( t ) = g ( t ) (x ( t ) , u ( t )) ; t = 1, 2,..., N

  Управления u (t) выбираются из множества допустимых управлений и образуют последовательность допустимых управлений u (0) ,u (1) ,…,u (N) . Последовательность допустимых управлений при заданном начальном состоянии х (0) определяет траекторию системы х (0) ,х (1) ,х (2) ,…,х (N) .

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

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

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

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

  Метод динамического программирования хорошо иллюстрируется на примере поиска кратчайшего пути между крайними узлами ориентированной сети. Рассмотрим некоторую ориентированную сеть, насчитывающую 12 узлов, которую нужно пройти от начального узла (1) до конечного узла (12) за четыре шага, передвигаясь с каждым шагом от узла к узлу.

  

  Рис. 6.4.1. Прохождение ориентированной сети по кратчайшему пути.

  Числа, указанные при дугах (i,j ) равны длинам дуг l ij между узлами i и j (в условных единицах). Возможные состояния системы s i в данном случае связаны с нахождением в i -м узле, управление u (t) связано с выбором направления пути на каждом шаге управления. Четыре шага управления u (1) ,...,u (4) последовательно переводят систему из начального состояния s 1 в конечное состояние s 12 и, таким образом, образуют некоторую траекторию, которую необходимо отыскать. В роли критериея оптимальности F в данном случае выступает длина траектории L , слагающаяся из длин отдельных дуг:

  Если поиски кратчайшего пути, т. е. оптимальной траектории, начинать не с начала, а сконца сети и двигаться в обратном направлении к началу, то в этом случае мы имеем алгоритм «обратной прогонки». В данном случае при реализации алгоритма обратной прогонки движение осуществляется от конечного состояния s 12 к начальному состоянию s 1 .

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

  Таблица 6.4.1

  i t	s 1	s 2	s 3	s 4	s 5	S 6	s 7	s 8	s 9	s 10	s 11
  									12	12 6
  						10	11 10
  			5
  1

  
  
  

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

  Заполнение таблицы начинается с первой строки, где хранится информация о последнем шаге пути. Последний, в данном случае четвертый шаг пути определен однозначно при переходе из любого предпоследнего состояния, которым может быть любое из трех возможных: s 9 , s 10 , s 11 . Поэтому оптимальное управление на последнем шаге очевидно. В зависимости от предпоследнего состояния вклад в критерий оптимальности L 4 (9) = 12, L 4 (10) = 6, либо L 4 (11) = 7. Эти значения вклада в L записываются в нижней части клеток первой строки табл. 6.4.1.

  Перед предпоследним – в данном случае третьим - шагом множество возможных состояний системы есть {s 5 , s 6 , s 7 , s 8 }. Применим теперь принцип Беллмана для определения траектории на третьем и четвертом шаге. Он заключается в том, что независимо от первых двух шагов управления отрезок траектории на последних двух шагах сам по себе является оптимальной траекторией, т.е. дает минимум вклада L 3 в критерий оптимальности.

  Если состояние системы перед предпоследним шагом есть состояние s 8 , то на последних шагах вклад в L определяется соотношением

  L 3 (s 5)=min{ }.

  Поскольку из s 5 возможны переходы в s 9 и s 11 .т.е.:

  g(s 5 ,9) = s 9 ; ; L 4 (s 9) = 12,

  g(s 5 ,11) = s 11 ; ; L 4 (s 11) = 7,

  L 3 (s 5) = min{6+12, 4+7} = 11 и u (3) = 11.

  Это означает, что если система находится в состоянии s 5 , то оптимальное управление заключается сначала в переходе в состояние s 11 , затем в состояние s 12 . Длина дуги из s 5 в s 12 при этом оказывается равна 11 единиц.

  Рассчитывая вклад в L аналогично для переходов из состояний s 6 , s 7 , s 8 , получим следующие вклады:

  L 3 (s 6)=min{7+12, 6+6)=12 , u (3) =10;

  L 3 (s 7)=min{5+6, 3+7)=10, u (3) =11;

  L 3 (s 8)=min{10+6, 12+7)=16, u (3) =10;

  Полученные четыре пары чисел записываются во вторую строку Табл. 6.4.1.

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

  L 2 (s 2) = min{ } = min{11+11, 14+10} = 22, u (2) = 5;

  L 2 (s 3) = min{ } = min{7+11, 9+12} = 18, u (2) = 5;

  L 2 (s 4) = min{ } = min{2+16, 3+12, 6+10} = 15, u (2) = 6;

  Полученные три пары чисел записываются в третью строку Табл.6.4.1.

  Начальное состояние s 1 определено однозначно, поэтому в последней строке таблицы заполняется единственная клетка, куда носятся значения 3 и 24 поскольку:

  L 1 (s 1) = min{ } = min{5+22, 6+18, 11+15} = 24, u (1) = 3.

  Теперь можно окончательно определить последовательность оптимального многошагового управления. На первом шаге u (1) = 3, т.е. из узла 1 переходим в узел 3, на втором шаге u (2) = 5, т.е. переходим в узел 5, далее после управления u (3) = 11 - в узел 11 и, наконец, в узел 12. Окончательно получаем, что кратчайший путь по сети, изображенной на Рис. 6.4.1, проходит по последовательности состояний s 1 →s 2 →s 5 →s 11 →s 12 , а его протяженность составляет 24 условных единиц.

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

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

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

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

  1. Исходная задача погружается во множество оптимизационных задач; при этом для каждого узла решается своя задача.

  2. Множество решений оптимизационных задач описывается функциональным уравнением, представляющим собой систему уравнений, которые связывают несколько оптимизационных задач. В такой системе каждое уравнение соответствует одному узлу и содержит обычно операторы типа min, mах или minimax справа от знака равенства, а переменные типа g i , и g j - по обе стороны от него.

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

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

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

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

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

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

  Множество S возможных (или наблюдаемых) состояний назы­вается пространством состояний, а элемент s из S определяет конкретное состояние. С каждым состоянием s связано множество D (s ) . Элемент d из множества D (s ) называется решением. Правило, согласно которому определяется допустимое решение для каждого состояния, называется стратегией d.

  Фактически страте­гия d ставит в соответствие каждому состоянию s некоторый эле­мент d(s ) из множества D (s ). Набор всех таких d образует про­странство стратегий D. Последнее означает, что выбор решения в некотором состоянии не ограничивает выбор во всех других состояниях. По существу, D представляет собой декартово произведение множеств D (s ) по s .

  Одна из идей динамического программирования состоит в том, каждой стратегии d должна соответствовать так называемая функция прибы­ли V d (s ), которую можно получить, исходя из состояния s и используя стратегию d. Понятие функции прибы­ли (или дохода) обобщает понятие вклада L t в общее значение критерия оптимальности L, рассматриваемое при решении задачи о кратчайшем пути.

  Выражение «используя стратегию d» означает, что в состоянии s выбирается решение d(s ); затем предполагается, что процесс перешел в состояние s " , т. е. реализуется состояние s ", в котором выбирается решение d(s "), и т. д. Функция прибыли имеет доволь­но сложную структуру, поскольку она зависит от последователь­ности состояний и решений, от вознаграждений, которые связаны с этими состояниями и решениями, а также от способа агрегиро­вания вознаграждений.

  Состояние представляет собой описание предыстории процесса со степенью подробности, позволяющей провести оценку текущих альтернативных решений. Основным свойством состояний является то, что состояние является краткой записью предыстории процесса, причем степень детализации позволяет определить локальную функцию дохода.Иными словами, локальная функция дохода может зависеть лишь от s , d и v.

  В следующей главе будут более подробно рассмотрены цепи Маркова, имеющие большое значение для моделирования временной эволюции производственных и технических систем. Существуют также Марковские модели принятия решений, в которых состояние s определяется некоторой парой чисел (n,i ) , решением является зависящая от них функция k , а локальная функция дохода определяется выражением типа h [(n , I ) , k, v ] = R k i (n ) + å j P k ij (n )v (n+ 1,j ) (n).

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

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

  Контрольные вопросы к главе 6.

  1. Из каких компонентов состоит ориентированная сеть?

  1. Как строится матрица пропускных способностей сети?

  1. Как образуется матрица потока в сети?

  1. Для чего вычитаются матрицы пропускных способностей и потоков?

  1. Что такое и для чего служит сетевой график?

  1. Как определяются времена раннего начала и раннего окончания работ?

  1. Что представляет собой общий резерв времени для некоторого события на сетевом графике?

  1. Как определяется критический путь?

  1. Что называется вектором состояния некоторой системы?

  1. Что представляет собой траектория системы в пространстве состояний?

  1. В чем заключается задача оптимального управления?

  1. Как формулируется критерий оптимальности?

  1. Что представляет собой динамическое программирование?

  1. Сформулируйте принцип оптимальности Беллмана.

  1. В чем сущность алгоритмов прямой и обратной прогонки при поиске кратчайшего пути?

  Варианты заданий к главе 6.

  Для сетей в каждом из вариантов:

  1) Найти максимальный поток из источника (1) в конечный узел сети – сток, полагая, что одно из чисел в скобках у каждой дуги (i, j) определяет пропускную способность дуги;

  1) Полагая, что дуги (1)®(2), (1)®(3) и т. д. определяют некоторые работы, минимальная и максимальная продолжительность которых заданы числами, указанными при соответствующих дугах, найти критический путь от начального события (1) до конечного;

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

  
  
  
  

  
  

  
  

  X 4