Войти
Рисунок 1 . Поиск кратчайшего пути с использованием оптимальной подструктуры. Числа обозначают длину пути; прямые линии обозначают одиночные ребра , волнистые линии обозначают кратчайшие пути, т. е. могут быть другие вершины, которые здесь не показаны. В информатике, говорят, что проблема имеет оптимальную подструктуру, если оптимальное решение может быть построено из оптимальных решений ее подзадач. Это свойство используется для определения полезности динамического программирования и жадных алгоритмов для проблемы.
Как правило, жадный алгоритм используется для решения проблемы с оптимальной подструктурой, если это может быть доказано с помощью индукция, что это оптимально на каждом шаге. В противном случае, при условии, что проблема также имеет перекрывающиеся подзадачи, используется динамическое программирование. Если нет подходящих жадных алгоритмов и проблема не может отображать перекрывающиеся подзадачи, часто длительный, но прямой поиск пространства решений является лучшей альтернативой.
В применении динамического программирования к математической оптимизации, Принцип оптимальности Ричарда Беллмана основан на идея о том, что для решения задачи динамической оптимизации от некоторого начального периода t до некоторого конечного периода T, нужно неявно решать подзадачи, начиная с более поздних дат s, где t
Рассмотрите возможность поиска кратчайшего пути для путешествия между двумя городами на машине, как показано на рисунке 1. Такой пример, вероятно, продемонстрирует оптимальную подструктуру. То есть, если кратчайший маршрут из Сиэтла в Лос-Анджелес проходит через Портленд, а затем через Сакраменто, то кратчайший маршрут из Портленда в Лос-Анджелес должен проходить через Сакраменто. То есть проблема того, как добраться из Портленда в Лос-Анджелес, вложена в проблему того, как добраться из Сиэтла в Лос-Анджелес. (Волнистые линии на графике представляют решения подзадач.)
В качестве примера проблемы, которая вряд ли будет иметь оптимальную подструктуру, рассмотрим задачу поиска самого дешевого авиабилета из Буэнос-Айреса в Москву. Даже если этот билет включает остановки в Майами, а затем в Лондоне, мы не можем сделать вывод, что самый дешевый билет из Майами в Москву останавливается в Лондоне, потому что цена, по которой авиакомпания продает поездку на несколько рейсов, обычно не является суммой цен. при которой он будет продавать отдельные рейсы в поездке.
Можно дать немного более формальное определение оптимальной подструктуры. Пусть «проблема» представляет собой набор «альтернатив», и пусть каждая альтернатива имеет соответствующую стоимость c (a). Задача состоит в том, чтобы найти набор альтернатив, минимизирующий c (a). Предположим, что альтернативы можно разделить на подмножества, т.е. каждая альтернатива принадлежит только одному подмножеству. Предположим, что каждое подмножество имеет свою собственную функцию стоимости. Можно найти минимумы каждой из этих функций затрат, а также минимумы глобальной функции затрат, ограниченные одними и теми же подмножествами. Если эти минимумы совпадают для каждого подмножества, то почти очевидно, что глобальный минимум может быть выбран не из полного набора альтернатив, а только из набора, который состоит из минимумов меньших локальных функций стоимости, которые мы определили. Если минимизация локальных функций является проблемой «более низкого порядка», и (в частности) если после конечного числа этих сокращений проблема становится тривиальной, то проблема имеет оптимальную подструктуру.
