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

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

Описание

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

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

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

[math]\displaystyle{ x_i=a+i\frac{\left(b-a\right)}{(n+1)},\quad i=1,\ldots,n }[/math]

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

[math]\displaystyle{ F\left(x_m\right)=\min F\left(x_i\right) }[/math] для всех [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math].

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

Модификация

Если заданное количество измерений чётно ([math]\displaystyle{ n=2k }[/math]), то разбиение можно проводить другим, более изощрённым способом:

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

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

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