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

Рисунок 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.

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

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

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