Формулировка задачи

Как и в приведенном выше описании, имеется множество точек P = {(xp у^, (x2, y2), ..., (xn,yn)}, в котором x1 < x2 < ... < xn.
Точка (х,у) будет обозначатьсяp. Сначала необходимо разбить P на некоторое количество сегментов. Каждый сег- мент является подмножеством P, представляющим непрерывный набор координат х; другими словами, это подмножество вида {p,, pi+1, ..., p p p} для некоторых ин- дексов i 0.

(ii) Для каждого сегмента — значение погрешности для оптимальной линии

через этот сегмент.

Нашей целью в сегментированной задаче наименьших квадратов является нахождение разбиения с минимальным штрафом. Минимизация этой характери- стики отражает компромиссы, упоминавшиеся ранее. При поиске решения могут рассматриваться разбиения на любое количество сегментов; с увеличением коли- чества сегментов уменьшаются слагаемые штрафа из части (ii) определения, но увеличивается слагаемое в части (i). (Множитель C предоставляется со входными данными; настраивая C, можно увеличить или уменьшить штраф за использование дополнительных линий.)

Количество возможных разбиений в P растет по экспоненте, и изначально не- понятно, возможен ли эффективный поиск оптимального разбиения. Сейчас мы покажем, как использовать динамическое программирование для нахождения минимального штрафа за время, полиномиальное по n.

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

Еще по теме Формулировка задачи:

  1. Глава 3. ФОРМУЛИРОВКА ВОПРОСОВ И КАЧЕСТВО АНКЕТЫ
  2. 4.3. «Эффект имени» при формулировке вопросов
  3. Требование формулировки "по Уставу"
  4. 3.1. Основные правила формулировки вопросов1
  5. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  6. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  7. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  8. ЗАДАЧА
  9. ЗАДАЧА: РЕШЕНИЕ
  10. Основные задачи.
  11. в) Задачи
  12. в) Задачи
  13. ПСИХОАНАЛИЗ: ЗАДАЧА