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

Перейти к навигацииПерейти к поиску

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


Описание

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

Пусть задана функция . И задача оптимизации выглядит так: . Пусть также задано число наблюдений .

Тогда отрезок разбивают на равных частей точками деления:

Вычислив значения в точках , найдем путём сравнения точку , где  — это число от до такую, что

для всех от до .

Тогда интервал неопределённости составляет величину , а погрешность определения точки минимума функции соответственно составляет :.

Модификация

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

, где  — некая константа из интервала .

Тогда в худшем случае интервал неопределённости имеет длину .

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

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

Литература

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

Примечания