12.3. ИГРЫ ПОИСКА НЕПОДВИЖНЫХ ОБЪЕКТОВ

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

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

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

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

Теорема 12.3.1. Цена простой игры поиска равна Единственная оптимальная смешанная стратегия для состоит в том, чтобы расположить объект в с равномерным распределением вероятности. Оптимальная стратегия для состоит в том, чтобы пройти либо некоторый тур, либо обратный к нему (тот же тур, но с противоположным направлением движения), каждый с вероятностью

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

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

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

2. Пусть использует стратегию, указанную в теореме. Чистая стратегия эквивалентна выбору точки на распрямленном туре. Если представляет собой время ее отыскания при прохождении тура в одном направлении, то есть время, соответствующее обратному направлению. Плата тогда составляет

Утверждение теоремы следует из стандартных определений теории игр.

Замечание. Из доказательства мы видим, что свобода, предоставленная для выбора начальной точки, — это несколько чрезмерная щедрость.

Задача 12.3.1. Дать оптимальную стратегию для существенно отличную от приведенной в теореме, или от полученной смешиванием таких стратегий для различных туров.

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

Следствие 12.3.1. Цена простейшей игры поиска с искателями (и одним прячущимся) есть

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

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

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

Более точно, мы по существу доказали, что

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

Мы выведем аналог неравенства (12.3.1) для дискретной модели. Пусть район испещрен точками и соседние из них соединены отрезками, т. е. аппроксимируется линейным графом. Новый вариант нашей игры очевиден: тайно располагает объектов в некоторых различных точках: в свою очередь начинает поиск с любых точек и за каждый ход перемещает каждого из своих искателей в одну из соседних (связанных отрезком) точек. Объект считается найденным, если искатель занял его точку. Платой является число ходов, после которых все объекты оказываются найденными.

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

Результат, установленный для таких дискретных игр в приведенной ниже теореме 12.3.2, аналогичен неравенству (12.3.1).

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

Лемма 12.3.1.

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

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

где

Преобразуя ("суммируя по частям"), получаем

где

Далее, поскольку имеем

Чтобы оценить о, используем известное соотношение

Далее,

что очевидно, если правую часть рассматривать как сумму равных членов. Если просуммировать по и заметить, что «числители» справа пробегают множество целых чисел от до то получим

И, наконец,

Теорема 12.3.2. Цена V для дискретного варианта с точками простой игры поиска с объектами и искателями удовлетворяет неравенству

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

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

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