Википедия

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

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Addbot (обсуждение | вклад)
535 049 правок
м Интервики (всего 28) перенесены на Викиданные, d:q380679
Строка 1:
'''Динамическое программирование''' в [[Теория управления|теории управления]] и [[Теория вычислений|теории вычислительных систем]] — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с {{нуженНе переводпереведено|есть=:en:Optimal substructure|нужно=Оптимальная подструктура|текст=оптимальной подструктурой}}, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
 
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Строка 6:
 
== История ==
Словосочетание «динамическое программирование» впервые было использовано в [[1940-е годы|1940]]-х годах [[Ричард Беллман|Р. Беллманом]] для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В [[1953]]  г. он уточнил это определение до современного. Первоначально эта область была основана, как [[системный анализ]] и инжиниринг, которая была признана [[IEEE]]. Вклад Беллмана в динамическое программирование был увековечен в названии [[уравнение Беллмана|уравнения Беллмана]], центрального результата теории динамического программирования, который переформулирует [[Оптимизация (математика)|оптимизационную]] задачу в [[рекурсия|рекурсивной]] форме.
 
Слово «программирование» в словосочетании «динамическое программирование» в действительности к "«традиционному"» [[программирование|программированию]] (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «[[математическое программирование]]», которое является синонимом слова «оптимизация».
Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.
 
== Идея динамического программирования ==
[[Файл:Оитмальная подструктура в графе.png|200px|right|thumb|Нахождение кратчайшего пути в графе из одной вершины в другую, используя оптимальную подструктуру; прямая линия обозначает простое ребро; волнистая линия обозначает кратчайший путь между вершинами, которые она соединяет (промежуточные вершины пути не показаны); жирной линией обозначен итоговый кратчайший путь.]]
[[Файл:Fibonacci dynamic programming.svg|thumb|right|200px|Граф подзадач (ребро означает, что одна задача зависит от решения другой) для чисел Фибоначчи (граф  — ациклический).]]
 
''Оптимальная подструктура'' в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
Строка 48:
* [[Расстояние Левенштейна|Задача о редакционном расстоянии (расстояние Левенштейна)]]: даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
* [[Числа Фибоначчи|Задача о вычислении чисел Фибоначчи]]
* [[Задача о порядке перемножения матриц]]: даны матрицы <math>A_1</math>, ...…, <math>A_n</math>, требуется минимизировать количество скалярных операций для их перемножения.
* [[Задача о выборе траектории]]
* [[Задача последовательного принятия решения]]
Строка 86:
* Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19.
* Щербина О. А. [http://www.dynsys.crimea.edu/issue/22/dynsys_22_Shcherbina.pdf Методологические аспекты динамического программирования] // Динамические системы, 2007, вып. 22. — c.21-36.
* Габасов Р., [[Кириллова, Фаина Михайловна|Кириллова Ф.  М. ]] Основы динамического программирования. — Мн.: Изд-во БГУ, 1975. — 262  с.
 
== Ссылки ==
* [http://logic.pdmi.ras.ru/~kulikov/simplealgscourse/lecture7-slides.pdf Слайды лекции о динамическом программировании].
* [http://informatics.mccme.ru/moodle/course/view.php?id=9 Теория, задачи, тестирующая система].
* [http://comp-science.narod.ru/WebPage/lesson2.htm Е. В.  Брызгалов Динамическое программирование]
 
 
Источник — https://ru.wikipedia.org/wiki/Динамическое_программирование