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

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

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

Описание

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

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

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

x_i=a+i\frac{\left(b-a\right)}{(n+1)},\quad i=1,\ldots,n\,\!

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

F\left(x_m\right)=\min F\left(x_i\right) для всех i\,\! от 1\,\! до n\,\!.

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

Модификация

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

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

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

Литература

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



Wikimedia Foundation. 2010.

См. также в других словарях:

  • Метод перебора вариантов — Метод проб и ошибок (в просторечии также: метод тыка) форма научения, в 1898 г. описанна Э. Торндайком как основанная на закреплении случайно совершенных двигательных и мыслительных актов, за счет которых была решена значимая для животного задача …   Википедия

  • Метод научного тыка — Метод проб и ошибок (в просторечии также: метод тыка) форма научения, в 1898 г. описанна Э. Торндайком как основанная на закреплении случайно совершенных двигательных и мыслительных актов, за счет которых была решена значимая для животного задача …   Википедия

  • Метод тыка — Метод проб и ошибок (в просторечии также: метод тыка) форма научения, в 1898 г. описанна Э. Торндайком как основанная на закреплении случайно совершенных двигательных и мыслительных актов, за счет которых была решена значимая для животного задача …   Википедия

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

  • Метод проб и ошибок — Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Метод проб …   Википедия

  • Метод Нелдера — Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вв …   Википедия

  • Метод ветвей и границ — (англ. branch and bound) общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом… …   Википедия

  • Метод Грубой Силы — Полный перебор (или метод «грубой силы» от англ. brute force) метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений… …   Википедия

  • Метод грубой силы — Полный перебор (или метод «грубой силы» от англ. brute force) метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений… …   Википедия

  • Метод факторизации Ферма — Пьер Ферма Метод факторизации Ферма алгоритм факторизации нечётного целого числа , предложенный …   Википедия

Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»