Taatun haun teoria

Taattu hakuteoria (tai hakuteoria ; lyhennettynä TGP ) on matematiikan haara , joka tutkii graafien ja topologisten avaruuksien haun ominaisuuksia .

Löyhästi sanottuna yksi TGP:n päätehtävistä on muotoiltu seuraavasti. Etsintäareenalla on takaa - ajia , joille on taattava, että he saavat kiinni ns. kiertäjästä , jonka nopeus- ja sijaintitiedot puuttuvat. Kaikki liikkuvat hakuareenalla jatkuvasti . Meidän on löydettävä vähimmäismäärä takaa-ajoja, jotka taatusti pystyvät tavoittamaan kiertäjän. Numeerista ominaisuutta, joka kuvaa väistäjän kiinni saamiseksi vaadittavien takaa-ajien vähimmäismäärää, kutsutaan areenan hakunumeroksi . [yksi]

Esimerkiksi segmentin hakunumero on yhtä suuri kuin : riittää, että takaa-ajaja asetetaan segmentin toiseen päähän, josta hän siirtyy toiseen päähän, jossa hän saa taatusti kiinni kiertäjän. Ja ympyrässä yksi takaa-ajaja ei enää riitä, koska kiertäjä pysyy pisteessä, joka on diametraalisesti vastakkainen kuin tämä takaa-ajaja. T-kirjaimen muotoisessa kaaviossa yksi takaa-ajaja ei myöskään riitä, koska saavutettuaan "haarukan" hän ei voi varmasti arvata kumpi kahdesta jäljellä olevasta osasta on kiertäjä. Mutta kaksi takaa-ajajaa riittää, joten tämän kaavion hakunumero on yhtä suuri kuin .

Mielivaltaisen graafin tapauksessa hakunumeron löytämisongelma jää avoimeksi . [yksi]

Historia

On uteliasta, että speleologi Breish nosti ensimmäistä kertaa kysymyksen takaa-ajoista pienimmästä määrästä. Kuvittele, että jossain luolassa, joka koostuu käytävistä ja kaivoista, eksyi epäonninen tutkimusmatkailija, joka meidän on pelastettava. Meillä on käytössämme luolan kartta (kaavio), mutta pelastajien määrä on rajoitettu. Se, että kadonnut luola haluaa tavata pelastajia, ei helpota tehtäväämme taatun pelastuksen suhteen. Hän voi heittää päämäärättömästi luolan ympäri tuntemattomalla nopeudella. On laadittava etsintäsuunnitelma, joka takaa luolamiehen pelastamisen, toisin sanoen sulkee pois mahdollisuutta ohittaa hänet. [2]

Hakunumeron löytämisen ongelman esittivät ensin itsenäisesti matemaatikot Torrance Parsons [3] ja Nikolai Petrov [4] 1980-luvulla. Heidän paperinsa sisälsivät ratkaisun puiden etsintäongelmaan . Jonkin ajan kuluttua todistettiin [5] , että hakunumeron löytämisen ongelma on NP-täydellinen . Samassa artikkelissa karakterisoitiin kaikki graafit, joiden hakuluku on pienempi kuin 4. Vuonna 1989 P. A. Golovach osoitti [6] , että tavoitteluongelman topologiset ja kombinatoriset formulaatiot ovat samanarvoisia. Myöhemmin (hieman eri muotoilussa) todistettiin [7] , että kaikista graafin optimaalisista hauista voidaan erottaa yksitoikkoinen haku. Yllä luetelluissa töissä käsittelimme graafista hakua. Vuonna 2022 D. A. Grishmanovsky esitti ja tutki topologisessa avaruudessa etsimisen ongelmaa.

Taatun haun teorian osiot

Rajallinen taattu hakuteoria

Rajallisen taatun haun teoria (TFG) tai taatun haun teoria kaavioissa on osa taatun haun teoriaa, jossa missä tahansa haussa käytetään rajallista määrää takaajia, on omistettu graafien hakunumeroiden löytämiseen ja tutkimiseen. kombinatoristen graafien haun ominaisuudet .

Taatun haun analyyttinen teoria

Analyyttinen taattu hakuteoria (ATGP) - tutkii hakuja, joissa käytetään ääretöntä joukkoa takaa-ajia. ATGP:ssä on tärkeää, että tutkittavaan alueeseen tavalla tai toisella liittyvät joukot ovat aina mitattavissa .

Sovellukset

Yksi TGP:n ensimmäisistä sovelluksista oli ohjusohjausjärjestelmissä . Näiden järjestelmien tehtävät muotoili Rufus Isaacs RAND Corporationista [8] . Jotkut tutkijat uskovat, että THP:tä voidaan käyttää virustentorjuntaohjelmien luomiseen. Tässä on tunnetun asiantuntijan Bienstockin mielipide [9] :

Harkitse tietokoneviruksen käyttäytymistä verkossa. Olettaen pahinta, meidän pitäisi epäillä, että koko verkko on saastunut, joten solmut tulisi puhdistaa. Oletetaan, että meillä on useita kopioita rokoteohjelmista ja useampien kopioiden tekeminen on epäkäytännöllistä. Toisaalta huonosti suunniteltu strategia voi johtaa isännän uudelleeninfektioon. Siksi haasteena on kehittää puhdistusstrategia, joka käyttää vähiten kopioita rokoteohjelmista.

Lisäksi TGP:llä on sovelluksia [1] sellaisilla tieteellisen toiminnan aloilla kuin

ja monet muut.

Katso myös

Muistiinpanot

  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 .

Kirjallisuus