Вычисление решения помимо его значения

Пока что мы вычислили только значение оптимального решения; вероятно, также желательно получить полный оптимальный набор интервалов. Алгоритм M-Compute- Opt легко расширяется для отслеживания оптимального решения: можно создать дополнительный массив S, в элементе S[i] которого хранится оптимальное множе- ство интервалов из {1, 2, ..., i}.
Однако наивное расширение кода для сохранения решений в массиве S увеличит время выполнения с дополнительным множите- лем O(n): хотя позиция в массиве M может обновляться за время O(1), запись множества в массив S занимает время O(n). Чтобы избежать возрастания O(n), вместо явного хранения S можно восстановить оптимальное решение по значениям, хранящимся в массиве M после вычисления оптимального значения.

Из (6.2) известно, что j принадлежит оптимальному решению для множества интервалов {1, ..., j} в том, и только в том случае, если v. + OPT( p(j)) > OPT(j - 1). Воспользовавшись этим фактом, получаем простую процедуру, которая «прохо- дит в обратном направлении» по массиву M, чтобы найти множество интервалов оптимального решения.

Find-Solution (j)

Если j = 0

Ничего не выводить Иначе

Если v + M[p(j)] > M[j - 1]

Вывести j вместе С результатом Find-Solution(p(j))

Иначе

Вывести результат Find-Solution( j - 1)

Конец Если Конец Если

Поскольку Find-Solution рекурсивно вызывает себя только для строго меньших значений, всего делается O(n) рекурсивных вызовов; а так как на один вызов тра- тится постоянное время, имеем

(6.5) Для массива M с оптимальными значениями подзадач Find-Solution воз- вращает оптимальное решение за время O(n).

6.2.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Вычисление решения помимо его значения:

  1. § 32 Право распоряжения. – Двоякое его значение. – Отделение его от права собственности. – Добровольное и недобровольное. – Запрещение. – Действие его и форма. – Арест движимости. – Опека
  2. § 26 Идея усыновления и римское его учреждение. – Значение и формы его в новейших законодательствах. – Отношение воспитателя к воспитаннику во Франции. – Присоединение детей в Германии.
  3. § 4. Значение судебных и арбитражных решений
  4. §4. Решения Конституционного суда РФ, их виды и значение
  5. § 76 Историческое развитие идеи об авторском праве. – Значение его в новейшее время. – Сущность сего права. – Пределы его в русском законе. – Сроки и исчисления их для посмертных сочинений. – Удостоверение литературной собственности
  6. § 3 Сущность и идея брака. – Нравственное его значение. – Таин- ство в браке. – Историческое развитие идеи брака. – Много- женство, многомужие и одноженство. – Идея, семейное, обще- ственное и религиозное значение брака в Древнем мире. – Религиозный обряд брака у древних. – Строгая форма брака. – Освящение брака в христианстве. – Церковное понятие о браке на Западе и Востоке. – Секуляризация брака и подчинение его гражданскому закону и суду после реформации и революции. – Брачный закон и суд в Р
  7. РЕШЕНИЕ ПЕРЕВЕРНУЛО ЕГО ЖИЗНЬ
  8. § 61 Компания на акциях. – Сущность учреждения. – Цель его и историческое развитие. – Нынешнее ее значение. – Понятие об акции. – Образование компании. – Учредители. – Устав, утверждение его и регистрация. – Подписка на акции. – Органы управления. – Общее собрание акционеров. – Состав его, созыв и деятельность. – Правление. – Наблюдательный совет. – Понятие о дивиденде. – Выпуск новых акций. – Прекращение компании и ликвидация.
  9. СМЕЛОЕ РЕШЕНИЕ ИЗМЕНИЛО ЕГО ЖИЗНЬ
  10. Принятие решения о нововведении и подготовка программы его реализации.
  11. 12.2. Психологический реагент и его криминалистическое значение
  12. Правило критической самооценки принятого решения и действий по его исполнению.
  13. Право ребенка выражать свое мнение при решении любого вопроса, затрагивающего его интересы
  14. 4. Помимо чувствительности вы должны ориентировать ребенка и на воспитание душевной стойкости и чувства собственного достоинства
  15. 3. Значение системы гражданского права для законодатель-ства, его изучения и преподавания