Динамическое программирование: различия между версиями

[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
мНет описания правки
Строка 9:
 
Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» [[программирование|программированию]] (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «[[математическое программирование]]», которое является синонимом слова «оптимизация».
Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенноеопределённое расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.
 
== Идея динамического программирования ==
Строка 15:
[[Файл:Fibonacci dynamic programming.svg|thumb|right|200px|Граф подзадач (ребро означает, что одна задача зависит от решения другой) для чисел Фибоначчи (граф — ациклический).]]
 
''Оптимальная подструктура'' в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса реберрёбер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
# Разбиение задачи на подзадачи меньшего размера.
# Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый [[алгоритм]].
Строка 35:
* восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого [[стек]]а и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.
 
Языки программирования могут запоминать результат вызова функции с определеннымопределённым набором аргументов ([[мемоизация]]), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, [[Scheme]], [[Common Lisp]], [[Clojure]], [[Perl]]), а в некоторых требует дополнительных расширений ([[C++]]).
 
Известны сериальное динамическое программирование, включённое во все учебники по [[исследование операций|исследованию операций]], и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.
 
Обычное динамическое программирование является частным случаем несериального динамического программирования, когда [[граф (математика)|граф]] взаимосвязей переменных — просто путь. НСДП, являясь естественным и общим методом для учетаучёта структуры задачи оптимизации, рассматривает множество ограничений и/или [[целевая функция|целевую функцию]] как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах.
 
Одним из основных свойств задач, решаемых с помощью динамического программирования, является [[аддитивность]]. Неаддитивные задачи решаются другими методами. Например, многие задачи по оптимизации инвестиций компании являются неаддитивными и решаются с помощью сравнения [[стоимость компании|стоимости компании]] при проведении инвестиций и без них.