§ 5.7. УПРАВЛЕНИЕ ДЛИТЕЛЬНОСТЬЮ ПРОБНЫХ ШАГОВ ПО ГРУППИРОВАННЫМ ДАННЫМ

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

Число независимых данных в интервале группировки, очевидно равно отношению где интервал временной дискретизации.

Применение способа группировки приводит к дискретному изменению длительности пробного шага на величину, кратную интервалу группировки.

Средняя длительность пробных шагов при способе группированной процедуры как можно показать, в худшем случае не может превосходить среднюю длительность пробного шага достигаемую при последовательном анализе данных, более чем на величину двойного интервала группировки (см. [1] стр. 140).

С большой вероятностью может быть использована оценка

Используя получаем условие для выбора йнтерйалй группировки

При выполнении условия (5.30) можно пренебрегать «потерями», связанными с использованием группированной процедуры.

Процедура поиска при управлении длительности пробных шагов по группированным данным может быть представлена в виде эквивалентного многоэтапного процесса:

а) на первом этапе все элементы зондируются с длительностью пробного шага, равной интервалу группировки, и с помощью двухпорогового сравнения отбираются элементы для повторного зондирования;

б) на втором этапе процесс зондирования с длительностью повторяется на элементах, на которых не было получено решение в первом этапе и т. д.

Используя интервалы группировки, равные интервалам временной дискретизации, мы получаем многоэтапный процесс поиска в пределе, эквивалентный процессу с непрерывным управлением длительностью пробного шага.

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