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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
  
 
==Оптимальная подструктура==
 
==Оптимальная подструктура==
 +
Задача имеет оптимальную подструктуру, если её оптимальное решение может быть рационально
 +
составлено из оптимальных решений её подзадач.
 +
Наличие оптимальной подструктуры в задаче используется для определения применимости динамического программирования и жадных алгоритмов для решения оной.
 
[[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]]
 
[[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]]
Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.
+
Многие задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.
  
Задача по нахождению кратчайшего  пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач. Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.
+
Задача по нахождению кратчайшего  пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач.  
 
[[Файл:ULP.JPG|thumb|left|150px|Задача о самом длинном невзвешенном пути]]
 
[[Файл:ULP.JPG|thumb|left|150px|Задача о самом длинном невзвешенном пути]]
 
Иногда оптимальная структура может отсутствовать в задаче.   
 
Иногда оптимальная структура может отсутствовать в задаче.   
Строка 18: Строка 21:
 
Рассмотрим путь $q \rightarrow r \rightarrow t$, который является самым длинным простым путем $q \rightsquigarrow t$. Является ли путь $q \rightarrow r$ самым длинным путем $q \rightsquigarrow r$? Нет, поскольку простой путь $q \rightarrow s \rightarrow t \rightarrow r$ длиннее. Является ли путь $r \rightarrow t$ самым длинным путем $r \rightsquigarrow t$? Снова нет, поскольку простой путь $r \rightarrow q \rightarrow s \rightarrow t$ длиннее.  
 
Рассмотрим путь $q \rightarrow r \rightarrow t$, который является самым длинным простым путем $q \rightsquigarrow t$. Является ли путь $q \rightarrow r$ самым длинным путем $q \rightsquigarrow r$? Нет, поскольку простой путь $q \rightarrow s \rightarrow t \rightarrow r$ длиннее. Является ли путь $r \rightarrow t$ самым длинным путем $r \rightsquigarrow t$? Снова нет, поскольку простой путь $r \rightarrow q \rightarrow s \rightarrow t$ длиннее.  
 
Таким образом, в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это NP-полная задача, т.е. вряд ли ее можно решить в течение полиномиального времени.  
 
Таким образом, в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это NP-полная задача, т.е. вряд ли ее можно решить в течение полиномиального времени.  
 
 
  
  
 
==Оптимальность для подзадач==
 
