В информатике говорят, что проблема имеет оптимальную подструктуру, если оптимальное решение может быть построено из оптимальных решений ее подзадач. Это свойство используется для определения полезности динамического программирования и жадных алгоритмов для решения проблемы. [1]
Обычно для решения задачи с оптимальной подструктурой используется жадный алгоритм, если по индукции можно доказать, что он оптимален на каждом шаге. [1] В противном случае, если проблема также имеет перекрывающиеся подзадачи , используется динамическое программирование . Если нет подходящих жадных алгоритмов и проблема не может отображать перекрывающиеся подзадачи, часто длительный, но прямой поиск пространства решений является лучшей альтернативой.
При применении динамического программирования к математической оптимизации , Ричард Беллман «S Принцип оптимальности основан на идее о том , что для того , чтобы решить проблему оптимизации динамической от некоторого исходного периода т к некоторому заканчивающемуся периоду T , один неявно должен решать подзадачи , начиная с более поздние даты s , где t <s <T . Это пример оптимальной подструктуры. Принцип оптимальности используется для вывода уравнения Беллмана , которое показывает, как значение задачи, начиная с t , связано со значением задачи, начинающейся с s .
Пример [ править ]
Рассмотрите возможность поиска кратчайшего пути для передвижения между двумя городами на машине, как показано на рисунке 1. Такой пример, вероятно, покажет оптимальную подструктуру. То есть, если кратчайший маршрут из Сиэтла в Лос-Анджелес проходит через Портленд, а затем через Сакраменто, то кратчайший маршрут из Портленда в Лос-Анджелес должен проходить через Сакраменто. То есть проблема того, как добраться из Портленда в Лос-Анджелес, вложена в проблему того, как добраться из Сиэтла в Лос-Анджелес. (Волнистые линии на графике представляют решения подзадач.)
В качестве примера проблемы, которая вряд ли будет иметь оптимальную подструктуру, рассмотрим задачу поиска самого дешевого авиабилета из Буэнос-Айреса в Москву. Даже если этот билет включает остановки в Майами, а затем в Лондоне, мы не можем сделать вывод, что самый дешевый билет из Майами в Москву останавливается в Лондоне, потому что цена, по которой авиакомпания продает поездку на несколько рейсов, обычно не является суммой цен. при которой он будет продавать отдельные рейсы в поездке.
Определение [ править ]
Можно дать более формальное определение оптимальной подструктуры. Пусть «проблема» представляет собой набор «альтернатив», и пусть каждая альтернатива имеет соответствующую стоимость c (a) . Задача - найти набор альтернатив, минимизирующий c (a) . Предположим, что альтернативы можно разбить на подмножества, т.е. каждая альтернатива принадлежит только одному подмножеству. Предположим, что каждое подмножество имеет свою собственную функцию стоимости. Можно найти минимумы каждой из этих функций затрат, а также минимумы глобальной функции затрат, ограниченные одними и теми же подмножествами.. Если эти минимумы совпадают для каждого подмножества, то почти очевидно, что глобальный минимум может быть выбран не из полного набора альтернатив, а только из набора, который состоит из минимумов меньших локальных функций стоимости, которые мы определили. Если минимизация локальных функций является проблемой «более низкого порядка», и (в частности) если после конечного числа этих сокращений проблема становится тривиальной, то проблема имеет оптимальную подструктуру.
Проблемы с оптимальной подструктурой [ править ]
- Самая длинная общая проблема подпоследовательности
- Самая длинная возрастающая подпоследовательность
- Самая длинная палиндромная подстрока
- Кратчайший путь для всех пар
- Любая проблема, которую можно решить с помощью динамического программирования .
Проблемы без оптимальной подструктуры [ править ]
- Проблема самого длинного пути
- Самая низкая стоимость авиабилетов. (Используя онлайн-поиск рейсов, мы часто обнаруживаем, что самый дешевый рейс из аэропорта A в аэропорт B включает в себя одну стыковку через аэропорт C, но самый дешевый рейс из аэропорта A в аэропорт C предполагает стыковку через какой-либо другой аэропорт D.) Однако, если в задаче в качестве параметра используется максимальное количество пересадок, тогда у проблемы есть оптимальная подструктура: самый дешевый рейс из A в B с одним стыковкой - это либо прямой рейс; или перелет из A в пункт назначения C, плюс оптимальный прямой рейс из C в B.
См. Также [ править ]
Ссылки [ править ]
- ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009). Введение в алгоритмы (3-е изд.). MIT Press . ISBN 978-0-262-03384-8.
