Chase-evasion (hvoraf politifolk og røvere og grafsøgning er varianter ) er en familie af problemer inden for matematik og datalogi , hvor en gruppe forsøger at fange medlemmer af en anden gruppe i et bestemt miljø. Tidligt arbejde med problemer af denne art modellerede miljøet geometrisk [1] . I 1976 introducerede Torrens Parsons en formulering, hvor bevægelser er begrænset til en graf [2] . Den geometriske formulering kaldes undertiden for continuous pursuit-evasion , og grafformuleringen diskret pursuit-evasion (nogle gange også grafsøgning ). Nuværende forskning er normalt begrænset til en af disse to formuleringer.
I den diskrete formulering af forfølgelses-unddragelsesproblemet er miljøet modelleret som en graf .
Der er utallige variationer af stilk-unddragelse, selvom de har en tendens til at dele mange elementer. Et typisk grundlæggende eksempel på en sådan opgave er politiets og røvere-spillet. Forfølgerne og de forfulgte indtager grafens toppunkter . Modstandere bevæger sig skiftevis, og hvert træk består af enten ikke at bevæge sig eller bevæge sig langs en kant til en naboknude. Hvis forfølgeren indtager samme node som den forfulgte, anses han for at være taget til fange og fjernet fra spillet. Spørgsmålet stilles normalt således: hvor mange forfølgere skal der til for at fange alle de forfulgte. Hvis forfølgelsen lykkes, kaldes grafen for en vindende politimandsgraf . I dette tilfælde kan en forfulgt altid fanges i lineær tid fra antallet af hjørner n af grafen. Indfangningen af r forfulgt af k forfulgt sker i en tid med orden rn , men de nøjagtige grænser for mere end én forfølger kendes ikke.
Ofte ændres færdselsreglerne ved at ændre hastigheden på den forfulgte. Hastighed er det maksimale antal kanter, som den forfulgte kan passere i et træk. I eksemplet ovenfor har den forfulgte person en hastighed svarende til én. Et andet yderpunkt er konceptet med uendelig hastighed, som gør det muligt for den forfulgte at bevæge sig til enhver knude, hvortil der er en sti mellem start- og slutpositionen, som ikke indeholder knudepunkter med forfølgere. På samme måde giver nogle varianter forfølgerne "helikoptere", der giver dem mulighed for at bevæge sig til enhver top.
De andre muligheder ignorerer de begrænsninger, at forfølgerne og de forfulgte skal være i knudepunktet og tillade, at det er et sted inden for kanten. Disse varianter omtales ofte som fejende opgaver, mens de tidligere varianter så falder ind under kategorien søgeopgaver.
Nogle muligheder svarer til vigtige grafparametre. Især at finde det nødvendige antal forfølgere for at fange en forfulgt med uendelig hastighed på grafen G (når forfølgerne og de forfulgte ikke er begrænset til træk træk for træk, men kan bevæge sig samtidigt) svarer til at finde træbredden af graf G , og vinderstrategien for den forfulgte kan beskrives i form af at skjule sig i graf G. Hvis denne forfulgte er usynlig for forfølgerne, så svarer problemet til at finde vejbredden eller topadskillelsen [3] . At finde antallet af forfølgere, der er nødvendigt for at fange én usynlig forfølger i graf G i ét træk, svarer til at finde antallet af mindst dominerende sæt af graf G , idet det antages, at forfølgerne i begyndelsen kan være hvor som helst, de vil.
Brætspillet "Scotland Yard" er en variant af forfølgelses-unddragelsesproblemet.
Kompleksiteten af nogle varianter af forfølgelses-unddragelsesproblemerne, nemlig hvor mange forfølgere er nødvendige for at rydde en given graf, og hvordan et givet antal forfølgere skal bevæge sig langs grafen for at klare den enten med minimumsummen af deres tilbagelagte afstande eller med den minimale tid til at fuldføre spillet, blev studeret af Nimrod Megiddo, S. L. Hakimi, Michael R. Garay, David S. Johnson og Christos H. Papadimitriou og R. Bori, K. Tovey og S. Koenig [4] .
Løsning af multi-player pursuit-evasion- spil får også stigende opmærksomhed. Se artikler af R. Vidal et al. [5] , Chang og Furukawa [6] , Espaniya, Kim og Sastri [7] og referencer i disse artikler. Marcos A. M. Vieira, Ramesh Govindan og Gaurav S. Sukatmi [8] foreslog en algoritme, der beregner en strategi med minimum udførelsestid for forfølgere for at fange alle forfølgere, når alle spillere træffer en optimal beslutning baseret på fuldstændig viden. Denne algoritme kan også bruges i tilfælde, hvor de forfulgte er meget hurtigere end forfølgerne. Desværre skalerer denne algoritme ikke længere end et lille antal robotter. For at overvinde dette problem udviklede og implementerede Marcos A. M. Vieira, Ramesh Govindan og Gaurav S. Sukatmi en partitioneringsalgoritme, hvor forfølgere fanger det forfulgte ved at dekomponere spillet til spil med én forfulgt og flere forfølgere.
I en kontinuerlig formulering af forfølgelses-undgåelsesspil modelleres miljøet geometrisk, normalt i form af et euklidisk plan eller en anden mangfoldighed . Spilvariationer kan pålægge begrænsninger på spillernes manøvredygtighed, såsom hastigheds- eller accelerationsgrænser. Forhindringer kan også bruges.
En af de første anvendelser af forfølgelses-unddragelsesproblemet var missilkontrolsystemer. Opgaverne for disse systemer blev formuleret af Rufus Isaacs fra RAND Corporation [1] .