Войти
A поиск игры - это игра для двух человек с нулевой суммой, которая происходит в наборе, называемом пространством поиска. Поисковик может выбрать любую непрерывную траекторию с учетом ограничения максимальной скорости. Всегда предполагается, что ни ищущий, ни прячущийся ничего не знают о движении другого игрока до тех пор, пока их расстояние друг от друга не станет меньше или равно радиусу обнаружения, и в этот самый момент происходит захват. В качестве математических моделей поисковые игры могут применяться к таким областям, как игры в прятки, в которые играют дети, или к изображениям некоторых тактических военных ситуаций. Сфера поисковых игр была представлена в последней главе классической книги Руфуса Айзекса «Дифференциальные игры» и была развита Шмуэлем Галом и Стивом Алперном. Игра принцесс и монстров имеет дело с движущейся целью.
Естественная стратегия поиска стационарной цели в графе - это найти минимальную замкнутую кривую L, которая покрывает все дуги графа. (L называется китайский почтальон тур). Затем пройдите L с вероятностью 1/2 для каждого направления. Эта стратегия, кажется, работает хорошо, если граф эйлеров. В общем, этот случайный тур по китайскому почтальону действительно является оптимальной стратегией поиска тогда и только тогда, когда граф состоит из набора эйлеровых графов, соединенных древовидной структурой. Обманчиво простой пример графа не из этого семейства состоит из двух узлов, соединенных тремя дугами. Случайный тур по китайскому почтальону (эквивалент обхода трех дуг в случайном порядке) не является оптимальным, и оптимальный способ поиска по этим трем дугам сложен.
В общем, разумная основа для поиска неограниченного домена, как в случае онлайн-алгоритма, состоит в использовании нормализованной функции стоимости (называемой конкурентным соотношением в Computer Научная литература). Минимаксная траектория для задач этих типов всегда является геометрической последовательностью (или экспоненциальной функцией для непрерывных задач). Этот результат дает простой метод поиска минимаксной траектории путем минимизации по одному параметру (генератору этой последовательности) вместо поиска по всему пространству траекторий. Этот инструмент использовался для решения задачи линейного поиска, то есть поиска цели на бесконечной линии, которая привлекала большое внимание на протяжении нескольких десятилетий и была проанализирована как поисковая игра. Он также использовался, чтобы найти минимаксную траекторию для поиска набора параллельных лучей. Оптимальный поиск в плоскости осуществляется с помощью экспоненциальных спиралей. Поиск набора параллельных лучей был позже повторно открыт в литературе по компьютерным наукам как «проблема коровьего пути».
