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

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

Версия 04:40, 5 декабря 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. Пусть вершины пронумерованы в порядке топологической сортировки и d(i, j) - ответ на задачу. Ясно, что d(i, i) = 0 и d(i, j) = infinity, если не существует путь от i до j. Путь от вершины i до j пересчитывается следующим образом: пусть для любого k (k = [i..j]), d(i, k) и d(k, j) посчитаны, тогда:

[math] d(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>