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

Рисунок 1. Поиск кратчайшего пути с использованием оптимальной подструктуры. Числа обозначают длину пути; прямые линии обозначают одиночные края, волнистые линии обозначают самые короткие пути, т.е. могут быть другие вершины, которые здесь не показаны.

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

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

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

Пример

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

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

Определение

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

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

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

  • Проблема самого длинного пути
  • Самая низкая стоимость авиабилетов. (Используя онлайн-поиск рейсов, мы часто обнаруживаем, что самый дешевый рейс из аэропорта A в аэропорт B включает в себя одну стыковку через аэропорт C, но самый дешевый рейс из аэропорта A в аэропорт C предполагает стыковку через какой-либо другой аэропорт D.) Однако, если в задаче в качестве параметра используется максимальное количество пересадок, тогда у проблемы есть оптимальная подструктура: самый дешевый рейс из A в B с одним стыковкой - это либо прямой рейс; или перелет из A в пункт назначения C, плюс оптимальный прямой рейс из C в B.

Смотрите также

Рекомендации

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