Разработка алгоритма
Для сегментированной задачи наименьших квадратов очень полезно следующее наблюдение: последняя точка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
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
- Разработка Плана
- 2.7. Разработка анкеты
- 6. Разработка перспектив
- Разработка и принятие Основного закона
- Состояние научной разработки проблемы.
- Правило разработки веера версий
- Правило разработки графических схем
- Правило разработки графических схем
- Правило разработки веера версий