Сегментированные наименьшие квадраты: многовариантный выбор

Перейдем к другой категории задач, которая демонстрирует чуть более сложную разновидность динамического программирования. В предыдущем разделе рекур- рентное отношение было разработанно на основе выбора, который был, по сути, бинарным: интервал n либо принадлежал оптимальному решению, либо не принад- лежал ему.
В задаче, рассматриваемой ниже, в рекуррентности будет задействовано то, что можно назвать «многовариантным выбором»: на каждом шаге существует
полиномиальное количество вариантов, которые могут рассматриваться как канди- даты для структуры оптимального решения. Как вы увидите, метод динамического программирования очень естественно адаптируется к этой более общей ситуации.

Отдельно стоит сказать о том, что задача этого раздела также хорошо показывает, как четкое алгоритмическое определение может формализовать понятие, изначально казавшееся слишком нечетким и нелогичным для математического представления.

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

Еще по теме Сегментированные наименьшие квадраты: многовариантный выбор:

  1. Линия наименьшего сопротивления
  2. Линии малого внутреннего квадрата
  3. Квадрат
  4. По пути наименьшего сопротивления. Построение гороскопа на компьютере
  5. Подготовка к интервью, или квадрат успеха
  6. Выбор линейного мышления - это выбор прожить жизнь в танце частиц.
  7. Выбор есть. Он существует всегда. Сознание - это выбор.
  8. ОБЪЕКТ СЕКСУАЛЬНЫЙ: ВЫБОР
  9. Финансирование выборов
  10. ВЫБОР МЕЖЛИЧНОСТНЫЙ: МОТИВАЦИЯ
  11. § 4. Выборы и референдум
  12. Элекция (выбор часа)
  13. Парламентские выборы
  14. РЕАКЦИЯ ВЫБОРА
  15. Вы в состоянии сделать выбор
  16. Организация выборов
  17. О собственном выборе