Teoria căutării garantate

Teoria căutării garantate (sau teoria căutării ; abreviată ca TGP ) este o ramură a matematicii care studiază proprietățile căutării pe grafice și spații topologice .

Vorbind, una dintre sarcinile principale ale TGP este formulată după cum urmează. Există urmăritori pe arena de căutare , cărora trebuie să li se garanteze că îl prind pe așa-numitul evader , a cărui viteză și informații despre locație lipsesc. Toată lumea se mișcă în arena de căutare în mod continuu . Ni se cere să găsim numărul minim de urmăritori cărora li se garantează că vor putea prinde evadatorul. O caracteristică numerică care descrie numărul minim de urmăritori necesar pentru a prinde un evasor se numește numărul de căutare în arenă . [unu]

De exemplu, numărul de căutare al segmentului este egal cu : este suficient să puneți urmăritorul la unul dintre capetele segmentului, de unde va merge la celălalt capăt, unde este garantat să-l prindă pe evasor. Iar pe cerc, un urmăritor nu mai este suficient, deoarece evasiva se va menține într-un punct diametral opus acestui urmăritor. Într-un grafic în formă de litera „T”, un urmăritor nu este, de asemenea, suficient, deoarece, după ce a ajuns la „furcătură”, nu va putea ghici cu siguranță care dintre cele două părți rămase este evaderul. Dar doi urmăritori vor fi suficiente, prin urmare, numărul de căutare al acestui grafic este egal cu .

În cazul unui grafic arbitrar, problema găsirii numărului de căutare rămâne deschisă . [unu]

Istorie

Este curios că pentru prima dată problema celui mai mic număr de urmăritori a fost pusă de speologul Breish. Imaginați-vă că într-o peșteră, formată din pasaje și cămine, s-a pierdut un explorator ghinionist, pe care trebuie să-l salvăm. Avem o hartă a peșterii (grafic) la dispoziție, dar numărul salvatorilor este limitat. Faptul că un speolog pierdut dorește să se întâlnească cu salvatorii nu ne ușurează sarcina atunci când vine vorba de mântuirea garantată. El poate săgeată fără țintă în jurul peșterii cu o viteză necunoscută. Este necesară elaborarea unui plan de căutare care să garanteze salvarea speologiului, adică excluzând orice posibilitate de a-l trece. [2]

Problema găsirii numărului de căutare a fost pusă pentru prima dată independent de matematicienii Torrance Parsons [3] și Nikolai Petrov [4] în anii 1980. Lucrările lor conţineau o soluţie la problema căutării copacilor . După ceva timp, s-a dovedit [5] că problema găsirii numărului de căutare este NP-complet . În aceeași lucrare au fost caracterizate toate graficele cu un număr de căutare mai mic de 4. În 1989, P. A. Golovach a demonstrat [6] că formulările topologice și combinatorii ale problemei urmăririi sunt echivalente. Mai târziu (într-o formulare puțin diferită) s-a dovedit [7] că dintre toate căutările optime pe un grafic se poate evidenția o căutare monotonă. În lucrările enumerate mai sus, ne-am ocupat de căutarea pe grafice. În 2022, D. A. Grishmanovsky a pus și a studiat problema căutării într-un spațiu topologic.

Secțiuni ale teoriei căutării garantate

Teoria căutării garantate finite

Teoria căutării garantate finite (TFG), sau teoria căutării garantate pe grafice, este o secțiune a teoriei căutării garantate, în care orice căutare folosește un număr finit de urmăritori, este dedicată găsirii numerelor de căutare ale graficelor și studierii proprietăţi de căutare pe grafice combinatorii .

Teoria analitică a căutării garantate

Teoria analitică a căutării garantate (ATGP) - se ocupă cu studiul căutărilor folosind un set infinit de urmăritori. În ATGP, este important ca seturile, într-un fel sau altul legate de zona studiată, să fie întotdeauna măsurabile .

Aplicații

Una dintre primele aplicații ale TGP a fost în sistemele de control al rachetelor . Sarcinile pentru aceste sisteme au fost formulate de Rufus Isaacs de la RAND Corporation [8] . Unii oameni de știință cred că THP poate fi folosit pentru a crea programe antivirus. Iată opinia cunoscutului expert Bienstock [9] :

Luați în considerare comportamentul unui virus de computer într-o rețea. Presupunând ce este mai rău, ar trebui să bănuim că întreaga rețea este infectată, așa că nodurile ar trebui curățate. Să presupunem că avem mai multe copii ale programelor de vaccinare și să facem mai multe copii nu este practic. Pe de altă parte, o strategie prost concepută poate duce la reinfectarea gazdei. Astfel, provocarea este de a dezvolta o strategie de curățare care să folosească cele mai puține copii ale programelor de vaccinare.

De asemenea, TGP are aplicații [1] în domenii de activitate științifică precum

și multe altele.

Vezi și

Note

  1. ↑ 1 2 3 Abramovskaya, Petrov, 2013 .
  2. ↑ Breish, 1967 .
  3. ↑ Parsons, 1976 .
  4. ↑ Petrov, 1982 .
  5. ↑ Megiddo, Hakimi, Garey, 1988 .
  6. ↑ Golovach, 1989 .
  7. ↑ Lapaugh, 1993 .
  8. ↑ Isaacs, 1965 .
  9. ^ Bienstock , 1991 .

Literatură