Игра на поиск — это игра с нулевой суммой двух лиц, которая происходит на множестве, называемым пространством поиска. Искатель может выбрать любую непрерывную траекторию, на которую накладывается ограничение на максимальную скорость. Всегда предполагается, что ни искатель, ни прячущийся не знают о передвижениях другого игрока, пока расстояние между ними не станет меньше (или равно) радиусу обнаружения и в этот самый момент осуществляется захват. В качестве математических моделей игры на поиск могут быть применены в таких областях, как игры в прятки, в которые играют дети, или в некоторых военных тактических обстоятельствах. Игры на поиск введены в последней главе классической книги Руфуса Айзекса «Дифференциальные игры» и позднее их развил Шмуэль Гал и Стив Альперн. Игра «Принцесса и Чудовище» имеет дело с движущейся целью.
Стратегия Естественной стратегией поиска для неподвижной цели в графе является поиск минимальной замкнутой кривой L, которая проходит все дуги графа. (L называется маршрутом китайского почтальона). Тогда обходим L с вероятностью 1/2 для каждого направления. Эта стратегия работает хорошо, если граф эйлеров. В общем случае маршрут китайского почтальона является оптимальной стратегией тогда и только тогда, когда граф состоит из набора эйлеровых графов, соединённых подобной дереву структурой. Обманчиво простой пример графа не из этого семейства состоит из двух узлов, соединённых тремя дугами. Случайный обход китайского почтальона (эквивалентно проходу трёх дуг в случайном порядке) не оптимален, а оптимальный путь поиска этих трёх дуг сложен.
Неограниченные области В общем случае неограниченной области для поиска, как в случае , приемлемой стратегией будет использование нормализованной функции потерь (называемой в литературе ).
Минимаксная траектория для задач такого типа всегда является геометрической последовательностью (или экспоненциальной функцией для непрерывных задач). Этот результат даёт простой метод нахождения минимаксной траектории путём минимизации единственного параметра (генератора этой последовательности) вместо поиска по всему пространству траекторий. Это средство используется в , то есть задаче поиска цели на бесконечной прямой, которая привлекла много внимания в последнее время и анализировалась как игра на поиск. Оно использовалось также для поиска минимаксной траектории нахождения набора сходящихся в точке лучей. Оптимальный поиск на плоскости осуществляется с помощью экспоненциальных спиралей.
Поиск сходящихся лучей позднее был переоткрыт в научной литературе как «задача о коровьей тропе».
См. также Теория гарантированного поиска
Примечания
Литература
Категория:Алгоритмы поиска Категория:Некооперативные игры