Joc de căutare

Jocul de căutare  este un joc de două persoane cu sumă zero care are loc pe un set numit spațiu de căutare. Căutătorul poate alege orice traiectorie continuă supusă unei limite de viteză maximă. Se presupune întotdeauna că nici căutătorul, nici ascunzătorul nu sunt conștienți de mișcările celuilalt jucător până când distanța dintre ele este mai mică (sau egală cu) raza de detectare și chiar în acel moment se face captura. Ca modele matematice , jocurile de căutare pot fi aplicate în domenii precum jocurile de ascunselea jucate de copii sau în anumite circumstanțe tactice militare. Jocurile de căutare au fost introduse în ultimul capitol al Jocurilor diferențiale clasice ale lui Rufus Isaacs [1] și dezvoltate ulterior de Shmuel Gal [2] [3] și Steve Alpern [3] . Jocul „ Prițesa și Bestia ” tratează o țintă în mișcare.

Strategie

O strategie naturală de căutare pentru o țintă fixă ​​într-un grafic este găsirea curbei minime închise L care trece prin toate arcele graficului. (L se numește traseul poștașului chinez ). Apoi ocolim L cu probabilitate 1/2 pentru fiecare direcție. Această strategie funcționează bine dacă graficul Euler este . În general, traseul poștașului chinez este o strategie optimă dacă și numai dacă graficul constă dintr-un set de grafice Euler conectate printr-o structură arborescentă [4] . Un exemplu înșelător de simplu de graf care nu este din această familie este format din două noduri conectate prin trei arce. Traversarea aleatorie a poștașului chinez (echivalent cu trecerea a trei arce în ordine aleatorie) nu este optimă, iar calea optimă pentru a găsi aceste trei arce este complicată [2] .

Zone nelimitate

În cazul general al unei zone de căutare nemărginite, ca și în cazul algoritmului online , o strategie acceptabilă ar fi folosirea unei funcții de pierdere normalizate (numită raportul de concurență în literatură ).

Traiectoria minimax pentru probleme de acest tip este întotdeauna o secvență geometrică (sau o funcție exponențială pentru probleme continue). Acest rezultat oferă o metodă simplă de găsire a unei traiectorii minimax prin minimizarea unui singur parametru (generatorul acestei secvențe) în loc de a căuta în întreg spațiul traiectoriilor. Acest instrument este folosit în problema de căutare liniară , adică problema găsirii unui scop pe o linie infinită, care a primit multă atenție recent și a fost analizată ca un joc de căutare [5] . De asemenea, a fost folosit pentru a găsi o traiectorie minimax pentru a găsi un set de raze care converg într-un punct. Căutarea optimă pe plan se realizează folosind spirale exponențiale [2] [3] [6] .

Căutarea razelor convergente a fost mai târziu redescoperită în literatura științifică ca „problema căii vacilor” [7] .

Vezi și

• Teoria căutării garantate

Note

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

Literatură

• Rufus Isaacs. Jocuri diferențiale . — John Wiley și fiii. — 1965.
• Gal S. Despre optimitatea unei strategii simple de căutare a graficelor // Int. J. Teoria jocurilor. — 2000.
• Shmuel Gal. Jocuri de căutare / Richard Bellman. - New York: Academic Press, 1980. - (Matematică în știință și inginerie). — ISBN 0-12-273850-0 .
• Alpern S., Gal S. Theory of Search Games and Rendezvous. - New York, Boston, Londra, Moscova: Kluwer Academic Publishers, 2003. - (Seria internațională în cercetarea operațională și știința managementului). - 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 , nr. 4 . - S. 419-429 . - doi : 10.1007/BF02798690 .
• Chrobak M. O prințesă care înoată în ceață în căutarea unei vaci monstru // Știri ACM Sigact. - 2004. - T. 35 , nr. 2 .
• Kao MY, Reif JH, Tate SR Căutarea într-un mediu necunoscut: un algoritm optim randomizat pentru problema cow-path // SODA. — 1993.