Chase-evasion (josta poliisit ja rosvot sekä kaaviohaku ovat muunnelmia ) on matematiikan ja tietojenkäsittelytieteen ongelmaperhe , jossa yksi ryhmä yrittää vangita toisen ryhmän jäseniä tietyssä ympäristössä. Varhainen työ tällaisten ongelmien parissa mallinsi ympäristöä geometrisesti [1] . Torrens Parsons esitteli vuonna 1976 muotoilun, jossa liikkeet on rajoitettu graafiin [2] . Geometristä muotoilua kutsutaan joskus jatkuvaksi harjoittamisesta väistöstä ja graafisesta muotoilusta diskreetistä harjoittamisesta väistöstä (joskus myös kaaviohaku ). Nykyinen tutkimus rajoittuu yleensä yhteen näistä kahdesta formulaatiosta.
Tavoitteen kiertämisen ongelman diskreetissä muotoilussa ympäristö mallinnetaan graafina .
Varren kiertämisestä on olemassa lukemattomia muunnelmia, vaikka niillä on taipumus jakaa monia elementtejä. Tyypillinen perusesimerkki tällaisesta tehtävästä on poliisien ja rosvojen peli. Takaajat ja takaa -ajat ovat graafin kärjessä. Vastustajat liikkuvat vuorotellen, ja jokainen liike koostuu joko siitä, että ne eivät liiku tai liikkuvat reunaa pitkin naapurisolmuun. Jos takaa-ajaja on samassa solmussa kuin takaa, hänet katsotaan vangituksi ja poistetuksi pelistä. Kysymys esitetään yleensä näin: kuinka monta takaa-ajajaa tarvitaan kaikkien takaa-avien saamiseen. Jos takaa-ajo onnistuu, kuvaajaa kutsutaan voittavan poliisin graafiksi . Tässä tapauksessa tavoitettu voidaan aina siepata lineaarisessa ajassa graafin kärkien lukumäärästä n . R : n sieppaus , jota k jäljittää, tapahtuu järjestyksessä rn , mutta tarkkoja rajoja useammalle kuin yhdelle takaa-ajalle ei tiedetä.
Usein liikennesääntöjä muutetaan muuttamalla takaa-ajettavan nopeutta. Nopeus on reunojen enimmäismäärä, jonka tavoitettava voi ohittaa yhdellä liikkeellä. Yllä olevassa esimerkissä takaa-ajettavan henkilön nopeus on yhtä suuri. Toinen äärimmäinen on äärettömän nopeuden käsite , joka sallii jahtaavan siirtymisen mihin tahansa solmuun, johon lähtö- ja loppuasennon välillä on polku , joka ei sisällä solmuja takaa-ajoineen. Samoin jotkin muunnelmat tarjoavat takaa-ajoille "helikoptereita", joiden avulla he voivat siirtyä mihin tahansa huippuun.
Muut vaihtoehdot jättävät huomiotta rajoitukset, joiden mukaan takaa-ajien ja takaa-ajon on oltava solmussa, ja sallivat sen olla jossain reunan sisällä. Näitä muunnelmia kutsutaan usein pyyhkäisytehtäviksi, kun taas aiemmat variantit kuuluvat sitten hakutehtävien luokkaan.
Jotkut vaihtoehdot vastaavat tärkeitä kaavioparametreja. Etenkin, jos takaa-ajettavien lukumäärän löytäminen äärettömällä nopeudella ajettavaan kuvaajasta G (kun takaa-ajajat ja takaa-ajat eivät rajoitu liikkeisiin, jotka liikkuvat liikkeeltä, vaan voivat liikkua samanaikaisesti) on sama kuin puun leveyden löytäminen. graafi G , ja tavoitellun voittostrategia voidaan kuvata kaaviossa G piiloutumalla . Jos tavoiteltu on näkymätöntä takaa-ajoille, niin ongelma vastaa polun leveyden tai kärkien erotuksen löytämistä [3] . Sellaisen takaa-ajien määrän löytäminen, joka tarvitaan yhden näkymättömän takaa-ajan vangitsemiseen kaaviossa G yhdellä siirrolla, vastaa vähiten hallitsevan graafin G joukon löytämistä olettaen, että takaa-ajat voivat aluksi olla missä haluavat.
Lautapeli "Scotland Yard" on muunnos takaa-ajo-kiertoongelmasta.
Joidenkin takaa-ajon kiertämisongelmien muunnelmien monimutkaisuus, nimittäin se, kuinka monta takaa-ajajaa tarvitaan tietyn kaavion tyhjentämiseen ja kuinka tietyn määrän takaajia on liikuttava kaaviota pitkin, jotta se selviää joko kuljettujen matkojensa vähimmäissummalla. tai minimiaika pelin suorittamiseen, tutkivat Nimrod Megiddo, S. L. Hakimi, Michael R. Garay, David S. Johnson ja Christos H. Papadimitriou ja R. Bori, K. Tovey ja S. Koenig [4] .
Myös usean pelaajan takaa-ajo-kiertopelien ratkaiseminen saa yhä enemmän huomiota. Katso R. Vidalin ym. [5] , Changin ja Furukawa [6] , Espaniyan, Kimin ja Sastrin [7] artikkelit ja viittaukset näissä artikkeleissa. Marcos A. M. Vieira, Ramesh Govindan ja Gaurav S. Sukatmi [8] ehdottivat algoritmia, joka laskee takaa-ajoille strategian mahdollisimman lyhyellä suoritusajalla kaikkien takaa-ajien vangitsemiseksi, kun kaikki pelaajat tekevät täydellisen tiedon perusteella optimaalisen päätöksen. Tätä algoritmia voidaan käyttää myös tapauksissa, joissa jahtaajat ovat paljon nopeampia kuin takaajat. Valitettavasti tämä algoritmi ei skaalaudu pidemmälle kuin pieni määrä robotteja. Tämän ongelman voittamiseksi Marcos A. M. Vieira, Ramesh Govindan ja Gaurav S. Sukatmi kehittivät ja ottavat käyttöön osiointialgoritmin, jossa takaa-ajat vangitsevat takaa-ajoonsa hajottamalla pelin peleiksi, joissa on yksi jahtaaja.
Jatkuvassa tavoittelun välttämispelien muotoilussa ympäristö mallinnetaan geometrisesti, tavallisesti euklidisen tason tai muun monimuotoisena . Pelimuunnelmat voivat asettaa rajoituksia pelaajien ohjattavuudelle, kuten nopeus- tai kiihtyvyysrajoituksia. Myös esteitä voidaan käyttää.
Yksi ensimmäisistä takaa-ajon-kierto-ongelman sovelluksista oli ohjusohjausjärjestelmät. Näiden järjestelmien tehtävät muotoili Rufus Isaacs RAND Corporationista [1] .