§ 14.15. Задачи поиска с равными стоимостями

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

вероятность того, что объект находится в клетке то мы предположим только, что Если объекта нет ни в одной из клеток, то Однако по-прежнему, если объект не был обнаружен при одном поиске в клетке то апостериорные вероятности имеют вид (1) § 44.14.

Далее, вероятность обнаружить объект во цремя осмотра клетки по-прежнему задается формулой (4) § 14.14.

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

Поскольку процесс поиска проводится со скоростью один шаг в единицу времени, то мы можем вернуться к динамической интерпретации" оптимальной процедуры, описанной в конце § 14.14. Здесь процедура имеет особенно простой вид, и из приводимых далее рассуждений видно, что она оптимальна в весьма сильном смысле.

На любом данном шаге процесса пусть — текущие вероятности того, что объект находится в соответствующей клетке. Тогда очередной поиск проводится в клетке, для которой значение максимально. Так как последнее число совпадает с вероятностью обнаружить объект при этом очередном поиске, если проводить его в клетке то оптимальная процедура близорукая: на каждом шаге поиск надо проводить в той клеткег для которой вероятность найти объект на этом шаге максимальна. Эта же процедура одновременно максимизирует для всех натуральных вероятность того, что объект будет обнаружен не больше, чем за шагов. Если объект действительно находится в одной из клеток и статистик продолжает поиск до обнаружения объекта, то, как было установлено в § 14.14, эта процедура минимизирует среднее число поисков Кроме того, эта процедура минимизирует и для любой неубывающей функции

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

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

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

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

Задача определения оптимального числа поисков, после проведения которых процесс надо закончить, несколько более трудна. Мы не будем ее здесь обсуждать. Эта задача была исследована Чжу (1967).

Дальнейшие замечания и ссылки на литературы. Задачи поиска типа рассмотренных в этом и предыдущем параграфах изучались Староверовым (1963); Матулой (1964), который излагает также результаты Блекуэлла в этой области; Блэком (1965); Чжу (1967) и Кадейном (1968), статья которого и положена в основу нашего изложения. Близкие задачи исследовал Беллман (1957а). Известны и другие типы задач поиска. Обширную библиографию по этому вопросу составил Энслоу (1966).