Алгоритм наискорейшего спуска

@q74 · Регистрация: 14.11.2016

Студворк — интернет-сервис помощи студентам

Мне нужно найти локальные минимумы в массиве в пределах окрестности.
Прочитала про метод наискорейшего спуска, но везде в алгоритмах используется значение функции и вычисленная ее производная. Я не совсем понимаю, если у меня массив состоит из чисел:
x y f(x), где f(x) - значение функции, то о какой производной идет речь?

Можете дать какие-то наводки по решению данной задачи?

@q74 · 26.11.2016, 10:37 **[ТС]**

Как? Я пыталась с помощью рассмотрения окрестности из 8 - ми соседей - метод не всегда достоверный.

Добавлено через 5 минут
можете поподробнее? как перебрать? попытаться методом покоординатного спуска?

@Mr.X · 26.11.2016, 11:08

Сообщение от q74

Как? Я пыталась

Ну, вы задачу-то сформулируйте по-человечески, чтобы ее решить можно было.

IGPIGP · 26.11.2016, 12:11

Сообщение от q74

Я пыталась с помощью рассмотрения окрестности из 8 - ми соседей - метод не всегда достоверный.

q74, суть алгоритма в том же в чем и для нахождения минимума у функции одной переменной. Давайте посмотрим, что получается если с одной из сторон окрестности нет не возрастания ни убывания. Это значит - горизонтальный участок начался. То есть если где-то потом начнётся спуск - всё отбросить. А если набор, то это все минимумы. Для двумерного случая могут получаться плоские элементы произвольной формы. Ну и что?
То есть, если в одномерном случае итерация это смещение на ещё один примыкающий пиксел, то для двумерного это обход по ещё одному примыкающему контуру пикселей.
Тут чтобы легче жить, надо бы класс пиксел хорошо написать. Чтобы он умным был и умел отвечать на вопросы вроде:
gеt_neighbors - "дай соседей", gеt_smaller_neighbors "дай младшего из соседей" и пр.
Вообще задача не тривиальна. Нужно отслеживать обработанные области и выбрать алгоритм обхода.

Добавлено через 13 минут
И нужно выработать аксиоматику, которой потом следует придерживаться. Например:

Сообщение от IGPIGP

Для двумерного случая могут получаться плоские элементы произвольной формы. Ну и что?

Такой элемент это множество точек. Считать его набором минимумов? -Это самый простой путь. Но с точки зрения смысла для понятия "локальный минимум" это будет неверно. Тогда имеет смысл этот набор считать объектом. И следовательно объектом поиска является множество пикселей, которое для случая успешного обхода первой 8-мёрки вырождается до набора из одной штуки.

А можно упростить считая что локальный минимум это минимум только из одного пиксела. Тогда остальные будут нелокальными и отбрасываются. Это надо от задачи отталкиваться. То есть это "зависит от", - от смысла слова "локальный" в терминах Вашей задачи.

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

Если говорить о математике, то существует, например понятие, просто, локального экстремума и строгого локального экстремума:
https://www.google.ru/#newwind... 1%82%D0%BE

@q74 · 28.11.2016, 07:56 **[ТС]**

IGPIGP, сделала как Вы посоветывали, получился следующий код:

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
   
 
    int sizeNhood = 15;
 
    for(int j = sizeNhood; j <= h-sizeNhood-1; ++j){
        for(int i = sizeNhood; i <= w-sizeNhood-1; ++i){
            if(arr[i+j*w].z > arr[(i-sizeNhood)+(j-sizeNhood)*w].z) continue;
            else if(arr[i+j*w].z == arr[(i-sizeNhood)+(j-sizeNhood)*w].z){
                if(getNextNeighbors(arr, i, j, i-sizeNhood, j-sizeNhood, w-sizeNhood-1, h-sizeNhood-1, -1, -1)) continue;
            }
 
            if(arr[i+j*w].z > arr[i+(j-sizeNhood)*w].z) continue;
            else if(arr[i+j*w].z == arr[i+(j-sizeNhood)*w].z){
                if(getNextNeighbors(arr, i, j, i, j-sizeNhood, w-sizeNhood-1, h-sizeNhood-1, 0, -1)) continue;
            }
 
            if(arr[i+j*w].z > arr[(i+sizeNhood)+(j-sizeNhood)*w].z) continue;
            else if(arr[i+j*w].z == arr[(i+sizeNhood)+(j-sizeNhood)*w].z){
                if(getNextNeighbors(arr, i, j, i+sizeNhood, j-sizeNhood, w-sizeNhood-1, h-sizeNhood-1, 1, -1)) continue;
            }
 
            if(arr[i+j*w].z > arr[(i-sizeNhood)+j*w].z) continue;
            else if(arr[i+j*w].z == arr[(i-sizeNhood)+j*w].z){
                if(getNextNeighbors(arr, i, j, i-sizeNhood, j, w-sizeNhood-1, h-sizeNhood-1, -1, 0)) continue;
            }
 
            if(arr[i+j*w].z > arr[(i+sizeNhood)+j*w].z) continue;
            else if(arr[i+j*w].z == arr[(i+sizeNhood)+j*w].z){
                if(getNextNeighbors(arr, i, j, i+sizeNhood, j, w-sizeNhood-1, h-sizeNhood-1, 1, 0)) continue;
            }
 
            if(arr[i+j*w].z > arr[(i-sizeNhood)+(j+sizeNhood)*w].z) continue;
            else if(arr[i+j*w].z == arr[(i-sizeNhood)+(j+sizeNhood)*w].z){
                if(getNextNeighbors(arr, i, j, i-sizeNhood, j+sizeNhood, w-sizeNhood-1, h-sizeNhood-1, -1, 1)) continue;
            }
 
            if(arr[i+j*w].z > arr[i+(j+sizeNhood)*w].z) continue;
            else if(arr[i+j*w].z == arr[i+(j+sizeNhood)*w].z){
                if(getNextNeighbors(arr, i, j, i, j+sizeNhood, w-sizeNhood-1, h-sizeNhood-1, 0, 1)) continue;
            }
 
            if(arr[i+j*w].z > arr[(i+sizeNhood)+(j+sizeNhood)*w].z) continue;
            else if(arr[i+j*w].z == arr[(i+sizeNhood)+(j+sizeNhood)*w].z){
                if(getNextNeighbors(arr, i, j, i+sizeNhood, j+sizeNhood, w-sizeNhood-1, h-sizeNhood-1, 1, 1)) continue;
            }
 
                cout << arr[i+j*w].y << " " << arr[i+j*w].x << " " << arr[i+j*w].z << endl;
        }
    }
 
    // Функция рассмотрения ближайшего соседа
