Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.60/25: Рейтинг темы: голосов - 25, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 14.11.2016
Сообщений: 35

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

21.11.2016, 09:56. Показов 5329. Ответов 24
Метки нет (Все метки)

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

Можете дать какие-то наводки по решению данной задачи?
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
21.11.2016, 09:56
Ответы с готовыми решениями:

Метод наискорейшего спуска
#include "stdafx.h" #include <iostream> #include <cmath> #include <math.h> #include <conio.h> #include <iomanip> #include...

Метод наискорейшего спуска
Доброго времени суток! Возникла проблема с реализацией программы. Не понимаю ни алгоритма, ни к чему нужна матрица, ни, соответсвенно,...

Метод наискорейшего спуска зацикливает
Код: #include <iostream> #include <cmath> #include <cstdio> #include <iostream> #ifndef GRADIENTSP_H #define GRADIENTSP_H...

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

Добавлено через 5 минут
можете поподробнее? как перебрать? попытаться методом покоординатного спуска?
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
26.11.2016, 11:08
Цитата Сообщение от q74 Посмотреть сообщение
Как? Я пыталась
Ну, вы задачу-то сформулируйте по-человечески, чтобы ее решить можно было.
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
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
1
0 / 0 / 0
Регистрация: 14.11.2016
Сообщений: 35
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);
}
Не могу понять, почему при выводе графика в матлабе с отмеченными минимумами, у меня захватываются еще и соседние пиксели, значения в которых явно больше, чем в локальном минимуме.
Миниатюры
Алгоритм наискорейшего спуска  
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
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. Нужно только знаки поменять.
Интересная задача.
Что-то никто из математиков не ведётся. Ну ничего, не горюйте. Кто-то, да обязательно не выдержит.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
28.11.2016, 15:49

Поиск минимума функции методом наискорейшего спуска
Добрый день. Передо мной встала задача: реализовать поиск минимума функции градиентным методом наискорейшего спуска. Я программу решила...

Метод наискорейшего спуска: переделать для поиска максимума
если код для метода скорейшего спуска на нахождение минимума, а нужно переделать под находжение максимума. подскажите как это сделать ? вот...

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

написать алгоритм, вычисляющий, какое количество единиц топлива необходимо для спуска с высоты A до высоты B
Имя входного файла input.txt ...

Из консоли на форму (программа нахождения экстремума функции методом наискорейшего спуска)
Здравствуйте, у меня есть программа нахождения экстремума функции методом наискорейшего спуска в консоли С++ и в делфи(с формой). Помогите...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
25
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru