285
правок
Изменения
Нет описания правки
==Оптимальная подструктура==
[[Файл:C1515FG.JPGpng|320px150px|thumb|Производственная задача по определению оптимального способа сборки Граф подзадач для чисел Фибоначчи]]
Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.
Задача по нахождению кратчайшего пути между некоторыми вершинами графа (например, $S$<sub>$i,j$</sub>) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$<sub>$1,j-1$</sub> или $S$<sub>$2,j-2$</sub>). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.[[Файл:ULP.JPG|thumb|left|150px|Задача о самом длинном невзвешенном пути]]Иногда оптимальная структура может отсутствовать в задаче. Рассмотрим задачу, в которых имеется ориентированный граф $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|320px200px|thumb|left]]
Рассмотрим принцип оптимальности для динамического программирования на префиксе.
Задан граф. Требуется дойти от некоторой начальной вершины $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
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
