285
правок
Изменения
Нет описания правки
==Оптимальная подструктура==
Задача имеет оптимальную подструктуру, если её оптимальное решение может быть рационально
составлено из оптимальных решений её подзадач.
Наличие оптимальной подструктуры в задаче используется для определения применимости динамического программирования и жадных алгоритмов для решения оной.
[[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]]
Задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач. Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.
[[Файл:ULP.JPG|thumb|left|150px|Задача о самом длинном невзвешенном пути]]
Иногда оптимальная структура может отсутствовать в задаче.
Рассмотрим путь $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|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$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными.
