Здравствуйте! Столкнулся со следующей задачей, может кто подскажет идею.

Задана кусочно-линейная функция из N участков линейности. Вопрос: существует ли другая кусочно-линейная функция, отстоящая от данной не более чем на B и содержащая не более M участков линейности.
Отстоящая не более, чем на В, означает, что: |f(x) - g(x)| <= B  для любого x из [a;b].
Нужен наиболее оптимальный алгоритм решения этой задачи. Все варианты алгоритмов переборного типа не подходят.

Попробуйте объединять по 2 участка

и вообще, если линейная функция отстоит на B от двух заданных точек, то она отстоит на B и от отрезка

подозреваю что нада юзать мат анализ - определять "производные" исходной функции, экстремумы
т.е. если у 1й функции k экстремумов, то и у 2й должно быть k экстремумов, соотв. M не менее k + 2 (+2 на концах)
потом нада смотреть вторые "производные" и т.д.

Можно переформулировать задачу: найти кусочно-линейную функцию из не более чем N участков линейности, лежащую в определенном многоугольнике(с двумя параллельными цепями сторон). Как это помогает в решении, пока не могу понять.



Не очень понимаю какие "производные" можно анализировать, если функция кусочно-линейная. Тут первая производная уже не непрерывна и есть просто кусочно-постоянная. А экстремумы могут быть только в точках, где заканчивается линейный участок, но искомая функция от них увы не зависит. Например, можно представить "пилу" у которой зубья отстоят не более, чем на B / 2 - тогда искомая функция постоянна, несмотря на количество экстремумов у исходной.

