Подскажите алгоритм
От: Khimik  
Дата: 06.10.19 14:30
Оценка:
Я уже выкладывал на форуме свою программу для обработки данных коммерческих рыболовных эхолотов:

http://rsdn.org/forum/shareware/7483435.all
Автор: Khimik
Дата: 01.07.19


  Скрытый текст


Моя программа строит карту глубин. В данном случае карта – это двумерный массив точек. Алгоритм заключается в том, что сводится к минимуму некий функционал – сумма двух слагаемых, домноженных на выбранные коэффициенты. Первое слагаемое – средняя разница между «экспериментальными” точками (полученными на эхолоте) и точками модели (точнее, средний квадрат разницы). Чем меньше это число, тем лучше совпадает модель с замерами эхолотов (в местах где проводились замеры, само собой). Второе слагаемое – средний квадрат разности между каждыми соседними точками модели, можно сказать что это интеграл от квадрата первой производной на модели. Чем меньше это число – тем более «гладкая” выходит модель.
Коэффициент, на которых домножается второе слагаемое, характеризует значимость первого и второго слагаемого. Если первое слишком значимо (этот коэффициент мал), модель будет слишком подстраиваться под ошибки измерений; если второе слишком значимо, модель будет слишком гладкая и некорректно описывать замеры (в предельном случае это будет одна горизонтальная плоскость, единое число для всех точек модели).
Мой алгоритм минимизирует функционал методом градиентного спуска. К сожалению, такой подход жутко медленный – модель считается раз в тысячу медленнее, чем у других программ такого рода.
Я знаю что можно ускорить расчёт, если заменить градиентный спуск на построение системы линейных уравнений. Для одномерно варианта задачи у меня это довольно легко вышло, но в двумерном варианте получается что-то ужасно сложное. Система линейных уравнений двумерна, но её можно в данном случае назвать четырёхмерной, поскольку число строк и столбцов в ней – это общее число точек в модели, т.е. произведение длины модели на ширину.
В текущем варианте моя программа годится только для малых водоёмов (для средних расчёт модели длится слишком долго), но я слышал что для них рыбаки эхолотами не пользуются.
Может кто-нибудь подсказать более простой алгоритм для моей задачи? Это может быть либо другой способ минимизации описанного функционала, либо замена его на какие-нибудь сплайны или лагранжевы функции.
Мне кажется, должен существовать алгоритм итерационный, но «менее итерационный” чем градиентный спуск и соответственно более быстрый. Я не знаю как это называется, я бы описал это словом «самосогласованное схождение к минимуму”.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.