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

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

Описание

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

Пусть задана функция ${\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]

Литература

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

Примечания

1. Элементы комбинаторики. Методы решения некоторых задач