bool getNextNeighbors(vector<Point3D> &arr, int i, int j, int I, int J, int w, int h, int x, int y){
    if(x==-1 && y==-1){ I--; J--; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(x==0 && y==-1){ J--; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(x==1 && y==-1){ I++; J--; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(x==-1 && y==0){ I--; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(x==1 && y==0){ I++; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(x==-1 && y==1){ I--; J++; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(x==0 && y==1){ J++; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(x==1 && y==1){ I++; J++; if(I<0 || J<0 || I>w+1 || J>h+1) return 0; }
    if(arr[i+j*w].z < arr[I+J*w].z) return false;
    if(arr[i+j*w].z > arr[I+J*w].z) return true;
    if(arr[i+j*w].z == arr[I+J*w].z) getNextNeighbors(arr, i, j, I, J, w, h, x, y);
}

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

IGPIGP · 28.11.2016, 15:49

Сообщение от q74

сделала как Вы посоветывали

Такой код смотреть без комментариев не каждому под силу. Я не могу, например.

Вообще, такие вещи без ООП это подвиг. Я бы написал классы. Потом если где-то захочется скорости можно порефакторить. Но обычно, если задача выглядит тяжеловато, с таким желанием легко справиться.
Главное вот в чём, с моей точки зрения. Раз Вы пошли в атаку, значит такие вопросы как:

Сообщение от IGPIGP

нужно выработать аксиоматику, которой потом следует придерживаться

Вы для себя решили. А нам ничего не говорите.

Что касается большого кода с вопросом "почему не работает?", то это философская риторика. Помните Гамлета с черпом новой опреационки в руке? Есть такой всеобщий закон: Понятие "правильно" для большого кода это нонсенс. Есть конечно и практически идеальные вещи. И под словом "практически" тихо живут не злые и умные баги, каждый из которых это всё знает.

Что касается "сталактитов", то я как спелиолог спелиологине Вам скажу. Нужно копать. У Вас табличная форма задания функции ведь. Как Вы получили этот рельеф?

Добавлено через 4 часа 50 минут
q74, еще момент. Если таблица у Вас нарезана равными интервалами $https://www.cyberforum.ru/cgi-bin/latex.cgi?\Delta x, \Delta y$ , то окрестностью любого значения являются ближайшие значения - точки. То есть, сплошная плоскость из точек. Почему бы не находить "частные" производные по направлению? Я имею ввиду, то что у каждой точки 8 соседей и Вы можете вычислить восемь приближённых значений ( в конечных разностях) производных. По их значениям Вы получаете направления спусков (их может быть быть аж до 8-ми штук если начинать с максимума. Если с краю начинать, то в максимум сам алгоритм не должен пустить.
То есть, обойдя точку Вы получаете список точек для дальнейшего обхода. Некоторое старые производные можно не выбрасывать, а использовать повторно. То есть если начальная точка 0, а обход с левого нижнего угла: 1, 2, 3, 4, 5, 6, 7, 8
то имеем восемь производных:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{\Delta z_{1}}{\Delta s_{1}} ; \frac{\Delta z_{2}}{\Delta s_{2}} ; . . . ; \frac{\Delta z_{8}}{\Delta s_{8}}$
где i-тое приращение z это $https://www.cyberforum.ru/cgi-bin/latex.cgi?\Delta z_{i} = z_{i} - z_{0}$ , а с s-ками такая же история:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\Delta s_i = \sqrt{\Delta x_i ^2 + \Delta y_i ^2}$
а знак по направлению из i в 0
Тогда если минимальные отрицательные значения получились для точек 3 и 6 то , при обходе 3 у Вас уже есть производная в точке 7, а для точки 6 - в точке 2. Нужно только знаки поменять.
Интересная задача.

Что-то никто из математиков не ведётся. Ну ничего, не горюйте. Кто-то, да обязательно не выдержит.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35

	Алгоритм наискорейшего спуска 21.11.2016, 09:56. Показов 5041. Ответов 24 Метки нет (Все метки) Мне нужно найти локальные минимумы в массиве в пределах окрестности. Прочитала про метод наискорейшего спуска, но везде в алгоритмах используется значение функции и вычисленная ее производная. Я не совсем понимаю, если у меня массив состоит из чисел: x y f(x), где f(x) - значение функции, то о какой производной идет речь? Можете дать какие-то наводки по решению данной задачи? 0

@q74 0 / 0 / 0 Регистрация: 14.11.2016 Сообщений: 35
	26.11.2016, 10:37 [ТС]
	Как? Я пыталась с помощью рассмотрения окрестности из 8 - ми соседей - метод не всегда достоверный. Добавлено через 5 минут можете поподробнее? как перебрать? попытаться методом покоординатного спуска? 0