Пошукова гра — це гра з нульовою сумою для двох осіб, яка відбувається на множині, званій простором пошуку. Шукач може вибрати будь-яку неперервну траєкторію, на яку накладається обмеження на максимальну швидкість. Завжди передбачається, що ні шукач, ні той, що ховається, не знають про пересування іншого гравця, поки відстань між ними не стане меншою (або рівною) радіусу виявлення і в цей самий момент здійснюється захоплення. Як математичні моделі пошукові ігри можна застосувати в таких галузях, як ігри в хованки, в які грають діти, або за деяких військових тактичних обставин. Ігри на пошук уведені в останньому розділі класичної книги «Диференціальні ігри» і пізніше їх розвинув Шмуель Гал і Стів Альперн. Гра «Принцеса і Чудовисько» має справу з рухомою ціллю.
Стратегія Природною стратегією пошуку для нерухомої цілі в графі є пошук мінімальної замкнутої кривої L, яка проходить всі дуги графу. (L називається маршрутом китайського листоноші). Тоді обходимо L з імовірністю 1/2 для кожного напрямку. Ця стратегія працює добре, якщо граф ейлерів. У загальному випадку маршрут китайського листоноші є оптимальною стратегією тоді й лише тоді, коли граф складається з набору ейлерових графів, з'єднаних деревоподібною структурою. Оманливо простий приклад графу не з цього сімейства складається з двох вузлів, з'єднаних трьома дугами. Випадковий обхід китайського листоноші (еквівалентний проходу трьох дуг у випадковому порядку) не оптимальний, а оптимальний шлях пошуку цих трьох дуг складний.
Необмежені області У загальному випадку необмеженої області для пошуку, як у разі онлайнового алгоритму, прийнятною стратегією буде використання нормалізованої функції втрат (званої в літературі конкурентним співвідношенням).
Мінімаксна траєкторія для задач такого типу завжди є геометричною послідовністю (або експоненційною функцією для неперервних задач). Цей результат дає простий метод знаходження мінімаксної траєкторії шляхом мінімізації єдиного параметра (генератора цієї послідовності) замість пошуку по всьому простору траєкторій. Цей засіб використовується в задачі лінійного пошуку, тобто задачі пошуку цілі на нескінченній прямій, яка привернула багато уваги останнім часом і аналізувалася як пошукова гра. Він використовувався також для пошуку мінімаксної траєкторії знаходження набору променів, що сходяться в точці. Оптимальний пошук на площині здійснюється за допомогою експоненційних спіралей.
Пошук променів, що сходяться, пізніше перевідкрито в науковій літературі як «задача про коров'ячу стежку».
Примітки
Література