A keresőjáték egy kétszemélyes, nulla összegű játék , amely a keresőtérnek nevezett halmazon játszódik . A kereső bármilyen folyamatos pályát választhat, amelyhez a maximális sebességkorlátozás tartozik. Mindig feltételezzük, hogy sem a kereső, sem a rejtőzködő nem ismeri a másik játékos mozgását, amíg a köztük lévő távolság kisebb (vagy egyenlő), mint az észlelési sugár, és abban a pillanatban a rögzítés megtörténik. Matematikai modellként a keresőjátékok olyan területeken alkalmazhatók, mint a gyerekek által játszott bújócska játékok , vagy bizonyos katonai taktikai körülmények között. Rufus Isaacs klasszikus könyvének utolsó fejezetében bemutatott játékok keresése"Differential Games" [1] , majd később Shmuel Gal [2] [3] és Steve Alpern [3] fejlesztette ki . A "A hercegnő és a szörnyeteg " játék egy mozgó célponttal foglalkozik.
A grafikonon lévő rögzített cél természetes keresési stratégiája az, hogy megtaláljuk a minimális zárt L görbét, amely átmegy a gráf összes ívén. (L-t kínai postás útnak hívják ). Ezután minden irányban 1/2 valószínűséggel megyünk L körül. Ez a stratégia jól működik, ha az Euler -gráf . Általánosságban elmondható, hogy a kínai postás útvonal akkor és csak akkor optimális stratégia, ha a gráf egy faszerű szerkezettel összekapcsolt Euler-gráfok halmazából áll [4] . A nem ebbe a családba tartozó gráf megtévesztően egyszerű példája két csomópontból áll, amelyeket három ív köt össze. A kínai postás véletlenszerű áthaladása (amely három ív véletlenszerű sorrendben való áthaladásával egyenlő) nem optimális, és ennek a három ívnek az optimális megtalálása bonyolult [2] .
Egy korlátlan keresési terület általános esetben, mint az online algoritmus esetében, elfogadható stratégia egy normalizált veszteségfüggvény használata (amelyet a szakirodalomban versenyaránynak neveznek ).
Az ilyen típusú feladatok minimax pályája mindig egy geometriai sorozat (vagy egy exponenciális függvény folytonos problémák esetén). Ez az eredmény egy egyszerű módszert kínál a minimax trajektória megtalálására egyetlen paraméter (ennek a sorozatnak a generátora) minimalizálásával, ahelyett, hogy a pályák teljes terében keresne. Ezt az eszközt a lineáris keresési feladatban használják , vagyis a végtelen vonalon való cél megtalálásának problémájában, amely az utóbbi időben nagy figyelmet kapott, és keresőjátékként elemezték [5] . Arra is használták, hogy megtalálják a minimax pályát egy pontban konvergáló sugarak halmazának megtalálásához. Az optimális keresés a síkon exponenciális spirálok segítségével történik [2] [3] [6] .
A konvergáló sugarak keresését később a tudományos irodalom "tehénút-problémaként" fedezte fel [7] .
| Játékelmélet | |
|---|---|
| Alapfogalmak | |
| A játékok típusai |
|
| Megoldási koncepciók | |
| Játékpéldák | |