Игра на поиск

Материал из Поле цифровой дидактики
Версия от 20:55, 19 октября 2022; Patarakin (обсуждение | вклад) (1 версия импортирована)

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

Стратегия

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

Неограниченные области

В общем случае неограниченной области для поиска, как в случае Шаблон:Не переведено 5, приемлемой стратегией будет использование нормализованной функции потерь (называемой в литературе Шаблон:Не переведено 5).

Минимаксная траектория для задач такого типа всегда является геометрической последовательностью (или экспоненциальной функцией для непрерывных задач). Этот результат даёт простой метод нахождения минимаксной траектории путём минимизации единственного параметра (генератора этой последовательности) вместо поиска по всему пространству траекторий. Это средство используется в Шаблон:Не переведено 5, то есть задаче поиска цели на бесконечной прямой, которая привлекла много внимания в последнее время и анализировалась как игра на поискШаблон:Sfn. Оно использовалось также для поиска минимаксной траектории нахождения набора сходящихся в точке лучей. Оптимальный поиск на плоскости осуществляется с помощью экспоненциальных спиралейШаблон:SfnШаблон:SfnШаблон:Sfn.

Поиск сходящихся лучей позднее был переоткрыт в научной литературе как «задача о коровьей тропе»Шаблон:Sfn.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Теория игр Шаблон:Rq