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

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

Стратегия

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

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

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

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

  1. ^ Руфус Айзекс, Дифференциальные игры, Джон Уайли и сыновья, (1965),
  2. ^ а б c С. Гал, Поиск игр, Academic Press, Нью-Йорк (1980)
  3. ^ а б c С. Альперн и С. Гал, Теория поисковых игр и рандеву, Спрингер (2003).
  4. ^ С. Гал, Об оптимальности простой стратегии поиска графов, Int. Дж. Теория игр (2000).
  5. ^ А. Бек, Д. Дж. Новичок. Еще больше о задаче линейного поиска. Israel J. Math. (1970).
  6. ^ М. Хробак, Принцесса, плывущая в тумане в поисках коровы-монстра, Новости ACM Sigact, 35 (2), 74–78 (2004).
  7. ^ MY Kao, JH Reif и SR Tate, Поиск в неизвестной среде: оптимальный рандомизированный алгоритм для проблемы коровьего пути, SODA 1993.