Vi studerar det klassiska problemet som infördes av R. Isaacs och S. Gal att minimera tiden för att hitta en dold punkt H på ett nätverk Q flytta från en känd utgångspunkt. I stället för att anta den traditionella kontinuerliga enhet hastighet väg paradigm, använder vi den dynamiska "öka sökning" paradigm som nyligen införts av författarna. Här de regioner S(t) som har sökts efter tid t ökar från utgångspunkten och har total längd t. Grovt talat sökningen följer en sekvens av bågar a i sådan att var och en börjar vid någon punkt av en tidigare. Denna typ av sökning utförs ofta av verkliga sökteam i jakten på försvunna personer, förrymda fångar, terrorister eller förlorade flygplan. Papperet som introducerade denna typ av sökning löste det kontradiktoriska problemet (där H döljs för att maximera tiden att hittas) för de fall där Q är ett träd eller är 2-arc-anslutet. Detta dokuments huvudsakliga bidrag är att ge två strategiklasser som kan användas på alla nätverk och har förväntat söktider som ligger inom en faktor nära 1 av spelets värde (minimax söktid). Dessa strategiklasser är optimala för träd respektive 2-arc-anslutna nätverk. Vi löser också spelet för cirkel-och-spik nätverk, som kan betraktas som den enklaste klassen av nätverk för vilka en lösning var tidigare okänd.
I ett uppföljande dokument REF studerade samma författare utökad sökning på allmänna nätverk och gav två strategiklasser som har förväntat söktider som ligger inom en faktor nära 1 av spelets värde.
Approximate solutions for expanding search games on general networks
{'venue': None, 'journal': 'Annals of Operations Research', 'mag_field_of_study': ['Computer Science', 'Mathematics']}