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