Sök spel

Ett sökspel är ett nollsummespel för två personer som utspelar sig i en uppsättning som kallas sökutrymmet. Sökaren kan välja vilken kontinuerlig bana som helst med en maximal hastighetsbegränsning. Det antas alltid att varken den som söker eller gömmer sig har någon kunskap om den andra spelarens rörelse förrän deras avstånd från varandra är mindre än eller lika med upptäcktsradien och just i detta ögonblick inträffar fångst. Som matematiska modeller kan sökspel tillämpas på områden som kurragömma-spel som barn spelar eller representationer av vissa taktiska militära situationer. Området sökspel introducerades i det sista kapitlet i Rufus Isaacs klassiska bok "Differential Games" och har utvecklats vidare av Shmuel Gal och Steve Alpern . Prinsessan och monsterspelet handlar om ett rörligt mål.

Strategi

En naturlig strategi för att söka efter ett stationärt mål i en graf är att hitta en minimal sluten kurva L som täcker alla bågar i grafen. (L kallas en kinesisk brevbärartur ). Kör sedan L med sannolikhet 1/2 för varje riktning. Denna strategi verkar fungera bra om grafen är Eulerian . I allmänhet är denna slumpmässiga kinesiska brevbärarturné verkligen en optimal sökstrategi om och bara om grafen består av en uppsättning Eulerian-grafer kopplade i en trädliknande struktur. Ett missvisande enkelt exempel på en graf som inte tillhör denna familj består av två noder sammankopplade med tre bågar. Den slumpmässiga kinesiska brevbärarturen (motsvarande att korsa de tre bågarna i en slumpmässig ordning) är inte optimal, och det optimala sättet att söka i dessa tre bågar är komplicerat.

Ogränsade domäner

I allmänhet är det rimliga ramverket för att söka på en ogränsad domän, som i fallet med en onlinealgoritm , att använda en normaliserad kostnadsfunktion (kallad konkurrensförhållandet i datavetenskaplig litteratur). Minimaxbanan för problem av dessa typer är alltid en geometrisk sekvens (eller exponentiell funktion för kontinuerliga problem) . Detta resultat ger en enkel metod för att hitta minimax-banan genom att minimera över en enda parameter (generatorn av denna sekvens) istället för att söka över hela banautrymmet. Det här verktyget har använts för det linjära sökproblemet , dvs att hitta ett mål på den oändliga linjen, vilket har väckt stor uppmärksamhet under flera decennier och har analyserats som ett sökspel. Den har också använts för att hitta en minimaxbana för att söka efter en uppsättning samtidiga strålar. Optimal sökning i planet utförs genom att använda exponentiella spiraler. Att söka efter en uppsättning samtidiga strålar återupptäcktes senare i datavetenskapslitteraturen som "kovägsproblemet".