Разработка алгоритма

Для начала вспомним, какие ингредиенты необходимы для алгоритма динамиче- ского программирования (см. в конце раздела 6.2). Это полиномиальное количе- ство подзадач, решения которых должны дать решение исходной задачи; и реше- ния этих подзадач должны строиться с использованием рекуррентного отношения.
Как и в случае задачи взвешенного интервального планирования, полезно пораз- мыслить над некоторыми простыми свойствами оптимального решения. Однако учтите, что прямой аналогии с задачей взвешенного интервального планирования здесь нет: в той задаче мы искали подмножество из n объектов, а здесь ищется способ разбиения n объектов.

Для сегментированной задачи наименьших квадратов очень полезно следующее наблюдение: последняя точкаpn принадлежит одному сегменту оптимального раз- биения, и этот сегмент начинается в некоторой более ранней точкер.. Подобные наблюдения могут подсказать правильное множество подзадач: зная последний сегмент р, ..., pn (рис. 6.9), мы можем исключить эти точки из рассмотрения и ре- курсивно решить задачу для оставшихся точек pl, ..., р r

Рис. 6.9. Возможное решение: подбираем один сегмент для точекр.,р. pn, после чего

переходим к поиску оптимального решения для оставшихся точек p1, p2 р. _1


Предположим, OPT(/) обозначает оптимальное решение для точекpl, ..., р., а e,, — минимальную погрешность для любой линии в отношении р., р.+ 1, ..., р.. (Запись OPT(0) = 0 используется как граничный случай.) Тогда приведенное выше наблю- дение означает следующее:

(6.6) Если последний сегмент оптимального решения состоит из точекр, ...,pn, то значение оптимального решения равно OPT(n) = ein + C + OPT(.

- 1).

Используя то же наблюдение для подзадачи, состоящей из точек p1, ..., р,, мы видим, что для получения OPT( .) необходимо найти лучший способ получения за- вершающего сегментар.,..., р — с оплатой погрешности и слагаемого C для этого сегмента — в сочетании с оптимальным решением OPT(. - 1) для остальных точек. Другими словами, мы обосновали следующее рекуррентное отношение:

(6.7) Для подзадачи с точками p1, ..., р.

а сегментр., ...,р используется в оптимальном решении подзадачи в том и только в том случае, если минимум достигается при использовании индекса ί.

Самая сложная часть разработки алгоритма осталась позади. Далее можно про- сто строить решения OPT(.) в порядке возрастания ..

Segmented-Least-Squares (n)

Массив M[0... n]

Присвоить M[0] = 0 Для всех пар i < j

Вычислить наименьшую квадратичную погрешность e..

для сегмента p ............. Рj

Конец цикла

For j = 1,2.............. n

Использовать рекуррентное отношение (6.7) для вычисления M[j]

Конец For Вернуть M[n]

По аналогии с рассуждениями для взвешенного интервального планирования правильность этого алгоритма напрямую доказывается посредством индукции ((6.7) предоставляет шаг индукции).

Как и в алгоритме взвешенного интервального планирования, оптимальное разбиение вычисляется обратным отслеживанием по M.

Find-Segments( j)

Если j = 0

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

Найти значение i, минимизирующее e, + C + M[i - 1]

Вывести сегмент {p ............ p} и результат Find-Segments(i - 1)

Конец Если

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

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий
  18. Правило разработки графических схем
  19. Правило разработки графических схем
  20. Правило разработки веера версий