Методы перебора и слепого (случайного) поиска

11.10.2.1. Метод перебора
Методы спуска плохо работают на неупорядоченном рельефе. Если локальных экстремумов много, то спуск из одного начального приближения может сойтись только к одному локальному минимуму, не обязательно абсолютному. В связи с неимоверно вырсошими вычислительными возможностями современных ЭВМ во многих случаях может помочь примтивный метод перебора, в соответствии с которым вся исследуемая область разбивается на элементарные области, в которых и вычисляется значение исследуемой функции. Для того чтобы наглядно представить себе сущность метода примтивного перебора, рассмотрим следующую задачу. Допустим, в большом современном городе у молодого горячего джигита потерялась девушка, в которую он влюблен и собирается на ней жениться. Ему нужно найти ее, причем за ценой он не постоит. Самый примитивный метод поиска состоит в поквартирном обходе всех домов в городе. Если предположить, что в каждой квартире ему скажут правду, то задача будет состоять только в том, чтобы быстро бегать по городу... Девушка давно с нетерпением смотрит на свой сотовый, ожидая звонка от любимого, который бегает по всему городу в ее поисках... Невольно вспоминается бородатый анекдот про чукчу, которго заперли одного в комнате с телефоном для связи. После того как терпение экспериментаторов иссякло, они сами открыли дверь в комнату и увидели чукчу, стоящего на коленях у телефона: "Телефона, телефона, чукча кушать хочет..."
Несмотря на всю очевидную примтивность метода перебора, он довольно часто применяется молодыми горячими студентами, страстно желающими получить зачет или сдать экзамен. Таким можно сказать только одно: проверено, мин нет... Помните анекдот, в котором эксперименты ставили над обезьянами: подвесят банан посреди комнаты, а в угол бросят палку. Задача обезьян взять палку и сбить банан. И вот как-то в выходной вместо банана подвесили в ту комнату пол-литру.. И завели туда двух местных... Реакция их была именно такой, которая хорошо согласуется с алгоритмом перебора: "Чего думать, прыгать надо!" 11.10.2.2. Метод случайного поиска
В методе случайного поиска молодой джигит, не долго думая, просто бросает монетку и в зависмости от того, что выпадет, выбирает себе маршрут поиска.
Даже при миллионе пробных точек вероятность того, что хотя бы одна точка попадет в небольшую окрестность локального минимума, ничтожно мала. В самом деле, пусть диаметр котловины составляет 10% от пределов изменения каждой координаты. Тогда объем этой котловины составляет 0,1ⁿ часть объема n-мерного куба. Уже при n>6 ни одна точка в котловину не попадет.
В соответствии с методом слепого (случайного) поиска предполагают, что все локальные минимумы лежат в некоторой ограниченной области; линейным преобразованием координат помещают ее внутрь единичного n-мерного куба. Выбирают в этом кубе N=(5÷20)n случайных точек с использованием генератора случайных чисел, и из каждой их них осуществляют спуск, быстро попадая в ближайший овраг или котловину; когда шаги спуска укорачиваются, его прекращают, не добиваясь высокой точности. Этого уже достаточно, чтобы судить о величине функции в ближайшем локальном минимуме с удовлетворительной точностью.
Затем среди всех выявленных локальных минимумов выбираются те, которые представляют интерес, и в них производится окончательный счет с требуемой точностью.
Метод случайного поиска зачастую позволяет находить все локальные минимумы функции от 10−20 переменных со сложным рельефом. Он полезен и при исследовании функций с единственным минимумом; в этом случае можно обойтись заметно меньшим числом случайных точек. Недостаток метода в том, что надо заранее задать область, в которой выбираются случайные точки. Если задать слишком широкую область, то ее трудно детально исследовать; если же область слишком узкая, то многие локальные минимумы могут оказаться вне ее. Правда, положение несколько облегчается тем, что при спусках траектории могут выйти за пределы заданной области и сойтись к лежащим вне этой области минимумам.