Поиск игры - Search game

Игра поиск состоит из двух людей игра с нулевой суммой , которая имеет место в наборе называется пространством поиска. Поисковик может выбрать любую непрерывную траекторию с учетом ограничения максимальной скорости. Всегда предполагается, что ни ищущий, ни прячущийся ничего не знают о движении другого игрока до тех пор, пока их расстояние друг от друга не станет меньше или равно радиусу обнаружения, и в этот самый момент происходит захват. В качестве математических моделей поисковые игры могут применяться к таким областям, как игры в прятки, в которые играют дети, или к изображениям некоторых тактических военных ситуаций. Сфера поисковых игр была представлена ​​в последней главе классической книги Руфуса Айзекса «Дифференциальные игры» и была развита Шмуэлем Галом и Стивом Альперном . Игра принцесса и монстр имеет дело с движущейся целью.

Стратегия

Естественная стратегия поиска стационарной цели в графе - найти минимальную замкнутую кривую L, которая покрывает все дуги графа. (L называется тур по китайскому почтальону ). Затем пройдите L с вероятностью 1/2 для каждого направления. Эта стратегия, кажется, работает хорошо, если граф эйлеров . В общем, этот случайный тур по китайскому почтальону действительно является оптимальной стратегией поиска тогда и только тогда, когда граф состоит из набора эйлеровых графов, связанных древовидной структурой. Обманчиво простой пример графа не из этого семейства состоит из двух узлов, соединенных тремя дугами. Случайный тур по китайскому почтальону (эквивалентный обходу трех дуг в случайном порядке) не является оптимальным, и оптимальный способ поиска по этим трем дугам сложен.

Неограниченные домены

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

Рекомендации