Zaručená teorie vyhledávání

Garantovaná teorie hledání (nebo teorie hledání ; zkráceně TGP ) je odvětví matematiky , které studuje vlastnosti hledání na grafech a topologických prostorech .

Volně řečeno, jeden z hlavních úkolů TGP je formulován následovně. V pátrací aréně jsou pronásledovatelé , kteří musí mít jistotu, že chytí takzvaného evadera , o jehož rychlosti a poloze chybí informace. Všichni se neustále pohybují po hledací aréně . Jsme povinni najít minimální počet pronásledovatelů, u kterých je zaručeno, že budou schopni chytit evadera. Číselná charakteristika, která popisuje minimální počet pronásledovatelů potřebných k dopadení evadera, se nazývá arénové vyhledávací číslo . [jeden]

Například vyhledávací číslo segmentu se rovná : pronásledovatele stačí umístit na jeden z konců segmentu, odkud přejde na druhý konec, kde zaručeně chytí unikajícího. A na kruhu už jeden pronásledovatel nestačí, protože vyhýbající se bude držet v bodě diametrálně opačném k tomuto pronásledovateli. V grafu ve tvaru písmene „T“ jeden pronásledovatel také nestačí, protože po dosažení „vidlice“ nebude schopen s jistotou odhadnout, která ze dvou zbývajících částí je únikem. Dva pronásledovatelé ale budou stačit, proto se hledané číslo tohoto grafu rovná .

V případě libovolného grafu zůstává problém najít hledané číslo otevřený . [jeden]

Historie

Je zvláštní, že otázku nejmenšího počtu pronásledovatelů poprvé nastolil speleolog Breish. Představte si, že v nějaké jeskyni, skládající se z chodeb a průlezů, se ztratil nešťastný průzkumník, kterého musíme zachránit. Máme k dispozici mapu jeskyně (graf), ale počet záchranářů je omezený. Skutečnost, že se ztracený jeskyňář chce sejít se záchranáři, nám v otázce zaručené záchrany nijak neulehčuje. Dokáže se bezcílně vrhnout po jeskyni neznámou rychlostí. Je nutné vypracovat plán pátrání, který zaručí záchranu jeskyňáře, to znamená, že vyloučí jakoukoli možnost kolem něj. [2]

Problém najít hledané číslo poprvé nezávisle na sobě položili matematici Torrance Parsons [3] a Nikolaj Petrov [4] v 80. letech 20. století. Jejich dokumenty obsahovaly řešení problému hledání stromů . Po nějaké době se ukázalo [5] , že problém najít hledané číslo je NP-úplný . Ve stejném příspěvku byly charakterizovány všechny grafy s hledaným číslem menším než 4. V roce 1989 P. A. Golovach dokázal [6] , že topologické a kombinatorické formulace problému pronásledování jsou ekvivalentní. Později (v trochu jiné formulaci) se ukázalo [7] , že mezi všemi optimálními hledáními v grafu lze vyčlenit monotónní hledání. Ve výše uvedených pracích jsme se zabývali vyhledáváním v grafech. V roce 2022 D. A. Grishmanovsky položil a studoval problém hledání v topologickém prostoru.

Sekce teorie garantovaného vyhledávání

Teorie konečného zaručeného vyhledávání

Finite Guaranteed Search Theory (TFG), neboli teorie zaručeného vyhledávání v grafech, je část teorie zaručeného vyhledávání, ve které jakékoli vyhledávání využívá konečný počet pronásledovatelů, je věnována vyhledávání hledaných čísel v grafech a studiu vlastnosti vyhledávání na kombinatorických grafech .

Analytická teorie zaručeného vyhledávání

Analytic Guaranteed Search Theory (ATGP) – zabývá se studiem vyhledávání pomocí nekonečné množiny pronásledovatelů. V ATGP je důležité, aby množiny, tak či onak související se zkoumanou oblastí, byly vždy měřitelné .

Aplikace

Jedna z prvních aplikací TGP byla v systémech řízení raket . Úlohy pro tyto systémy formuloval Rufus Isaacs z RAND Corporation [8] . Někteří vědci se domnívají, že THP lze použít k vytvoření antivirových programů. Zde je názor známého odborníka Bienstocka [9] :

Zvažte chování počítačového viru v síti. Za předpokladu nejhoršího bychom měli mít podezření, že je infikována celá síť, takže by měly být uzly vyčištěny. Předpokládejme, že máme několik kopií očkovacích programů a vytváření dalších kopií je nepraktické. Na druhou stranu, špatně navržená strategie může vést k opětovné infekci hostitele. Úkolem je tedy vyvinout strategii čištění, která využívá co nejméně kopií očkovacích programů.

TGP má také aplikace [1] v takových oblastech vědecké činnosti, jako je

a mnoho dalších.

Viz také

Poznámky

  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 .

Literatura