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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание[править | править исходный текст]

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

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