Garanterad sökteori

Garanterad sökteori (eller sökteori ; förkortat TGP ) är en gren av matematiken som studerar egenskaperna för sökning på grafer och topologiska utrymmen .

Löst uttryckt är en av TGP:s huvuduppgifter formulerad enligt följande. Det finns förföljare på sökarenan , som måste garanteras fånga den så kallade undanflyktaren , vars hastighets- och platsinformation saknas. Alla rör sig kontinuerligt på sökarenan . Vi är skyldiga att hitta det minsta antalet förföljare som garanterat kan fånga undanflyktaren. En numerisk egenskap som beskriver det minsta antal förföljare som behövs för att fånga en smygare kallas arenasöknummer . [ett]

Till exempel är söknumret för segmentet lika med : det räcker att placera förföljaren i en av ändarna av segmentet, varifrån han kommer att gå till den andra änden, där han garanterat kommer att fånga undandragaren. Och på cirkeln räcker det inte längre med en förföljare, eftersom förföljaren kommer att hålla sig på en punkt som är diametralt motsatt denna förföljare. I en graf formad som bokstaven "T" räcker det inte heller med en förföljare, för efter att ha nått "gaffeln" kommer han inte att kunna gissa säkert vilken av de två återstående delarna som är undandragaren. Men två förföljare räcker, därför är söknumret på denna graf lika med .

I fallet med en godtycklig graf förblir problemet med att hitta söknumret öppet . [ett]

Historik

Det är märkligt att frågan om det minsta antalet förföljare för första gången togs upp av speleologen Breish. Föreställ dig att i någon grotta, bestående av passager och brunnar, gick en olycklig upptäcktsresande förlorad, som vi måste rädda. Vi har en karta över grottan (grafen) till vårt förfogande, men antalet räddare är begränsat. Att en förlorad grottare vill träffa bärgare gör inte vår uppgift lättare när det kommer till garanterad frälsning. Han kan planlöst pila runt grottan med okänd hastighet. Det krävs att man utvecklar en sökplan som garanterar räddningen av grottmannen, det vill säga utesluter varje möjlighet att passera honom. [2]

Problemet med att hitta söknumret ställdes först oberoende av matematikerna Torrance Parsons [3] och Nikolai Petrov [4] på 1980-talet. Deras papper innehöll en lösning på sökproblemet efter träd . Efter en tid bevisades det [5] att problemet med att hitta söknumret är NP-komplett . I samma artikel karakteriserades alla grafer med ett söktal mindre än 4. 1989 bevisade P. A. Golovach [6] att de topologiska och kombinatoriska formuleringarna av jaktproblemet är likvärdiga. Senare (i en något annorlunda formulering) bevisades [7] att man bland alla optimala sökningar på en graf kan peka ut en monoton sökning. I de ovan listade arbetena behandlade vi sökning på grafer. 2022 ställde och studerade D. A. Grishmanovsky problemet med att söka på ett topologiskt utrymme.

Delar av garanterad sökteori

Finite Guaranteed Search Theory

Finite Guaranteed Search Theory (TFG), eller teorin om garanterad sökning på grafer, är en del av teorin om garanterad sökning, där varje sökning använder ett ändligt antal förföljare, ägnas åt att hitta söknumret på grafer och studera egenskaper för sökning på kombinatoriska grafer .

Analytisk teori om garanterad sökning

Analytic Guaranteed Search Theory (ATGP) - handlar om studiet av sökningar med hjälp av en oändlig uppsättning förföljare. I ATGP är det viktigt att uppsättningarna, på ett eller annat sätt relaterade till området som studeras, alltid är mätbara .

Applikationer

En av de första tillämpningarna av TGP var i missilkontrollsystem . Uppgifterna för dessa system formulerades av Rufus Isaacs från RAND Corporation [8] . Vissa forskare tror att THP kan användas för att skapa antivirusprogram. Här är åsikten från den välkände experten Bienstock [9] :

Tänk på beteendet hos ett datavirus i ett nätverk. Om vi ​​antar det värsta bör vi misstänka att hela nätverket är infekterat, så noderna bör städas upp. Anta att vi har flera kopior av vaccinprogram och att göra fler kopior är opraktiskt. Å andra sidan kan en dåligt utformad strategi leda till återinfektion av värden. Utmaningen är alltså att utveckla en saneringsstrategi som använder så få kopior av vaccinprogrammen.

TGP har också tillämpningar [1] inom sådana områden av vetenskaplig verksamhet som

och många andra.

Se även

Anteckningar

  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 .

Litteratur