4.3.6. Вероятностные характеристики поиска

Эффективность описанного алгоритма поиска существенно зависит от вида заданной логической функции а также от параметров алгоритма поиска. Действительно, с увеличением количество индексных зон быстро возрастает и роятность нахождения оптимальной (для заданной функции) зоны уменьшается. Если в подобной ситуации осуществлять поиск с большим шагом при малом значении то функция ведет себя как многоэкстремальная, хотя в действитель ности она может и не обладать этим свойством. С другой сто роны, при малом шаге и большом поиск становится неэффективным по затратам времени, хотя принципиально позво ляет решить задачу.

Таким образом, параметры алгоритма должны быть в определенном смысле согласованы с характером функции . В этом отношении можно дать лишь качественные рекомендации.

Для случая функций трех переменных получены количественные оценки эффективности поиска, которые приводятся ниже.

Пусть в пространстве задана сфера с центром в начале координат. На участке сферы, лежащем в первом октанте, возьмем случайную точку в соответствии с равномерной плотностью распределения по поверхности этого участка. Оценим вероятности попадания этой точки в индексные зоны (см. подраздел 4.3.4 настоящей книги и работу [26]).

Найдем плотности распределения углов являющихся сферическими координатами точки Пусть плотность распределения угла равномерная:

Тогда плотность распределения угла согласно

Поскольку — независимые случайные величины, то

Следовательно, вероятность попадания точки в индексную зону равна

где определяются границами этой зоны. Вычислим, например, вероятность попадания в первую индексную зону (см. рис. 4.3.4). Пределы интегрирования:

Получаем

Аналогично можно найти остальные вероятности:

Для рассмотренной выше функции вероятность случайного попадания в оптимальную область равна

т. е. потери на поиск достаточно малы (в среднем каждый третий случайный шаг поиска оказывается удачным).