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

Материал из Поле цифровой дидактики
Версия от 13:17, 20 мая 2021; ru_wikipedia>Deltahead (откат правок 31.129.246.100 (обс.) к версии Ochkarik)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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


Описание

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

Пусть задана функция [math]\displaystyle{ f(x):\;[a,\;b]\to\mathbb{R} }[/math]. И задача оптимизации выглядит так: [math]\displaystyle{ f(x)\to\min_{x\in [a,\;b]} }[/math]. Пусть также задано число наблюдений [math]\displaystyle{ n }[/math].

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

[math]\displaystyle{ x_i=a+i\frac{\left(b-a\right)}{(n+1)},\quad i=1,\ldots,n }[/math]

Вычислив значения [math]\displaystyle{ F\left(x\right) }[/math] в точках [math]\displaystyle{ x_i,\;i=1,\ldots,n }[/math], найдем путём сравнения точку [math]\displaystyle{ x_m }[/math], где [math]\displaystyle{ m }[/math] — это число от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math] такую, что

[math]\displaystyle{ F\left(x_m\right)=\min F\left(x_i\right) }[/math] для всех [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math].

Тогда интервал неопределённости составляет величину [math]\displaystyle{ 2\frac{\left(b-a\right)}{(n+1)} }[/math], а погрешность определения точки минимума [math]\displaystyle{ x_m }[/math] функции [math]\displaystyle{ F\left(x\right) }[/math] соответственно составляет :[math]\displaystyle{ \varepsilon=\frac{\left(b-a\right)}{n+1} }[/math].

Модификация

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

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

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

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

Метод перебора является одним из простейших методов комбинаторики. <ref>Элементы комбинаторики. Методы решения некоторых задач</ref>

Литература

  1. {{#if:Акулич И.Л.|Акулич И.Л. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов]]|{{#if:|[ Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов]|Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:Высш. шк.|и}}{{#if:1986|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Высш. шк., 1986.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Высш. шк..
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 1986.
 |иг= — Высш. шк., 1986.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — Высш. шк..
 |г= — 1986.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  1. {{#if:Гилл Ф., Мюррей У., Райт М.|Гилл Ф., Мюррей У., Райт М. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Практическая оптимизация. Пер. с англ]]|{{#if:|[ Практическая оптимизация. Пер. с англ]|Практическая оптимизация. Пер. с англ}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Практическая оптимизация. Пер. с англ|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:Мир|и}}{{#if:1985|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Мир, 1985.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Мир.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 1985.
 |иг= — Мир, 1985.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — Мир.
 |г= — 1985.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  1. {{#if:Максимов Ю.А.,Филлиповская Е.А.|Максимов Ю.А.,Филлиповская Е.А. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы решения задач нелинейного программирования]]|{{#if:|[ Алгоритмы решения задач нелинейного программирования]|Алгоритмы решения задач нелинейного программирования}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы решения задач нелинейного программирования|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:МИФИ|и}}{{#if:1982|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: МИФИ, 1982.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: МИФИ.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 1982.
 |иг= — МИФИ, 1982.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — МИФИ.
 |г= — 1982.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:| — С. .}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

  1. {{#if:Корн Г., Корн Т.|Корн Г., Корн Т. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Справочник по математике для научных работников и инженеров]]|{{#if:|[ Справочник по математике для научных работников и инженеров]|Справочник по математике для научных работников и инженеров}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Справочник по математике для научных работников и инженеров|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:| — .}}{{#switch:{{#if:М.|м}}{{#if:Наука|и}}{{#if:1970|г}}
 |миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Наука, 1970.
 |ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Наука.
 |мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 1970.
 |иг= — Наука, 1970.
 |м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
 |и= — Наука.
 |г= — 1970.

}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:575-576| — С. 575-576.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| —  p.}}{{#if:| —  s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:| — ISBN }}

Примечания

Шаблон:Reflist

Шаблон:Методы оптимизации

Источник — http://digida.mgpu.ru/index.php?title=Метод_перебора&oldid=4642