Hledání hry

Pátrací hra  je hra pro dvě osoby s nulovým součtem , která se odehrává na sadě zvané vyhledávací prostor. Hledač si může vybrat libovolnou souvislou trajektorii s omezením maximální rychlosti. Vždy se předpokládá, že ani hledač, ani schovávač si neuvědomují pohyby druhého hráče, dokud vzdálenost mezi nimi není menší než (nebo rovna) detekčnímu poloměru a v tom okamžiku je zajetí provedeno. Jako matematické modely lze pátrací hry použít v oblastech, jako jsou hry na schovávanou , které hrají děti, nebo za určitých vojenských taktických okolností. Vyhledávací hry byly představeny v poslední kapitole klasických diferenciálních her Rufuse Isaacse [1] a později vyvinuty Shmuelem Galem [2] [3] a Stevem Alpernem [3] . Hra " Princezna a zvíře " se zabývá pohyblivým cílem.

Strategie

Přirozenou strategií hledání pevného cíle v grafu je najít minimální uzavřenou křivku L, která prochází všemi oblouky grafu. (L se nazývá Čínská pošťácká cesta ). Potom obejdeme L s pravděpodobností 1/2 pro každý směr. Tato strategie funguje dobře, pokud je Eulerův graf . Obecně platí, že cesta čínského pošťáka je optimální strategií tehdy a jen tehdy, pokud graf sestává ze sady Eulerových grafů spojených stromovou strukturou [4] . Zdánlivě jednoduchý příklad grafu, který není z této rodiny, sestává ze dvou uzlů spojených třemi oblouky. Náhodné procházení čínského pošťáka (ekvivalent projetí tří oblouků v náhodném pořadí) není optimální a optimální cesta k nalezení těchto tří oblouků je komplikovaná [2] .

Neomezené oblasti

V obecném případě neomezené oblasti vyhledávání, jako v případě online algoritmu , by přijatelnou strategií bylo použití normalizované ztrátové funkce (v literatuře nazývané konkurenční poměr ).

Trajektorie minimaxu pro problémy tohoto typu je vždy geometrická posloupnost (nebo exponenciální funkce pro spojité problémy). Tento výsledek poskytuje jednoduchou metodu pro nalezení minimaxové trajektorie minimalizací jediného parametru (generátoru této sekvence) namísto prohledávání celého prostoru trajektorií. Tento nástroj se používá v problému lineárního hledání , tedy problému hledání cíle na nekonečné čáře, kterému se v poslední době dostalo velké pozornosti a byl analyzován jako hra na hledání [5] . Byl také použit k nalezení minimaxové trajektorie pro nalezení sady paprsků sbíhajících se v bodě. Optimální hledání v rovině se provádí pomocí exponenciálních spirál [2] [3] [6] .

Hledání konvergujících paprsků bylo později ve vědecké literatuře znovu objeveno jako „problém kravské cesty“ [7] .

Viz také

• Zaručená teorie vyhledávání

Poznámky

1. ↑ Isaacs, 1965 .
2. ↑ 1 2 3 Gal, 1980 .
3. ↑ 1 2 3 Alpern, Gal, 2003 .
4. ↑ Gal, 2000 .
5. ↑ Beck, Newman, 1970 , str. 419-429.
6. ↑ Chrobak2004 , str. 74–78.
7. ↑ Kao, Reif, Tate, 1993 .

Literatura

• Rufus Isaacs. Rozdílové hry . — John Wiley and Sons. — 1965.
• Gal S. O optimálnosti jednoduché strategie prohledávání grafů // Int. J. Teorie her. — 2000.
• Shmuel Gal. Vyhledávání her / Richard Bellman. - New York: Academic Press, 1980. - (Matematika ve vědě a inženýrství). — ISBN 0-12-273850-0 .
• Alpern S., Gal S. Teorie vyhledávacích her a setkání. - New York, Boston, Londýn, Moskva: Kluwer Academic Publishers, 2003. - (Mezinárodní řada v operačním výzkumu a managementu). - ISBN 0-7923-7468-1 . — ISBN 0-306-48212-6 .
• Beck A., Newman DJ Yet More on the linear search problem // Israel J. Math .. - 1970. - V. 8 , no. 4 . - S. 419-429 . - doi : 10.1007/BF02798690 .
• Chrobak M. Princezna plavající se v mlze a hledá monstrózní krávu // ACM Sigact news. - 2004. - T. 35 , no. 2 .
• Kao MY, Reif JH, Tate SR Vyhledávání v neznámém prostředí: optimální randomizovaný algoritmus pro problém krávy // SODA. — 1993.