Søg spil

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. februar 2022; verifikation kræver 1 redigering .

Søgespillet  er et to-personers nulsumsspil, der foregår på et sæt kaldet søgerummet. Søgeren kan vælge en hvilken som helst kontinuerlig bane med en maksimal hastighedsgrænse. Det antages altid, at hverken søgeren eller skjuleren er opmærksomme på den anden spillers bevægelser, før afstanden mellem dem er mindre end (eller lig med) detektionsradius, og netop i det øjeblik er fangsten foretaget. Som matematiske modeller kan søgespil anvendes i områder som gemmeleg spil, der spilles af børn, eller under nogle militære taktiske omstændigheder. Søgespil blev introduceret i det sidste kapitel af Rufus Isaacs ' klassiske Differential Games [1] og senere udviklet af Shmuel Gal [2] [3] og Steve Alpern [3] . Spillet "The Princess and the Beast " omhandler et bevægeligt mål.

Strategi

En naturlig søgestrategi for et fast mål i en graf er at finde den mindste lukkede kurve L, der går gennem alle grafens buer. (L kaldes den kinesiske postbudsrute ). Så går vi rundt om L med sandsynlighed 1/2 for hver retning. Denne strategi fungerer godt, hvis Euler- grafen er . Generelt er den kinesiske postbudsrute en optimal strategi, hvis og kun hvis grafen består af et sæt Euler-grafer forbundet med en trælignende struktur [4] . Et vildledende simpelt eksempel på en graf, der ikke er fra denne familie, består af to knudepunkter forbundet med tre buer. Tilfældigt at krydse det kinesiske postbud (svarende til at passere tre buer i tilfældig rækkefølge) er ikke optimalt, og den optimale vej til at finde disse tre buer er kompliceret [2] .

Ubegrænsede områder

I det generelle tilfælde af et ubegrænset søgeområde, som i tilfældet med onlinealgoritmen , ville en acceptabel strategi være at bruge en normaliseret tabsfunktion (kaldet konkurrenceforholdet i litteraturen ).

Minimax -banen for problemer af denne type er altid en geometrisk sekvens (eller en eksponentiel funktion for kontinuerlige problemer). Dette resultat giver en enkel metode til at finde en minimax-bane ved at minimere en enkelt parameter (generatoren af ​​denne sekvens) i stedet for at søge gennem hele banerummet. Dette værktøj bruges i det lineære søgeproblem , det vil sige problemet med at finde et mål på en uendelig linje, som har fået meget opmærksomhed på det seneste og er blevet analyseret som et søgespil [5] . Det blev også brugt til at finde en minimax-bane til at finde et sæt stråler, der konvergerer i et punkt. Optimal søgning på flyet udføres ved hjælp af eksponentielle spiraler [2] [3] [6] .

Søgen efter konvergerende stråler blev senere genopdaget i den videnskabelige litteratur som "kovejsproblemet" [7] .

Se også

Noter

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

Litteratur