Меню Главная Случайная статья Настройки Метод перебора Материал из https://ru.wikipedia.org Метод перебора (метод равномерного поиска, перебор по сетке) — простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум, на минимум, на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной оптимизации. Содержание 1 Описание 2 Модификация 3 Комбинаторика 4 Литература 5 Примечания Описание Проиллюстрируем суть метода равномерного поиска посредством рассмотрения задачи нахождения минимума. Пусть задана функция ${\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. Примечания Элементы комбинаторики. Методы решения некоторых задач