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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функциональные  уравнения

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

Функциональные уравнения, весьма общий класс уравнений, в которых искомой является некоторая функция. К Функциональные уравнения по существу относятся дифференциальные уравнения, интегральные уравнения, уравнения в конечных разностях следует, однако, отметить, что название «Функциональные уравнения» обычно не относят к уравнениям этих типов. Под Функциональные уравнения в узком смысле слова понимают уравнения, в которых искомые функции связаны с известными функциями одного или нескольких переменных при помощи операции образования сложной функции. Функциональные уравнения можно также рассматривать как выражение свойства, характеризующего тот или иной класс функций [например, Функциональные уравнения (x) = f (—x) характеризует класс чётных функций,  Функциональные уравнения 

f (x + 1)= f (x) — класс функций, имеющих период 1, и т.д. 
 
   Одним из простейших Функциональные уравнения является уравнение  f (x + у)= f (x)+ f (y). Непрерывные решения этогоФункциональные уравнения имеют вид  f (x) = Cx. Однако в классе разрывных функций это Функциональные уравнения имеет и иные решения. С рассмотренным Функциональные уравнения связаны 
 
f (x + у)= f (x) f (y), f (xy)— f (x)+ f (y),   f (xy)= f (x) f (y), непрерывные решения которых имеют соответственно вид e^Cx, Clnx, x^a (x > 0). Т. о., эти Функциональные уравнения могут служить для определения показательной, логарифмической и степенной функций. 
 
  В теории аналитических функций Функциональные уравнения часто применяются для введения новых классов функций. Например, двоякопериодические функции характеризуются Функциональные уравнения f (z + а) = f (z) и f (z + b) = f (z), автоморфные функции —Функциональные уравнения f (s_az) = f (z), где {s_a} — некоторая группа дробно-линейных преобразований. Если функция известна в некоторой области, то знание для неё Функциональные уравнения позволяет расширить область определения этой функции. Например, Ф. у. f(x + 1) = f (x) для периодических функций позволяет определить их значение в любой точке по значениям на отрезке [0, 1]. Этим часто пользуются для аналитического продолжения функций комплексного переменного. Например, пользуясь Функциональные уравнения Г (z + 1) = zГ (z) и зная значения функции Г (z) (см. Гамма-функция) в полосе 0 £ Rez £ 1, можно продолжить её на всю плоскость z. 
  Условия симметрии, имеющиеся в какой-либо физической задаче, обусловливают определённые законы преобразования решений этой задачи при тех или иных преобразованиях координат. Этим определяются Функциональные уравнения, которым должно удовлетворять решение данной задачи. Значение соответствующих Функциональные уравнения во многих случаях облегчает нахождение решений. 
  Решения Функциональные уравнения могут быть как конкретными функциями, так и классами функций, зависящими от произвольных параметров или произвольных функций. Для некоторых Функциональные уравнения общее решение может быть найдено, если известны одно или несколько его частных решений. Например, общее решение Функциональные уравнения f (x) = f (ax) имеет вид j[w(x)], где j(x) — произвольная функция, а w(x) — частное решение этого Функциональные уравнения Для решения Функциональные уравнения их во многих случаях сводят к дифференциальным уравнениям. Этот метод даёт лишь решения, принадлежащие классу дифференцируемых функций. 
  Другим методом решения Функциональные уравнения является метод  итераций. Этот метод даёт, например, решение уравнения Абеля f[a(x)] = f (x) + 1 [где a(x) — заданная функция] и связанного с ним уравнения Шрёдера f[a(x)] = cf (x). А. Н. Коркин доказал, что если a(х) — аналитическая функция, то уравнение Абеля имеет аналитическое решение. Эти результаты, нашедшие применение в теории групп Ли (см.Непрерывные группы), привели в дальнейшем к созданию теории итераций аналитических функций. В некоторых случаях уравнение Абеля решается в конечном виде. Например, Функциональные уравнения f (xⁿ) = f (x) + 1 имеет частное решение  .