285
правок
Изменения
Нет описания правки
==Оптимальная подструктура==
Задача имеет оптимальную подструктуру, если её оптимальное решение может быть рационально составлено из оптимальных решений её подзадач.
Наличие оптимальной подструктуры в задаче используется для определения применимости динамического программирования и жадных алгоритмов для решения оной. Например, задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач.
[[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]]
Многие задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой. Например, задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач.
[[Файл:ULP.JPG|thumb|left|150px|Задача о самом длинном невзвешенном пути]]
