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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 36: Строка 36:
  
 
== Принцип оптимальности на подотрезках==
 
== Принцип оптимальности на подотрезках==
Требуется посчитать функцию f(1, n). Принцип состоит в том, что мы пересчитываем f(u, v) через такие f(i, j), что <tex> u \le i \le j \le v </tex>. Данную задачу можно свести к следующей задаче: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер - любое вещественное число. Требуется найти кратчайший путь от вершины u до v. Пусть вершины пронумерованы в порядке топологической сортировки w(i, j) - величина ребра от i до j(если ребра не существует, то данно е значение првно infinity) и d(i, j) - ответ на задачу. Ясно, что d(i, i) = 0. Путь от вершины i до j пересчитывается следующим образом: пусть для любого k (k = [i..j]), d(i, k) и d(k, j) посчитаны, тогда: <br />
+
Требуется посчитать функцию f(1, n). Принцип состоит в том, что мы пересчитываем $f(u, v)$ через такие $f(i, j)$, что <tex> u \le i \le j \le v </tex>. Данную задачу можно свести к следующей задаче: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер - любое вещественное число. Требуется найти кратчайший путь от вершины $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)$ посчитаны, тогда: <br />
 
: <tex> d(i, j) = \min(w(i, j), \min\limits_{\mathop{k:i \rightsquigarrow k \rightsquigarrow j}} [d(i, k) + d(k, j)]) </tex> <br />
 
: <tex> d(i, j) = \min(w(i, j), \min\limits_{\mathop{k:i \rightsquigarrow k \rightsquigarrow j}} [d(i, k) + d(k, j)]) </tex> <br />
  
Ответ будет равен d(u, v).
+
Ответ будет равен $d(u, v)$.
  
  

Версия 06:10, 18 декабря 2011

<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>