§ 14.14. Задачи поиска

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

Предположим, что в одной из клеток спрятан некий объект, и пусть априорная вероятность того, что он спрятан в клетке Здесь Допустим, что статистику надо найти этот объект, а в единицу времени он может осмотреть только одну клетку. Следовательно, ему нужно выработать последовательную процедуру поиска, определяющую на каждом шаге ту клетку, в которой проводится поиск.

Предположим, что, даже если на некотором шаге поиск проводится в клетке, содержащей искомый объект, существует положительная вероятность того, что объект не будет найден. Более точно, условимся считать, что еслй объект находится в клетке то с вероятностью он не будет обнаружен при поиске в этой клетке. Конечно, если объект не

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

Процесс поиска можно описать следующим образом. Предположим, что на некотором шаге вероятность того, что объект находится в клетке равна Предположим также, осмотрена одна из клеток, скажем с номером и объект не обнаружен. Тогда при апостериорная вероятность того, что объект находится в клетке равна

Будем считать, что статистик должен продолжать поиск до обнаружения объекта и стоимость осмотра клетки равна Надо определить процедуру, минимизируюшую среднюю общую стоимость процедуры поиска.

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

Пусть на первом шаге поиск проводится в клетке Тогда с вероятностью объект обнаруживается при первом осмотре и процесс поиска заканчивается. С другой сторовы, с вероятностью при первом шаге поиска статистик не находит объект. В этом случае апостериорные вероятности имеют вид (1) и средняя стоимость последующей части процесса поиска при оптимальной процедуре равна Учитывая стоимость первого шага поиска, видим, что средняя общая стоимость процесса при поиске на первом шаге в клетке и последующем оптимальном продолжении равна Так как на первом

шаге осматривается одна из имеющихся клеток, то для справедливо следующее соотношение:

Можно показать, что для любых вероятностей . В самом деле, если средняя общая стоимость оптимальной процедуры, то ее значения не могут превосходить среднюю стоимость процедуры, при которой клетки от 1-й до обследуются в циклическом порядке до обнаружения объекта. Найдем оценку для средней стоимости циклической процедуры.

Предположим сначала, что объект находится в клетке Тогда среднее число поисков в клетке необходимое для обнаружения объекта, равно . Так как стоимость каждого цикла поисков во всех клетках равна то средняя стоимость обнаружения объекта не превосходит Если мы вычислим математическое ожидание при всех возможных расположениях объекта, то получим, что средняя общая стоимость не может превосходить

Таким образом, эта величина является границей сверху для значения

Как мы уже сказали выше, решение уравнения (2) представляется весьма сложным делом. Поэтому мы применим другой подход. Для произвольной последовательной процедуры и для обозначим через вероятность того, что для этой процедуры объект будет найден и тем самым поиск прекратится после осмотра клетки. Тогда независимо от числа осмотра других клеток до осмотра клетки вероятность равна

Каждая процедура поиска предписывает на каждом шаге если объект еще не найден, осмотреть одну из клеток Для любой заданной процедуры S обозначим через стоимость поиска на шаге и через вероятность обнаружить объект на шаге Так, например, если процедура 6 требует осмотра клетки в 7-й раз на шаге, то Как всегда, будет обозначать общее число шагов, необходимых для обнаружения объекта. Тогда средняя

общая стоимость поисков объекта дается формулой

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

Покажем теперь, что согласно оптимальной процедуре поиск должен проходить так, чтобы выполнялось следующее соотношение:

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

Предположим теперь, что процедура с для которой при некотором

Пусть, согласно процедуре надо осмотреть клетку на шаге и клетку к на шаге. Из (7) видно, что Введем процедуру которая требует осмотра клетки к на шаге, клетки на шаге, а в остальном совпадает с процедурой Если и — это определенные выше стоимость и вероятность на шаге для процедуры то

Из (5), (7) и (8) вытекает следующий результат:

Поэтому для процедуры средний общий риск меньше, чем для процедуры

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

Использованный нами метод построения оптимальной процедуры несколько отличается от применявшихся ранее в этой главе. Мы почти отказались от «динамической» точки зрения поскольку не было никаких заключительных апостериорных распределений и все шаги процесса было удобнее рассматривать скорее одновременно, нежели последовательно, Однако из, (1) и (4) видно, что полученная нами оптимальная процедура имеет следующую простую и полезную динамическую интерпретацию. Пусть на данном шаге процесса текущие апостериорные вероятности того, что объект находится в клетке с соответствующим номером. Тогда следующий осмотр должен быть проведен в клетке, для которой значение максимально. Так как это вероятность обнаружения объекта при одном осмотре клетки то, согласно оптимальной процедуре, на каждом шаге надо осматривать клетку с максимальным отношением вероятности обнаружения к стоимости обнаружения объекта.

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