Evadarea urmăririi (din care polițiști și hoți și căutarea grafică sunt variante ) este o familie de probleme de matematică și informatică în care un grup încearcă să prindă membrii altui grup într-un anumit mediu. Lucrările timpurii asupra problemelor de acest fel au modelat mediul în mod geometric [1] . În 1976, Torrens Parsons a introdus o formulare în care mișcările sunt limitate la un grafic [2] . Formularea geometrică este uneori numită urmărire-evaziune continuă , în timp ce formularea grafică este numită urmărire-evaziune discretă (uneori și căutare grafică ).). Cercetările actuale se limitează de obicei la una dintre aceste două formulări.
În formularea discretă a problemei urmărire-evaziune, mediul este modelat ca un grafic .
Există nenumărate variații ale evadării tulpinilor, deși tind să împărtășească multe elemente. Un exemplu de bază tipic al unei astfel de sarcini este jocul polițiștilor și hoților. Următorii și urmăritorii ocupă vârfurile graficului. Oponenții se mișcă alternativ și fiecare mișcare constă fie în nedeplasarea, fie în deplasarea de-a lungul unei margini către un nod învecinat. Dacă urmăritorul ocupă același nod cu cel urmărit, el este considerat a fi capturat și eliminat din joc. Întrebarea este de obicei pusă astfel: de câți urmăritori sunt necesari pentru a-i captura pe toți urmăriți. Dacă urmărirea reușește, graficul se numește grafic de polițist câștigător . În acest caz, unul urmărit poate fi întotdeauna surprins în timp liniar din numărul de vârfuri n ale graficului. Captarea lui r urmărit de k urmărit are loc într-un timp de ordin rn , dar limitele exacte pentru mai mult de un urmăritor nu sunt cunoscute.
De multe ori regulile de circulație sunt modificate prin schimbarea vitezei celui urmărit. Viteza este numărul maxim de muchii pe care cel urmărit le poate trece într-o singură mișcare. În exemplul de mai sus, persoana urmărită are o viteză egală cu unu. O altă extremă este conceptul de viteză infinită , care permite urmăritului să se deplaseze către orice nod la care există o cale între pozițiile de început și de sfârșit care nu conține noduri cu urmăritori. În mod similar, unele variante oferă urmăritorilor „elicoptere” care le permit să facă o mișcare spre orice vârf.
Celelalte opțiuni ignoră constrângerile pe care urmăritorii și urmăritorii trebuie să fie în nod și îi permit să fie undeva în interiorul marginii. Aceste variante sunt adesea denumite sarcini de măturare, în timp ce variantele anterioare se încadrează apoi în categoria sarcinilor de căutare.
Unele opțiuni sunt echivalente cu parametri importanți ai graficului. În special, găsirea numărului de urmăritori necesari pentru capturarea unui urmărit cu viteză infinită pe graficul G (când urmăritorii și urmăritorii nu se limitează la mișcări mișcare cu mișcare, ci se pot deplasa simultan) echivalează cu găsirea lățimii arborelui graficul G , iar strategia câștigătoare pentru cei urmăriți poate fi descrisă în termeni de ascundere în graficul G. Dacă acest lucru urmărit este invizibil pentru urmăritori, atunci problema este echivalentă cu găsirea lățimii căii sau a separării vârfurilor [3] . Găsirea numărului de urmăritori necesari pentru a captura un urmăritor invizibil în graficul G într-o singură mișcare este echivalent cu găsirea numărului de seturi cel mai puțin dominante din graficul G , presupunând că urmăritorii pot fi inițial oriunde doresc.
Jocul de societate „Scotland Yard” este o variantă a problemei urmărire-evaziune.
Complexitatea unor variante ale problemelor de urmărire-evaziune, și anume de câți urmăritori sunt necesari pentru a șterge un anumit grafic și modul în care un anumit număr de urmăritori trebuie să se deplaseze de-a lungul graficului pentru a-l șterge fie cu suma minimă a distanțelor lor parcurse sau cu timpul minim pentru finalizarea jocului, a fost studiat de Nimrod Megiddo, S. L. Hakimi, Michael R. Garay, David S. Johnson și Christos H. Papadimitriou și R. Bori, K. Tovey și S. Koenig [4] .
Rezolvarea jocurilor de urmărire-evaziune pentru mai mulți jucători primește, de asemenea, o atenție din ce în ce mai mare. Vezi articolele lui R. Vidal și colab. [5] , Chang și Furukawa [6] , Espaniya, Kim și Sastri [7] și referințele din acele articole. Marcos A. M. Vieira, Ramesh Govindan și Gaurav S. Sukatmi [8] au propus un algoritm care calculează o strategie cu timp minim de execuție pentru urmăritori pentru a captura toți urmăritorii atunci când toți jucătorii iau o decizie optimă bazată pe cunoștințe complete. Acest algoritm poate fi folosit și în cazurile în care urmăritorii sunt mult mai rapizi decât urmăritorii. Din păcate, acest algoritm nu crește mai mult decât un număr mic de roboți. Pentru a depăși această problemă, Marcos A. M. Vieira, Ramesh Govindan și Gaurav S. Sukatmi au dezvoltat și implementat un algoritm de partiționare în care urmăritorii captează cei urmăriți prin descompunerea jocului în jocuri cu un urmăritor și mai mulți urmăritori.
Într-o formulare continuă a jocurilor de urmărire-evitare, mediul este modelat geometric, luând de obicei forma unui plan euclidian sau a unei alte varietăți . Variațiile jocului pot impune restricții asupra manevrabilității jucătorilor, cum ar fi limitele de viteză sau accelerație. De asemenea, pot fi folosite obstacole.
Una dintre primele aplicații ale problemei de urmărire-evaziune a fost sistemele de control al rachetelor. Sarcinile pentru aceste sisteme au fost formulate de Rufus Isaacs de la RAND Corporation [1] .