Поисковая игра — это игра с нулевой суммой для двух человек , которая происходит в наборе , называемом пространством поиска. Ищущий может выбрать любую непрерывную траекторию, подлежащую ограничению максимальной скорости. Всегда предполагается, что ни ищущий, ни прячущийся не имеют никаких знаний о движении другого игрока, пока их расстояние не станет меньше или равно радиусу обнаружения, и в этот самый момент происходит захват. Игра является игрой с нулевой суммой, а выигрышем является время, потраченное на поиск. Как математические модели, поисковые игры могут применяться в таких областях, как игры в прятки, в которые играют дети, или представления некоторых тактических военных ситуаций. Область поисковых игр была представлена в последней главе классической книги Руфуса Айзекса «Дифференциальные игры» [1] и была далее развита Шмуэлем Галом [2] [3] и Стивом Альперном . [3] Игра принцесса и монстр имеет дело с движущейся целью.
Естественная стратегия поиска стационарной цели в графе (в котором дуги имеют длину) — найти минимальную замкнутую кривую L, которая покрывает все дуги графа. (L называется обходом китайского почтальона ). Затем, пройдите L с вероятностью 1/2 для каждого направления. Эта стратегия, кажется, хорошо работает, если граф является эйлеровым . В общем, этот случайный обход китайского почтальона действительно является оптимальной стратегией поиска тогда и только тогда, когда граф состоит из набора эйлеровых графов, соединенных в древовидную структуру. [4] Обманчиво простой пример графа, не входящего в это семейство, состоит из двух узлов, соединенных тремя дугами. Случайный обход китайского почтальона (эквивалент обхода трех дуг в случайном порядке) не является оптимальным, и оптимальный способ поиска этих трех дуг сложен. [2]
В общем, разумной основой для поиска в неограниченной области, как в случае онлайн-алгоритма , является использование нормализованной функции стоимости (называемой конкурентным отношением в литературе по информатике). Минимаксная траектория для задач такого типа всегда является геометрической последовательностью (или экспоненциальной функцией для непрерывных задач). Этот результат дает простой метод нахождения минимаксной траектории путем минимизации по одному параметру (генератору этой последовательности) вместо поиска по всему пространству траекторий. Этот инструмент использовался для задачи линейного поиска , т. е. поиска цели на бесконечной прямой, которая привлекала большое внимание в течение нескольких десятилетий и анализировалась как поисковая игра. [5] Он также использовался для поиска минимаксной траектории для поиска набора параллельных лучей. Оптимальный поиск на плоскости выполняется с использованием экспоненциальных спиралей. [2] [3] [6] Поиск набора параллельных лучей был позже повторно открыт в литературе по информатике как «задача о коровьем пути». [7]