По-моему, тут надо построить некий хитрый граф, а дальше воспользоваться поиском пути или что-то вроде того. Мат анализ тут не поможет(

Это сообщение отредактировал(а) Sirt - 4.3.2009, 02:23

полностью согласен


Это смотря как их применить.

Ну вот примерно такой алгоритм можно попробывать:
Получается у каждой точки исходного графика есть свой интервал допустимых значений [y - B; y + B].
1 проход: Сначала пробуем удалить точку 2 и посчитать ее координату Y по прямой от 1 и 3 точек. Если попали в допустимый промежуток, значит точка 2 нам больше не нужна. Если не попали можно попробывать поднять ее до возможного предела y + B (если это локальный минимум) или опустить до y - B (если это локальный максимум). Таким образом если мы и не уменьшим количество промежутков, то хотя бы сгладим график, что может пригодится для второго прохода. И так далее для других точек.
2 проход: Теперь пытаемся удалить точку 1 и посчитать координату, продлив линию от точек 2 и 3. Потом пытаемся удалить точку 2, с помощью линии 3,4 и т.д.
В третьем проходе можно попробывать передвигать точки не только по Y но и по X.

Это все примерно на глаз может сработать. Если почитать мат. анализ можно и поточнее что нибудь придумать.

Это сообщение отредактировал(а) C/L - 4.3.2009, 04:19

Или второй метод:

Упрощаем все до предела, то есть оставляем только первую и последнюю точку исходного графика. Строим график прямой и определяем получившуюся погрешность B. Если она нас устраивает - конец программы. Если нет - ищем глобальный экстремум и строим график уже по 3 точкам: первая, последняя и точка экстремума. Считаем получившуюся погрешность B. Если не устраивает, то в том промежутке где погрешность B не устраивает ищем локальный экстремум и разбиваем ее еще на 2.... и т.д.
А если экстремума нет, функция монотонно растет или падает, то берем точку наибольшего изгиба или изменения изгиба или изменения изменения изгиба... и т.д. Это эквивалентно второй, третьей, четвертой и т.д. производным обычных функций. Это как раз то, о чем писал GoldFinch.

Это сообщение отредактировал(а) C/L - 4.3.2009, 05:02

Можно попробовать поднять, а может как раз на исходном месте она больше пригодится дальше. Получаем 2 крайних варианта, причем каждый из них в худшем случае может дать свою независимую ветвь решения. Если не прошел один вариант, придется вернуться и пройти по другому. В итоге получаем переборный алгоритм не полиномиальной сложности.


Построение графика по трем точкам уже не однозначно, поскольку искомая функция вообще может не проходить ни по одной опорных точек исходной прямой. В итоге снова получаем переборный алгоритм.


В упор не понимаю, о чем тут речь. Изменения изгиба у исходной функции может быть только в одной из опорных точек. В этих точках первая производная будет иметь разрыв, в остальных - кусочно постоянна. Или в качестве эквивалента производных имеются ввиду функции, получаемые соединением не соседних опорных точек исходной функции?

через M+2 точек можно провести полином степени M+1
аппроксимируем методом наименьших квадратов исходные точки, затем преобразуем полином в отрезки, точками будут концы и нули полинома, и смотрим влазят ли точки в границы заданные B

Да конечно все производные могут быть определены только на непрерывных графиках. Но мы же можем найти максимум и минимум кусочно линейной функции просто сравнив все опорные точки. Для вычисления изгиба мы можем взять разность производных двух соседних интервалов. Это как у функций дискретного аргумента. Операции расчета производных любого порядка у них заменяются простыми арифметическими операциями. Да, всё это определено только на опорных точках. Если нужен алгоритм с изменением положения опорных точек, то этот конечно не подойдёт

Даны прямая и отрезок.
Думаю, что не нужно приводить доказательство того, что максимальное расстояние между ними достигается на одном из концов отрезка.

Если доказательства не нужно, то идем дальше.

Мы можем вообще выкинуть из головы первоначальную ломанную и переформулировать задачу.

Дано N точек. Нужно сконструировать кусочно-линейную непрерывную функцию, состоящую из наменьшего числа узлов, такую, что расстояние от нее до заданных течек не превышает наперед заданное число B. Расстояние вычисляется, как модуль разности.

Поехали.
Для заданного множества точек находим аппроксимационную прямую методом наименьших квадратов - классическая линейная регрессия.
Пробегаем по нашему множеству и находим самую дальнюю точку. Если расстояние от нее до прямой меньше или равно B, то задача решена. Если нет, то делим наше множество на две кучки. 
Вопрос: в какую кучку включать B: в левую или в правую?
Ответ: ни в какую. Только помним, что в этом варианте у нас может получиться не две, а одна кучка., если "плохая" точка - крайняя.
С каждой кучкой повторяем упражнение. Если внутри кучки все хорошо, то решаем вопрос о "плохой" точке. И еще нужно отделные прямые, принадлежащие разным кучкам, сшивать. Точки сшивания и будут теми самыми искомыми узлами 

Все это не столько алгоритм, сколько его грубая схема. Алгоритм все же, мне кажется, нужно оформлять на каком-то конкретном языке программирования.
Стоит, видимо заметить, что хотя алгоритм и будет работать (если не ошибаться в коде программы), то остается все же открытым вопрос об оптимальности найденного решения.
Для практических целей можно обойтись и без доказательства.
Если же речь о теоретической разраьотке, то...

В том то и проблема, что задача важна теоретически. В идеале, сам алгоритм должен быть оптимален по времени. Нужно не некоторое хорошее приближение исходной функции, а именно точный ответ на вопрос, существует ли приближение с заданным числом точек. Приведенные алгоритмы работают удачно, если они находят решение. А если нет - то совсем не обязательно, что его не существует.

Если нужен «железный» алгоритм для ответа на теоретический вопрос, то задача мне представляется еще проще.

С точки зрения скорости работы алгоритма «мерзопакостным» обстоятельством является то, что приближение нужно равномерное, а не, скажем, среднеквадратичное.
Но это, на мой взгляд, второй вопрос (скорость) - сначала нужно разобраться с первым: можно ли вообще приблизиться на M узлах?

Итак, нам нужен алгоритм, который бы точно отвечал на вопрос: можно или нет вписаться? То есть такой, что если он скажет «умерла», то она таки «умерла». Ответ «не знаю» нас не устраивает. Вопрос о том, сколько времени алгоритм будет размышлять над этим вопросом, нас временно не занимает.

Считаем, что точки отсортированы по аргументу.
Несущественное для задачи построения алгоритма упрощение: среди заданных точек нет совпадающих по x.
Существенное замечание. В предыдущем своем сообщении я, не подумавши, ляпнул о построении непрерывной кусочно-линейной функции. Это очень тяжелое ограничение, существенно влияющее на построение алгоритма. Так как в начальной постановке задачи о непрерывности не сказано ни слова, мы от этого ограничения бодро отказываемся.

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

Поехали.

1. Стартовое множество - первые две точки. Почти ничего считать не надо - прямую получаем сразу. Уклонение нулевое, так что все прекрасно.

2. В этом пункте нашего похода мы имеем некое множество точек и аппроксимационную прямую, удовлетворяющую нашим условиям.
Начинаем проверять величину уклонения следующих за нашим множеством точек  от имеющейся прямой, пока не споткнемся. Каждый раз, когда новая точка удовлетворяет критерию, мы ее добавляем в текущее множество. Никаких пересчетов прямой пока не делаем.
Как только споткнемся, идем в следующий пункт.

3. Обращаемся к функции A, подавая ей на вход текущее множество с присоединенной к нему точкой, на которой мы запнулись.
Сначала найденную прямую проверяем на «плохой» точке. Если критерий удовлетворен, то мы вынуждены проверить здесь все предыдущие точки. Если и здесь все хорошо, то возвращаемся в пункт 2. Если тест не проходит, то идем в пункт 4.

4. Теперь вызываем функцию B. Если найденная прямая нас удовлетворяет, то возвращаемся в пункт 2.. А если нет, то считаем текущее множество (без «плохой» точки) заполненным. Возвращаемся в пункт 1 для набора следующего участка, если мы не исчерпали лимит - то самое M. Ну а если исчерпали, то значит «умерла»!

Теперь об оптимизации и переборе.
МНК дает аналитическое решение – никаких итераций. Но мало этого. В процессе вычисления уклонений можно очень просто подготавливать все необходимые коэффициенты для этого метода. Тут очень хорошие перспективы для оптимизации.

А поиск равномерного приближения в предложенном алгоритме происходит только в критических случаях да еще в условиях, когда уже найдено очень хорошее начальное приближение.

Мне кажется, что все это никак не тянет на алгоритм перебора.

Если алгоритм не прерывать при достижении M участков, то на выходе будет получено некое решение.
В связи с этим можно поставить вопрос: является ли оно оптимальным равномерным приближением на наименьшем числе узлов?
Ответ отрицательный.