==Оптимальность для подзадач==
 
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так:
 
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так:
{{Определение
+
«Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его  
|definition = «Если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}
+
нужно использовать для решения задачи в целом»
  
 
==Принцип оптимальности на префиксе==
 
==Принцип оптимальности на префиксе==
 
[[Файл:ST.jpg|200px|thumb|left]]
 
[[Файл:ST.jpg|200px|thumb|left]]
Рассмотрим некий необратимый процесс производства, например, производство консервов и представим его в виде ориентированного и ациклического графа. Предположим, что есть свиноферма и свиньи, которые выращиваются и отправляются на завод, чтобы стать консервами. Началом производства обозначим вершину графа $S$, а конец производства $T$. Процесс требует оптимизации, т.е. требуется найти наиболее оптимальный путь $S \rightsquigarrow T$. Он проходит через вершину графа $U$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Теперь рассмотрим принцип оптимальности для динамического программирования на префиксе. Итак, имеем некоторый оптимальный путь $S \rightsquigarrow T$, который проходит через $U$. Пусть префикс $ \Delta U$, т.е. путь от $S \rightsquigarrow U$, не оптимален. Тогда заменим неоптимальную часть $S \rightsquigarrow U$ пути $S \rightsquigarrow T$ оптимальной, а путь $U \rightsquigarrow T$ добавим в конец. Получим более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными.
+
Рассмотрим некий необратимый процесс производства, например, производство консервов и представим его в виде ориентированного и ациклического графа. Предположим, что есть свиноферма и свиньи, которые проходят ряд состояний (например, выращиваются, забиваются и отправляются на завод консервов), чтобы стать консервами. Началом производства (первым состоянием) обозначим вершину графа $S$, а конец производства (последнее состояние) $T$. Процесс требует оптимизации, т.е. требуется найти наиболее оптимальный путь $S \rightsquigarrow T$. Он проходит через вершину графа $U$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Теперь рассмотрим принцип оптимальности для динамического программирования на префиксе. Итак, имеем некоторый оптимальный путь $S \rightsquigarrow T$, который проходит через $U$. Пусть префикс $ \Delta U$, т.е. путь от $S \rightsquigarrow U$, не оптимален. Тогда заменим неоптимальную часть $S \rightsquigarrow U$ пути $S \rightsquigarrow T$ оптимальной, а путь $U \rightsquigarrow T$ добавим в конец. Получим более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными.
  
  

Версия 04:57, 14 января 2012

<wikitex>

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

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

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

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

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

Наличие оптимальной подструктуры в задаче используется для определения применимости динамического программирования и жадных алгоритмов для решения оной.

Граф подзадач для чисел Фибоначчи

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

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

Задача о самом длинном невзвешенном пути

Иногда оптимальная структура может отсутствовать в задаче. Рассмотрим задачу, в которой имеется ориентированный граф $G = (V, E)$ и вершины $u, v \in V$, задачу по определению простого пути от вершины $u$ к вершине $v$, состоящий из максимального количества рёбер.

Рассмотрим путь $q \rightarrow r \rightarrow t$, который является самым длинным простым путем $q \rightsquigarrow t$. Является ли путь $q \rightarrow r$ самым длинным путем $q \rightsquigarrow r$? Нет, поскольку простой путь $q \rightarrow s \rightarrow t \rightarrow r$ длиннее. Является ли путь $r \rightarrow t$ самым длинным путем $r \rightsquigarrow t$? Снова нет, поскольку простой путь $r \rightarrow q \rightarrow s \rightarrow t$ длиннее. Таким образом, в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это NP-полная задача, т.е. вряд ли ее можно решить в течение полиномиального времени.


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

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

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

Принцип оптимальности на префиксе

ST.jpg

Рассмотрим некий необратимый процесс производства, например, производство консервов и представим его в виде ориентированного и ациклического графа. Предположим, что есть свиноферма и свиньи, которые проходят ряд состояний (например, выращиваются, забиваются и отправляются на завод консервов), чтобы стать консервами. Началом производства (первым состоянием) обозначим вершину графа $S$, а конец производства (последнее состояние) $T$. Процесс требует оптимизации, т.е. требуется найти наиболее оптимальный путь $S \rightsquigarrow T$. Он проходит через вершину графа $U$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Теперь рассмотрим принцип оптимальности для динамического программирования на префиксе. Итак, имеем некоторый оптимальный путь $S \rightsquigarrow T$, который проходит через $U$. Пусть префикс $ \Delta U$, т.е. путь от $S \rightsquigarrow U$, не оптимален. Тогда заменим неоптимальную часть $S \rightsquigarrow U$ пути $S \rightsquigarrow T$ оптимальной, а путь $U \rightsquigarrow T$ добавим в конец. Получим более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными.


Примеры задач

Принцип оптимальности на подотрезках

Требуется посчитать функцию $f(1, n)$. Принцип состоит в том, что мы пересчитываем $f(u, v)$ через такие $f(i, j)$, что [math] u \le i \le j \le v [/math]. Данную задачу можно свести к следующей задаче: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер - любое вещественное число. Требуется найти кратчайший путь от вершины $u$ до $v$. Пусть вершины пронумерованы в порядке топологической сортировки $w(i, j)$ - величина ребра от $i$ до $j$(если ребра не существует, то данное значение равно $\infty$) и $d(i, j)$ - ответ на задачу. Ясно, что $d(i, i) = 0$. Путь от вершины $i$ до $j$ пересчитывается следующим образом: пусть для любого $k$ $(k = [i..j])$, $d(i, k)$ и $d(k, j)$ посчитаны, тогда:

[math] d(i, j) = \min(w(i, j), \min\limits_{\mathop{k:i \rightsquigarrow k \rightsquigarrow j}} [d(i, k) + d(k, j)]) [/math]

Ответ будет равен $d(u, v)$.


Примеры задач

Принцип оптимальности на подмножествах

Ссылки

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

</wikitex>