Jump to content

Поиск игры

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

Стратегия

[ редактировать ]

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

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

[ редактировать ]

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

  1. ^ Руфус Айзекс, Дифференциальные игры , Джон Уайли и сыновья, (1965),
  2. ^ Jump up to: а б с С. Гал, Поисковые игры , Academic Press, Нью-Йорк (1980).
  3. ^ Jump up to: а б с С. Альперн и С. Гал, Теория поисковых игр и рандеву , Springer (2003).
  4. ^ Гал, Шмуэль (2001). «Об оптимальности простой стратегии поиска графов» . Международный журнал теории игр . 29 (4): 533–542. дои : 10.1007/s001820000056 .
  5. ^ Бек, Анатоль; Ньюман, диджей (1970). «Ещё о задаче линейного поиска» . Израильский математический журнал . 8 (4): 419–429. дои : 10.1007/BF02798690 .
  6. ^ М. Хробак, Принцесса, плавающая в тумане в поисках коровы-монстра, Новости ACM Sigact, 35 (2), 74–78 (2004).
  7. ^ М. Я. Као, Дж. Х. Рейф и С. Р. Тейт, Поиск в неизвестной среде: оптимальный рандомизированный алгоритм для задачи коровьей тропы , SODA 1993.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: abae45cbc285b9cd82b6b2b08164f8e6__1710955260
URL1:https://arc.ask3.ru/arc/aa/ab/e6/abae45cbc285b9cd82b6b2b08164f8e6.html
Заголовок, (Title) документа по адресу, URL1:
Search game - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)