Метод перебора (метод равномерного поиска, перебор по сетке) — простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум, на минимум, на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной оптимизации.
Описание Проиллюстрируем суть метода равномерного поиска посредством рассмотрения задачи нахождения минимума.
Пусть задана функция . И задача оптимизации выглядит так: . Пусть также задано число наблюдений .
Тогда отрезок разбивают на равных частей точками деления:
Вычислив значения в точках , найдем путём сравнения точку , где — это число от до такую, что
для всех от до .
Тогда интервал неопределённости составляет величину , а погрешность определения точки минимума функции соответственно составляет :.
Модификация Если заданное количество измерений чётно (), то разбиение можно проводить другим, более изощрённым способом:
, где — некая константа из интервала .
Тогда в худшем случае интервал неопределённости имеет длину .
Комбинаторика
Метод перебора является одним из простейших методов комбинаторики. Элементы комбинаторики. Методы решения некоторых задач
Литература
Примечания
Категория:Алгоритмы оптимизации Категория:Алгоритмы поиска