Поиск игры
Поисковая игра — это игра двух человек с нулевой суммой , действие которой происходит в множестве, называемом пространством поиска. Искатель может выбрать любую непрерывную траекторию с ограничением максимальной скорости. Всегда предполагается, что ни искатель, ни скрывающийся не имеют никаких знаний о перемещении другого игрока до тех пор, пока их расстояние друг от друга не станет меньше или равно радиусу обнаружения и в этот самый момент не произойдет захват. Игра представляет собой нулевую сумму, а выигрышем является время, затраченное на поиск. В качестве математических моделей поисковые игры могут применяться к таким областям, как игры в прятки, в которые играют дети, или к изображению некоторых тактических военных ситуаций. Область поисковых игр была представлена в последней главе классической книги Руфуса Айзекса «Дифференциальные игры». [1] и был развит Шмуэлем Галем. [2] [3] и Стив Альперн . [3] В игре «Принцесса и монстр» используется движущаяся цель.
Стратегия
[ редактировать ]Естественная стратегия поиска стационарной цели в графе (в котором дуги имеют длину) — найти минимальную замкнутую кривую L, охватывающую все дуги графа. (L называется туром китайского почтальона ). Затем пройдите L с вероятностью 1/2 для каждого направления. Кажется, эта стратегия работает хорошо, если граф является эйлеровым . В общем, этот случайный обход китайского почтальона действительно является оптимальной стратегией поиска тогда и только тогда, когда граф состоит из набора эйлеровых графов, соединенных в древовидную структуру. [4] Обманчиво простой пример графа, не входящего в это семейство, состоит из двух узлов, соединенных тремя дугами. Случайный обход китайского почтальона (эквивалент прохождения трех дуг в случайном порядке) не является оптимальным, а оптимальный способ поиска этих трех дуг сложен. [2]
Неограниченные домены
[ редактировать ]В общем, разумной основой для поиска в неограниченной области, как и в случае с онлайн-алгоритмом , является использование нормализованной функции стоимости ( она называется коэффициентом конкуренции в литературе по информатике ). Минимаксная . траектория для задач такого типа всегда представляет собой геометрическую последовательность (или показательную функцию для непрерывных задач) Этот результат дает простой метод поиска минимаксной траектории путем минимизации по одному параметру (генератору этой последовательности) вместо поиска по всему пространству траекторий. Этот инструмент использовался для решения задачи линейного поиска , т. е. поиска цели на бесконечной линии, которая привлекала большое внимание на протяжении нескольких десятилетий и анализировалась как поисковая игра. [5] Он также использовался для поиска минимаксной траектории для поиска набора совпадающих лучей. Оптимальный поиск в плоскости осуществляется с использованием экспоненциальных спиралей. [2] [3] [6] Поиск набора параллельных лучей позже был вновь открыт в литературе по информатике как «проблема коровьей тропы». [7]
Ссылки
[ редактировать ]- ^ Руфус Айзекс, Дифференциальные игры , Джон Уайли и сыновья, (1965),
- ^ Jump up to: а б с С. Гал, Поисковые игры , Academic Press, Нью-Йорк (1980).
- ^ Jump up to: а б с С. Альперн и С. Гал, Теория поисковых игр и рандеву , Springer (2003).
- ^ Гал, Шмуэль (2001). «Об оптимальности простой стратегии поиска графов» . Международный журнал теории игр . 29 (4): 533–542. дои : 10.1007/s001820000056 .
- ^ Бек, Анатоль; Ньюман, диджей (1970). «Ещё о задаче линейного поиска» . Израильский математический журнал . 8 (4): 419–429. дои : 10.1007/BF02798690 .
- ^ М. Хробак, Принцесса, плавающая в тумане в поисках коровы-монстра, Новости ACM Sigact, 35 (2), 74–78 (2004).
- ^ М. Я. Као, Дж. Х. Рейф и С. Р. Тейт, Поиск в неизвестной среде: оптимальный рандомизированный алгоритм для задачи коровьей тропы , SODA 1993.