Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика

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

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


Описание

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

Пусть задана функция f ( x ) : [ a , b ] → R {displaystyle f(x):;[a,;b] o mathbb {R} } . И задача оптимизации выглядит так: f ( x ) → min x ∈ [ a , b ] {displaystyle f(x) o min _{xin [a,;b]}} . Пусть также задано число наблюдений n {displaystyle n} .

Тогда отрезок [ a , b ] {displaystyle left[a,b ight]} разбивают на ( n + 1 ) {displaystyle (n+1)} равных частей точками деления:

x i = a + i ( b − a ) ( n + 1 ) , i = 1 , … , n {displaystyle x_{i}=a+i{frac {left(b-a ight)}{(n+1)}},quad i=1,ldots ,n}

Вычислив значения F ( x ) {displaystyle Fleft(x ight)} в точках x i , i = 1 , … , n {displaystyle x_{i},;i=1,ldots ,n} , найдем путём сравнения точку x m {displaystyle x_{m}} , где m {displaystyle m} — это число от 1 {displaystyle 1} до n {displaystyle n} такую, что

F ( x m ) = min F ( x i ) {displaystyle Fleft(x_{m} ight)=min Fleft(x_{i} ight)} для всех i {displaystyle i} от 1 {displaystyle 1} до n {displaystyle n} .

Тогда интервал неопределённости составляет величину 2 ( b − a ) ( n + 1 ) {displaystyle 2{frac {left(b-a ight)}{(n+1)}}} , а погрешность определения точки минимума x m {displaystyle x_{m}} функции F ( x ) {displaystyle Fleft(x ight)} соответственно составляет : ε = ( b − a ) n + 1 {displaystyle varepsilon ={frac {left(b-a ight)}{n+1}}} .

Модификация

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

x 2 i = a + ( b − a ) ( n / 2 + 1 ) 2 i , i = 1 , … , n / 2 {displaystyle x_{2i}=a+{frac {(b-a)}{(n/2+1)}}2i,quad i=1,ldots ,n/2} x 2 i − 1 = x 2 i − δ {displaystyle x_{2i-1}=x_{2i}-delta } , где δ {displaystyle delta } — некая константа из интервала ( 0 , ( b − a ) ( n / 2 + 1 ) ) {displaystyle left(0,;{frac {(b-a)}{(n/2+1)}} ight)} .

Тогда в худшем случае интервал неопределённости имеет длину ( b − a ) ( n / 2 + 1 ) + δ {displaystyle {frac {(b-a)}{(n/2+1)}}+delta } .

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

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