Введение

В информатике говорят, что проблема обладает оптимальной подструктурой, если оптимальное решение может быть построено из оптимальных решений её подзадач. Это свойство используется для оценки применимости жадных алгоритмов к решению проблемы. Как правило, жадный алгоритм применяется для решения проблемы с оптимальной подструктурой, если посредством индукции можно доказать, что он оптимален на каждом шаге. В противном случае, если проблема также характеризуется наличием перекрывающихся подзадач, могут быть использованы методы «разделяй и властвуй» или динамическое программирование. Если подходящих жадных алгоритмов нет, и проблема не демонстрирует перекрывающиеся подзадачи, часто наилучшим решением является длительный, но прямой поиск по пространству решений. При применении динамического программирования к задачам математической оптимизации принцип оптимальности Ричарда Беллмана основан на идее, что для решения задачи динамической оптимизации от начального момента времени t до конечного момента времени T необходимо неявно решать подзадачи, начиная с более поздних моментов времени s, где t < s < T. Это является примером оптимальной подструктуры. Принцип оптимальности используется для вывода уравнения Беллмана, которое показывает, как значение задачи, начинающейся с момента t, связано со значением задачи, начинающейся с момента s.

Пример

Рассмотрим задачу нахождения кратчайшего пути для поездки между двумя городами на автомобиле, как показано на рисунке 1. Такой пример, скорее всего, обладает оптимальной подструктурой. То есть, если кратчайший маршрут из Сиэтла в Лос-Анджелес проходит через Портленд, а затем через Сакраменто, то кратчайший маршрут из Портленда в Лос-Анджелес также должен проходить через Сакраменто. Таким образом, задача о том, как добраться из Портленда в Лос-Анджелес, является частью задачи о том, как добраться из Сиэтла в Лос-Анджелес. (Волнистые линии на графе представляют решения подзадач.) В качестве примера задачи, которая вряд ли обладает оптимальной подструктурой, рассмотрим задачу поиска самого дешевого авиабилета из Буэнос-Айреса в Москву. Даже если этот билет предполагает пересадки в Майами и затем в Лондоне, мы не можем заключить, что самый дешевый билет из Майами в Москву также включает пересадку в Лондоне, поскольку цена, по которой авиакомпания продает билет с несколькими рейсами, обычно не равна сумме цен на отдельные рейсы, входящие в этот билет.

Определение

Можно дать несколько более формальное определение оптимальной подструктуры. Пусть "проблема" – это набор "альтернатив", и пусть у каждой альтернативы есть связанная с ней стоимость, c(a). Задача состоит в том, чтобы найти набор альтернатив, минимизирующих c(a). Предположим, что альтернативы можно разбить на подмножества, то есть каждая альтернатива принадлежит только одному подмножеству. Предположим, что у каждого подмножества есть своя функция стоимости. Можно найти минимумы каждой из этих функций стоимости, а также минимумы глобальной функции стоимости, ограниченные теми же подмножествами. Если эти минимумы совпадают для каждого подмножества, то становится почти очевидным, что глобальный минимум можно выбрать не из полного набора альтернатив, а только из набора, состоящего из минимумов меньших, локальных функций стоимости, которые мы определили. Если минимизация локальных функций является задачей "более низкого порядка", и (в особенности) если после конечного числа таких упрощений задача становится тривиальной, то задача обладает оптимальной подструктурой.