Chase-evasion (av vilka poliser och rånare och grafsökning är varianter ) är en familj av problem inom matematik och datavetenskap där en grupp försöker fånga medlemmar i en annan grupp i en viss miljö. Det tidiga arbetet med problem av detta slag modellerade miljön geometriskt [1] . 1976 introducerade Torrens Parsons en formulering där rörelser är begränsade till en graf [2] . Den geometriska formuleringen kallas ibland continuous pursuit-evasion , och grafformuleringen diskret pursuit-evasion (ibland även grafsökning ). Nuvarande forskning är vanligtvis begränsad till en av dessa två formuleringar.
I den diskreta formuleringen av problemet med jaktundandragande modelleras miljön som en graf .
Det finns otaliga varianter av stjälkflykt, även om de tenderar att dela många element. Ett typiskt grundläggande exempel på en sådan uppgift är polis- och rånarspelet. Förföljarna och de förföljda upptar grafens hörn . Motståndare rör sig växelvis, och varje drag består av att antingen inte röra sig eller att röra sig längs en kant till en närliggande nod. Om förföljaren upptar samma nod som den förföljde, anses han vara tillfångatagen och borttagen från spelet. Frågan brukar ställas så här: hur många förföljare behövs för att fånga alla förföljda. Om jakten lyckas kallas grafen för en vinnande polisgraf . I detta fall kan en förföljd alltid fångas i linjär tid från antalet hörn n i grafen. Infångandet av r som förföljs av k förföljs sker i en tid av ordning rn , men de exakta gränserna för mer än en förföljare är inte kända.
Ofta ändras trafikreglerna genom att den förföljdes hastighet ändras. Hastighet är det maximala antalet kanter som den förföljde kan passera i ett drag. I exemplet ovan har den förföljde personen en hastighet lika med ett. En annan ytterlighet är konceptet med oändlig hastighet, som tillåter den förföljde att flytta till vilken nod som helst dit det finns en väg mellan start- och slutpositionen som inte innehåller noder med förföljare. På samma sätt förser vissa varianter förföljarna med "helikoptrar" som gör att de kan ta sig till vilken topp som helst.
De andra alternativen ignorerar begränsningarna att förföljarna och de förföljda måste vara i noden och tillåta den att vara någonstans innanför kanten. Dessa varianter benämns ofta svepande uppgifter, medan de tidigare varianterna då hamnar i kategorin sökuppgifter.
Vissa alternativ motsvarar viktiga grafparametrar. I synnerhet, att hitta antalet förföljare som behövs för att fånga en som förföljs med oändlig hastighet på grafen G (när förföljarna och de förföljda inte är begränsade till drag drag för drag, utan kan röra sig samtidigt) motsvarar att hitta trädets bredd på graf G , och den vinnande strategin för den eftersträvade kan beskrivas i termer av att gömma sig i graf G. Om detta eftersträvade är osynligt för förföljarna, då är problemet likvärdigt med att hitta vägbredden eller vertexseparationen [3] . Att hitta antalet förföljare som behövs för att fånga en osynlig förföljare i graf G i ett drag motsvarar att hitta antalet minst dominerande uppsättningar av graf G , förutsatt att förföljarna initialt kan vara var de vill.
Brädspelet "Scotland Yard" är en variant av problemet med jaktundandragande.
Komplexiteten hos vissa varianter av problemen med jaktundandragande, nämligen hur många förföljare som behövs för att rensa en given graf och hur ett givet antal förföljare måste röra sig längs grafen för att klara den antingen med minsta summan av deras tillryggalagda avstånd eller med minsta möjliga tid för att slutföra spelet, studerades av Nimrod Megiddo, S. L. Hakimi, Michael R. Garay, David S. Johnson och Christos H. Papadimitriou och R. Bori, K. Tovey och S. Koenig [4] .
Att lösa flerspelares jakt-undvikande spel får också allt större uppmärksamhet. Se artiklar av R. Vidal et al [5] , Chang och Furukawa [6] , Espaniya, Kim och Sastri [7] och referenser i dessa artiklar. Marcos A. M. Vieira, Ramesh Govindan och Gaurav S. Sukatmi [8] föreslog en algoritm som beräknar en strategi med minsta exekveringstid för förföljare för att fånga alla förföljare när alla spelare fattar ett optimalt beslut baserat på fullständig kunskap. Denna algoritm kan också användas i fall där de förföljda är mycket snabbare än förföljarna. Tyvärr skalar denna algoritm inte längre än ett litet antal robotar. För att övervinna detta problem utvecklade och implementerade Marcos A. M. Vieira, Ramesh Govindan och Gaurav S. Sukatmi en partitioneringsalgoritm där förföljare fångar det eftersträvade genom att bryta ner spelet till spel med en förföljd och flera förföljare.
I en kontinuerlig formulering av jakt-undvikande spel, modelleras miljön geometriskt, vanligtvis i form av ett euklidiskt plan eller annan mångfald . Spelvariationer kan medföra begränsningar för spelarnas manövrerbarhet, såsom hastighets- eller accelerationsgränser. Hinder kan också användas.
En av de första tillämpningarna av problemet med jaktundandragande var missilkontrollsystem. Uppgifterna för dessa system formulerades av Rufus Isaacs från RAND Corporation [1] .