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

Описание

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

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

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

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

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

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

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

Модификация

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

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

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

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

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

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

Литература

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

Примечания