Рубрики

Оптимальное свойство субструктуры в динамическом программировании | ДП-2

Как мы обсуждали в наборе 1 , ниже приведены два основных свойства проблемы, которые предполагают, что данная проблема может быть решена с помощью динамического программирования:
1) Перекрывающиеся подзадачи
2) Оптимальная субструктура

Мы уже обсуждали свойство перекрывающей подзадачи в наборе 1 . Давайте обсудим свойство оптимальной субструктуры здесь.

2) Оптимальная подструктура: данная задача имеет свойство оптимальной подструктуры, если оптимальное решение данной проблемы может быть получено с помощью оптимальных решений ее подзадач.

Например, задача Кратчайшего пути имеет следующее свойство оптимальной подструктуры:
Если узел x лежит в кратчайшем пути от исходного узла u к узлу назначения v, то кратчайший путь от u до v является комбинацией кратчайшего пути от u до x и кратчайшего пути от x до v. Стандартные алгоритмы All Pair Shortest Path как Флойд-Варшалл и Беллман-Форд являются типичными примерами динамического программирования.

С другой стороны, проблема Longest Path не имеет свойства Optimal Substructure. Здесь под самым длинным путем мы подразумеваем самый длинный простой путь (путь без цикла) между двумя узлами. Рассмотрим следующий невзвешенный график, приведенный в книге CLRS . Есть два самых длинных пути от q до t: q → r → t и q → s → t. В отличие от кратчайших путей, эти самые длинные пути не имеют оптимального свойства субструктуры. Например, самый длинный путь q → r → t не является комбинацией самого длинного пути от q до r и самого длинного пути от r до t, потому что самый длинный путь от q до r — это q → s → t → r и самый длинный путь от r до t есть r → q → s → t.

Мы рассмотрим некоторые примеры проблем в будущих статьях по динамическому программированию .

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Ссылки:
http://en.wikipedia.org/wiki/Optimal_substructure
Книга CLRS

Рекомендуемые посты:

Оптимальное свойство субструктуры в динамическом программировании | ДП-2

0.00 (0%) 0 votes