Игра на поиск: различия между версиями

Материал из Поле цифровой дидактики
м (1 версия импортирована)
 
Строка 1: Строка 1:
'''Игра на поиск''' — это [[Антагонистическая игра|игра с нулевой суммой]] двух лиц, которая происходит на [[Множество|множестве]], называемым пространством поиска. Искатель может выбрать любую непрерывную траекторию, на которую накладывается ограничение на максимальную скорость. Всегда предполагается, что ни искатель, ни прячущийся не знают о передвижениях другого игрока, пока расстояние между ними не станет меньше (или равно) радиусу обнаружения и в этот самый момент осуществляется захват. В качестве [[Математическая модель|математических моделей]] игры на поиск могут быть применены в таких областях, как игры в [[прятки]], в которые играют дети, или в некоторых военных тактических обстоятельствах. Игры на поиск введены в последней главе классической книги [[Айзекс, Руфус (математик)|Руфуса Айзекса]] «Дифференциальные игры»{{sfn|Isaacs|1965}} и позднее их развил Шмуэль Гал{{sfn|Gal|1980}}{{sfn|Alpern, Gal|2003}} и Стив Альперн{{sfn|Alpern, Gal|2003}}. Игра «[[Принцесса и Чудовище (игра)|Принцесса и Чудовище]]» имеет дело с движущейся целью.
'''Игра на поиск''' — это [[Антагонистическая игра|игра с нулевой суммой]] двух лиц, которая происходит на [[Множество|множестве]], называемым пространством поиска. Искатель может выбрать любую непрерывную траекторию, на которую накладывается ограничение на максимальную скорость. Всегда предполагается, что ни искатель, ни прячущийся не знают о передвижениях другого игрока, пока расстояние между ними не станет меньше (или равно) радиусу обнаружения и в этот самый момент осуществляется захват. В качестве [[Математическая модель|математических моделей]] игры на поиск могут быть применены в таких областях, как игры в [[прятки]], в которые играют дети, или в некоторых военных тактических обстоятельствах. Игры на поиск введены в последней главе классической книги [[Айзекс, Руфус (математик)|Руфуса Айзекса]] «Дифференциальные игры»


== Стратегия ==
== Стратегия ==
Естественной стратегией поиска для неподвижной цели в графе является поиск минимальной замкнутой кривой L, которая проходит все дуги графа. (L называется [[Задача инспекции дорог|маршрутом китайского почтальона]]). Тогда обходим L с вероятностью 1/2 для каждого направления. Эта стратегия работает хорошо, если граф [[Эйлеров цикл|эйлеров]]. В общем случае маршрут китайского почтальона является оптимальной стратегией тогда и только тогда, когда граф состоит из набора эйлеровых графов, соединённых подобной дереву структурой{{sfn|Gal|2000}}. Обманчиво простой пример графа не из этого семейства состоит из двух узлов, соединённых тремя дугами. Случайный обход китайского почтальона (эквивалентно проходу трёх дуг в случайном порядке) не оптимален, а оптимальный путь поиска этих трёх дуг сложен{{sfn|Gal|1980}}.
Естественной стратегией поиска для неподвижной цели в графе является поиск минимальной замкнутой кривой L, которая проходит все дуги графа. (L называется [[Задача инспекции дорог|маршрутом китайского почтальона]]). Тогда обходим L с вероятностью 1/2 для каждого направления. Эта стратегия работает хорошо, если граф [[Эйлеров цикл|эйлеров]]. В общем случае маршрут китайского почтальона является оптимальной стратегией тогда и только тогда, когда граф состоит из набора эйлеровых графов, соединённых подобной дереву структурой. Обманчиво простой пример графа не из этого семейства состоит из двух узлов, соединённых тремя дугами. Случайный обход китайского почтальона (эквивалентно проходу трёх дуг в случайном порядке) не оптимален, а оптимальный путь поиска этих трёх дуг сложен.


== Неограниченные области ==
----
В общем случае неограниченной области для поиска, как в случае {{не переведено 5|Онлайн алгоритм|онлайнового алгоритма||online algorithm}}, приемлемой стратегией будет использование нормализованной [[Функция потерь|функции потерь]] (называемой в литературе {{не переведено 5|Конкурентный анализ (онлайн алгоритм)|конкурентным соотношением||Competitive analysis (online algorithm)}}).
 
[[Минимакс]]ная траектория для задач такого типа всегда является геометрической последовательностью (или экспоненциальной функцией для непрерывных задач). Этот результат даёт простой метод нахождения минимаксной траектории путём минимизации единственного параметра (генератора этой последовательности) вместо поиска по всему пространству траекторий. Это средство используется в {{не переведено 5|Задача линейного поиска|задаче линейного поиска||linear search problem}}, то есть задаче поиска цели на бесконечной прямой, которая привлекла много внимания в последнее время и анализировалась как игра на поиск{{sfn|Beck, Newman|1970|с=419—429}}. Оно использовалось также для поиска минимаксной траектории нахождения набора сходящихся в точке лучей. Оптимальный поиск на плоскости осуществляется с помощью экспоненциальных спиралей{{sfn|Gal|1980}}{{sfn|Alpern, Gal|2003}}{{sfn|Chrobak2004|с=74–78}}.
 
Поиск сходящихся лучей позднее был переоткрыт в научной литературе как «задача о коровьей тропе»{{sfn|Kao, Reif, Tate|1993}}.
 
==См. также==
* [[Теория гарантированного поиска]]
 
== Примечания ==
{{примечания}}
 
== Литература ==
* {{книга
|автор=Rufus Isaacs
|ref=Isaacs
|заглавие=Differential Games
|ссылка=https://archive.org/details/differentialgame0000isaa
|издание=John Wiley and Sons
|год=1965
}}
* {{статья
|автор=Gal S.
|ref=Gal
|заглавие=On the optimality of a simple strategy for searching graphs
|издание=Int. J. Game Theory
|год=2000
}}
* {{книга
|автор=Shmuel Gal
|ref=Gal
|выпуск=149
|серия=Mathematics in science and engeneering
|заглавие=Search Games
|ответственный=Richard Bellman
|издательство=Academic Press
|место=New York
|isbn=0-12-273850-0
|год=1980
}}
* {{книга
|автор=Alpern S., Gal S.
|ref=Alpern, Gal
|заглавие=The Theory of Search Games and Rendezvous
|издательство=Kluwer Academic Publishers
|место=New York, Boston, London, Moscow
|год=2003
|isbn=0-7923-7468-1
|isbn2=0-306-48212-6
|серия=International series in operations research & management science
}}
* {{статья
|автор=Beck A., Newman D.J.
|ref=Beck, Newman
|заглавие=Yet More on the linear search problem
|издание=Israel J. Math.
|том=8
|выпуск=4
|DOI=10.1007/BF02798690
|год=1970
|страницы=419—429
}}
* {{статья
|автор=Chrobak M.
|ref=Chrobak
|заглавие=A princess swimming in the fog looking for a monster cow
|издание=ACM Sigact news
|том=35
|выпуск=2
|год=2004
}}
* {{книга
|автор=Kao M.Y., Reif J.H., Tate S.R.
|ref=Kao, Reif, Tate
|часть=Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem
|заглавие=SODA
|год=1993
}}
{{Теория игр|status=collapsed}}
{{rq|checktranslate|style}}
[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы поиска]]
[[Категория:Некооперативные игры]]

Текущая версия на 16:37, 1 декабря 2022

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

Стратегия

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

Источник — http://digida.mgpu.ru/index.php?title=Игра_на_поиск&oldid=6217