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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<wikitex>
 
<wikitex>
==Оптимальность для подзадач==
+
==Процесс разработки алгоритмов динамического программирования==
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве,  термин оптимальности для подзадач может быть различным, но, в целом, он формулируется так:
+
В процессе составления алгоритма задачи с динамическим программированием, требуется следовать последовательности из четырёх шагов:
{{Определение
+
# Описать структуру оптимального решения
|definition = «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}
+
# Рекурсивно определить значение оптимального решения
 +
# Вычислить значение оптимального решения с помощью метода восходящего анализа
 +
# Составление оптимального решения на основе полученной информации
  
 
==Оптимальная подструктура==
 
==Оптимальная подструктура==
 +
[[Файл:C1515.JPG|320px|thumb|Производственная задача по определению оптимального способа сборки ]]
 
Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.
 
Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.
  
Задача по нахождению кратчайшего  пути до некоторой вершины графа (например, $S$<sub>$i,j$</sub>) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$<sub>$1,j-1$</sub> или $S$<sub>$2,j-2$</sub>). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.
+
Задача по нахождению кратчайшего  пути между некоторыми вершинами графа (например, $S$<sub>$i,j$</sub>) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$<sub>$1,j-1$</sub> или $S$<sub>$2,j-2$</sub>). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.
 +
 
 +
==Оптимальность для подзадач==
 +
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так:
 +
{{Определение
 +
|definition = «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}
  
 
==Принцип оптимальности для динамического программирования на префиксе==
 
==Принцип оптимальности для динамического программирования на префиксе==
Строка 22: Строка 30:
 
*[http://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC#.D0.9E.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D0.B4.D0.BB.D1.8F_.D0.BF.D0.BE.D0.B4.D0.B7.D0.B0.D0.B4.D0.B0.D1.87|Википедия, Жадный алгоритм]
 
*[http://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC#.D0.9E.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D0.B4.D0.BB.D1.8F_.D0.BF.D0.BE.D0.B4.D0.B7.D0.B0.D0.B4.D0.B0.D1.87|Википедия, Жадный алгоритм]
 
*Т. Кормен. «Алгоритмы. Построение и анализ» (2<sup>ое</sup>издание, Глава 15)
 
*Т. Кормен. «Алгоритмы. Построение и анализ» (2<sup>ое</sup>издание, Глава 15)
 +
*T. H. Cormen. «Introduction to Algorithms» (3<sup>rd</sup>edidion, Chapter 15)
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]

Версия 04:28, 29 ноября 2011

<wikitex>

Процесс разработки алгоритмов динамического программирования

В процессе составления алгоритма задачи с динамическим программированием, требуется следовать последовательности из четырёх шагов:

  1. Описать структуру оптимального решения
  2. Рекурсивно определить значение оптимального решения
  3. Вычислить значение оптимального решения с помощью метода восходящего анализа
  4. Составление оптимального решения на основе полученной информации

Оптимальная подструктура

Производственная задача по определению оптимального способа сборки

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

Задача по нахождению кратчайшего пути между некоторыми вершинами графа (например, $S$$i,j$) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$$1,j-1$ или $S$$2,j-2$). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.

Оптимальность для подзадач

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

Определение:
«Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»


Принцип оптимальности для динамического программирования на префиксе

ST.jpg

Рассмотрим принцип оптимальности для динамического программирования на префиксе.

Задан граф. Требуется дойти от $S$ до $T$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Есть какой-то префикс, оптимальный путь проходит через $U$. Рассмотрим префикс $\Delta U$ (т.е. путь $S \rightsquigarrow U$ ), пусть он неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. </wikitex>

Ссылки

  • Лекция 10.11.2011
  • Жадный алгоритм
  • Т. Кормен. «Алгоритмы. Построение и анализ» (2оеиздание, Глава 15)
  • T. H. Cormen. «Introduction to Algorithms» (3rdedidion, Chapter 15)