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

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

Описание

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

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

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

$x_i=a+i\frac{(b-a)}{(n+1)},i=1,\dots ,n$

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

$F\left(x_m\right)=\min F\left(x_i\right)$ для всех $i$ от $1$ до $n$.

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

Модификация

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

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

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

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

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

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

Литература

1. Шаблон:Книга
2. Шаблон:Книга
3. Шаблон:Книга
4. Шаблон:Книга