Метод перебора - История изменений

Patarakin в 18:07, 19 октября 2022

2022-10-19T18:07:12Z

@@ Строка 1: / Строка 1: @@
 '''Метод перебора (метод равномерного поиска, перебор по сетке)''' — простейший из методов поиска значений действительно-значных [[Функция (математика)|функций]] по какому-либо из критериев сравнения (на [[максимум]], на [[минимум]], на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной [[Оптимизация (математика)|оптимизации]].
@@ Строка 28: / Строка 27: @@
 Тогда в худшем случае [[интервал неопределённости]] имеет длину <math>\frac{(b-a)}{(n/2+1)}+\delta</math>.
 [[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:54:59Z

1 версия импортирована

← Предыдущая версия	Версия от 20:54, 19 октября 2022
(нет различий)

ru_wikipedia>Deltahead: откат правок 31.129.246.100 (обс.) к версии Ochkarik

2021-05-20T10:17:06Z

откат правок 31.129.246.100 (обс.) к версии Ochkarik

Новая страница

{{Значения|Перебор}}
'''Метод перебора (метод равномерного поиска, перебор по сетке)''' — простейший из методов поиска значений действительно-значных [[Функция (математика)|функций]] по какому-либо из критериев сравнения (на [[максимум]], на [[минимум]], на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной [[Оптимизация (математика)|оптимизации]].

== Описание ==
Проиллюстрируем суть метода равномерного поиска посредством рассмотрения задачи нахождения минимума.

Пусть задана [[Функция (математика)|функция]] <math>f(x):\;[a,\;b]\to\mathbb{R}</math>.
И [[задача оптимизации]] выглядит так: <math>f(x)\to\min_{x\in [a,\;b]}</math>.
Пусть также задано число наблюдений <math>n</math>.

Тогда [[отрезок]] <math>\left[a,b\right]</math> разбивают на <math>(n+1)</math> равных частей точками деления:
: <math>x_i=a+i\frac{\left(b-a\right)}{(n+1)},\quad i=1,\ldots,n</math>

Вычислив значения <math>F\left(x\right)</math> в точках <math>x_i,\;i=1,\ldots,n</math>, найдем путём сравнения точку <math>x_m</math>, где <math>m</math> — это число от <math>1</math> до <math>n</math> такую, что

: <math>F\left(x_m\right)=\min F\left(x_i\right)</math> для всех <math>i</math> от <math>1</math> до <math>n</math>.

Тогда [[интервал неопределённости]] составляет величину <math>2\frac{\left(b-a\right)}{(n+1)}</math>, а [[погрешность]] определения точки [[минимум]]а <math>x_m</math> функции <math>F\left(x\right)</math> соответственно составляет :<math>\varepsilon=\frac{\left(b-a\right)}{n+1}</math>.

== Модификация ==
Если заданное количество измерений чётно (<math>n=2k</math>), то разбиение можно проводить другим, более изощрённым способом:

: <math>x_{2i}=a+\frac{(b-a)}{(n/2+1)}2i, \quad i=1,\ldots,n/2</math>

: <math>x_{2i-1}=x_{2i}-\delta</math>, где <math>\delta</math> — некая константа из интервала <math>\left(0,\;\frac{(b-a)}{(n/2+1)}\right)</math>.

Тогда в худшем случае [[интервал неопределённости]] имеет длину <math>\frac{(b-a)}{(n/2+1)}+\delta</math>.

== Комбинаторика==

Метод перебора является одним из простейших методов комбинаторики. <ref>[http://urok.1sept.ru/%D1%81%D1%82%D0%B0%D1%82%D1%8C%D0%B8/416112/ Элементы комбинаторики. Методы решения некоторых задач]</ref>

== Литература ==
# {{книга
|автор = Акулич И.Л.
|заглавие = Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов
|оригинал =
|ссылка =
|издание =
|место = М.
|издательство = Высш. шк.
|год = 1986
|страницы =
|isbn =
}}
# {{книга
|автор = Гилл Ф., Мюррей У., Райт М.
|заглавие = Практическая оптимизация. Пер. с англ
|оригинал =
|ссылка =
|издание =
|место = М.
|издательство = Мир
|год = 1985
|страницы =
|isbn =
}}
# {{книга
|автор = Максимов Ю.А.,Филлиповская Е.А.
|заглавие = Алгоритмы решения задач нелинейного программирования
|оригинал =
|ссылка =
|издание =
|место = М.
|издательство = МИФИ
|год = 1982
|страницы =
|isbn =
}}
# {{книга
|автор = Корн Г., Корн Т.
|заглавие = Справочник по математике для научных работников и инженеров
|оригинал =
|ссылка =
|издание =
|место = М.
|издательство = Наука
|год = 1970
|страницы = 575-576
|isbn =
}}

== Примечания ==
{{reflist}}

{{Методы оптимизации}}

[[Категория:Алгоритмы оптимизации]]
[[Категория:Алгоритмы поиска]]