Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.02.2011, 16:21
Новичок

Отправить личное сообщение для Любитель алгоритмов Посмотреть профиль Найти все сообщения от Любитель алгоритмов
 
Регистрация: 14.02.2011
Сообщений: 6

Поиск экстремума случайной функции
Всем привет. Есть такой вопрос: Можно ли найти наибольшее значение случайной функции быстрее, чем полным перебором? Нужно для ускорения вычислений, т.к. значение функции для каждого аргумента долго считается. Возможно, можно как-то обойтись без расчета всех элементов и их перебора? Или для случайной функции ускорить процесс невозможно?
  #2  
Старый 14.02.2011, 16:47
гocть

 
Сообщений: n/a

что значит случайная функция? произвольная непрерывная, гладкая? гауссовский процесс может? как вы вообще представляете себе "полный перебор" значений аргумента непрерывной функции???
  #3  
Старый 14.02.2011, 17:03
Новичок

Отправить личное сообщение для Любитель алгоритмов Посмотреть профиль Найти все сообщения от Любитель алгоритмов
 
Регистрация: 14.02.2011
Сообщений: 6

Сообщение от гocть Посмотреть сообщение
что значит случайная функция? произвольная непрерывная, гладкая? гауссовский процесс может? как вы вообще представляете себе "полный перебор" значений аргумента непрерывной функции???
Дискретно меняется аргумент от 11 до 101 с шагом 2, например(аргумент нечетный). Для каждого значения аргумента я делаю расчет(численный, т.к. аналитическая зависимость неизвестна, считается долго), и получаю значение функции. Среди всех этих значений надо определить максимальное чтобы запомнить соответствующий аргумент. Дискретно непрерывная(определена на всех натуральных числах больше ноля), про гладкость, извините, ничего не могу сказать, т.к. не знаю, что это такое. Характер поведения не знаю(закон распределения значений), случайная, значит, что у нее может быть несколько локальных максимумов, а найти надо главный. Полный перебор - расчет всех значений функции для каждого значения аргумента.

Последний раз редактировалось Любитель алгоритмов, 14.02.2011 в 17:46.
  #4  
Старый 14.02.2011, 17:37
гocть

 
Сообщений: n/a

ну раз вы ничего про свою функцию не знаете, то только полный перебор или эвристики какие-нибудь: генетические алгоритмы, имитация отжига, дифференциальная эволиция и т.п.
  #5  
Старый 14.02.2011, 17:43
Новичок

Отправить личное сообщение для Любитель алгоритмов Посмотреть профиль Найти все сообщения от Любитель алгоритмов
 
Регистрация: 14.02.2011
Сообщений: 6

Есть идея считать меньше точек, скажем, 10% равномерно отстоящих, по ним сделать квдратичную или кубическую интерполяцию, потом по полученной формуле аналитически определить максимум. Только, я так понимаю, это будет очень неточно для много-экстремальной зависимости - на месте максимума параболы может и реальный минимум попасть?
  #6  
Старый 14.02.2011, 17:49
Новичок

Отправить личное сообщение для Любитель алгоритмов Посмотреть профиль Найти все сообщения от Любитель алгоритмов
 
Регистрация: 14.02.2011
Сообщений: 6

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Моделирование случайной величины гость Математические алгоритмы (другое) 12 27.11.2009 02:42
Синтаксис и функции С++ CryVIC Ltd. Реализация, исходники, языки 16 17.11.2009 21:00
Поиск экстремума гость Математические алгоритмы (другое) 1 12.05.2009 23:00
булевы функции гость Математические алгоритмы (другое) 1 24.04.2009 19:44
поиск корня многомерной разрывной, зато монотонной, функции гость Математические алгоритмы (другое) 1 19.12.2007 09:38