Оптимальная подструктура

В информатике говорят, что проблема имеет оптимальную подструктуру , если оптимальное решение может быть построено из оптимальных решений ее подзадач. Это свойство используется для определения полезности жадных алгоритмов для решения задачи. ^[1]

Обычно жадный алгоритм используется для решения задачи с оптимальной подструктурой, если можно с помощью индукции доказать, что она оптимальна на каждом шаге. ^[1] В противном случае, если проблема содержит перекрывающиеся подзадачи также методы «разделяй и властвуй» или динамическое программирование , можно использовать . Если подходящих жадных алгоритмов нет и задача не содержит перекрывающихся подзадач, часто лучшей альтернативой является длительный, но простой поиск пространства решений.

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

Пример

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

В качестве примера задачи, которая вряд ли будет иметь оптимальную структуру, рассмотрим задачу поиска самого дешевого авиабилета из Буэнос-Айреса в Москву. Даже если этот билет включает в себя остановки в Майами, а затем в Лондоне, мы не можем заключить, что самый дешевый билет из Майами в Москву останавливается в Лондоне, потому что цена, по которой авиакомпания продает поездку с несколькими рейсами, обычно не является суммой цен. по которой он будет продавать отдельные рейсы в поездке.

Определение

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

Проблемы с оптимальным основанием

Проблема самой длинной общей подпоследовательности
Самая длинная возрастающая подпоследовательность
Самая длинная палиндромная подстрока
Кратчайший путь для всех пар
Любая проблема, которую можно решить с помощью динамического программирования .

Проблемы без оптимальной подструктуры

Задача о самом длинном пути
Возведение в степень по цепочке сложения
Самый дешевый тариф авиакомпании. Используя онлайн-поиск рейсов, мы часто обнаруживаем, что самый дешевый рейс из аэропорта A в аэропорт B предполагает одну пересадку через аэропорт C, но самый дешевый рейс из аэропорта A в аэропорт C предполагает пересадку через какой-либо другой аэропорт D. Однако, если Задача принимает в качестве параметра максимальное количество остановок, то задача имеет оптимальную подструктуру. Самый дешевый рейс из А в Б, который включает не более k остановок, — это либо прямой рейс; или самый дешевый рейс из A в какой-либо аэропорт C, который включает не более t остановок для некоторого целого числа t с 0≤t<k , плюс самый дешевый рейс из C в B, который включает не более k−1−t остановок.

См. также

Ссылки

^ Перейти обратно: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009). Введение в алгоритмы (3-е изд.). МТИ Пресс . ISBN 978-0-262-03384-8 .

[cormen-1] Перейти обратно: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009). Введение в алгоритмы (3-е изд.). МТИ Пресс . ISBN 978-0-262-03384-8 .

[1]