Как найти локальный экстремум в таблице значений функции N переменных

yurijm123

Предположим, есть файл, в котором содержится таблица значений функции N переменных. Функция аналитически не задана. Нужно найти в этой таблице точки, отвечающие локальным минимумам и максимумам. Как это сделать?

BSCurt

если F(x)< F(y) для всех y соседних с x, то х лок минимум?

yurijm123

Да

Vlad128

и типа ты хочешь сэкономить константу? Типа ускорить в два раза выполнение за счет какой-то хитрости?

griz_a

Возьмем любую таблицу, выберем в ней любую ячейку. При любых значениях вокруг мы можем сделать из нее локальный минимум, а можем сделать не локальный минимум. Значит все точки перебрать все равно придется, число операций не менее n. Тупой перебор дает примерно (3^N-1)n, где n - число точек. Менее тупой поиск локальных экстремумов по каждой горизонтальной прямой дает 2N сравнений для поиска локальных экстремумов по направлению, затем для каждого из этих экстремумов по 2 сравнения по второму направлению и т.д.
Итого если функция часто колеблющаяся, то никакого сокращения, а если нет - то довольно эффективно.

Romyk

Совершенно случайно занимаюсь примерно похожим
На питоне можно использовать вот это
http://docs.scipy.org/doc/scipy-dev/reference/generated/scip...
Работает и по многомерному массиву (пробую в 3d причем именно так как тут пишут выше по треду - сравнивает соседние пиксели (причем можно задать сколько!) по каждой оси координат. То есть в 3д сравниваться будут 6 точек, а не как мне хочется - по всему кубику 3х3х3.
Оставить комментарий
Имя или ник:
Комментарий: