Метод перебора

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

Описание

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

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

Тогда отрезок $\left[a,b\right]$ разбивают на $(n+1)$ равных частей точками деления:

$x_{i}=a+i{\frac {\left(b-a\right)}{(n+1)}},\quad i=1,\ldots ,n$

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

$F\left(x_{m}\right)=\min F\left(x_{i}\right)$ для всех $i$ от $1$ до $n$.

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

Модификация

Если заданное количество измерений чётно ($n=2k$), то разбиение можно проводить другим, более изощрённым способом:

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

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

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

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

Метод перебора является одним из простейших методов комбинаторики.

Литература

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