Az üldözéses elkerülés (amelynek változatai a zsaruk és rablók , valamint a grafikonkeresés ) a matematikai és számítástechnikai problémacsalád , amelyben az egyik csoport egy másik csoport tagjait próbálja csapdába ejteni egy adott környezetben. Az ilyen jellegű problémák korai munkája geometriailag modellezte a környezetet [1] . 1976-ban Torrens Parsons bevezetett egy olyan megfogalmazást, amelyben a mozgások egy gráfra korlátozódnak [2] . A geometriai megfogalmazást néha folyamatos törekvés-elkerülésnek , a gráf-formulációt pedig diszkrét üldözés-elkerülésnek (néha gráfkeresésnek is ) nevezik . A jelenlegi kutatások általában e két készítmény valamelyikére korlátozódnak.
Az üldözés-elkerülés probléma diszkrét megfogalmazásában a környezetet gráfként modellezzük .
A szár-elkerülésnek számtalan változata létezik, bár ezek általában sok elemet tartalmaznak. Egy ilyen feladat tipikus alappéldája a zsaruk és rablók játék. Az üldözők és az üldözöttek a gráf csúcsait foglalják el . Az ellenfelek felváltva mozognak, és minden lépés abból áll, hogy nem mozognak, vagy egy él mentén mozognak a szomszédos csomóponthoz. Ha az üldöző ugyanazt a csomópontot foglalja el, mint az üldözött, akkor elfogottnak minősül, és eltávolították a játékból. A kérdést általában így fogalmazzák meg: hány üldözőre van szükség az összes üldözött elfogásához. Ha az üldözés sikeres, a gráfot győztes rendőr gráfnak nevezzük . Ebben az esetben a követett mindig lineáris időben rögzíthető a gráf n csúcsainak számából . A k üldözött által üldözött r elfogása rn sorrendben történik , de egynél több üldözőre vonatkozó pontos határok nem ismertek.
A közlekedési szabályokat gyakran megváltoztatják az üldözött sebességének megváltoztatásával. A sebesség az élek maximális száma, amennyit a követett egy mozdulattal át tud haladni. A fenti példában az üldözött személy sebessége eggyel egyenlő. Egy másik szélsőség a végtelen sebesség fogalma, amely lehetővé teszi, hogy az üldözött bármely olyan csomópontba lépjen, amelyhez a kezdő és végpozíció között van egy út , amely nem tartalmaz csomópontokat üldözőkkel. Hasonlóképpen, egyes változatok „helikoptereket” biztosítanak az üldözőknek, amelyek lehetővé teszik számukra, hogy bármely csúcsra mozduljanak.
A többi opció figyelmen kívül hagyja azokat a megszorításokat, amelyek szerint az üldözőknek és az üldözötteknek a csomópontban kell lenniük, és megengedik, hogy valahol a peremen belül legyen. Ezeket a változatokat gyakran söprési feladatoknak nevezik, míg az előző változatok a keresési feladatok kategóriájába tartoznak.
Egyes opciók egyenértékűek a grafikon fontos paramétereivel. Konkrétan az üldözők számának megtalálása a végtelen sebességgel üldözött személy rögzítéséhez a G grafikonon (amikor az üldözők és az üldözöttek nem korlátozódnak mozgásonkénti mozgásokra, hanem egyidejűleg is mozoghatnak), megegyezik az üldözött fa szélességének megállapításával. G grafikonon , a követett nyerő stratégiája pedig a G gráfban való elrejtés fogalmával írható le. Ha ez a követett dolog láthatatlan az üldözők számára, akkor a probléma egyenértékű az útszélesség vagy a csúcsok szétválasztásával [3] . Az üldözők számának megtalálása ahhoz, hogy egy láthatatlan üldözőt a G gráfban egyetlen lépésben rögzítsen, megegyezik a G gráf legkevésbé domináns halmazának megtalálásával , feltételezve, hogy az üldözők kezdetben bárhol lehetnek, ahol csak akarnak.
A „Scotland Yard” társasjáték az üldözés-elkerülési probléma egy változata.
Az üldözés-elkerülési problémák egyes változatainak összetettsége, nevezetesen az, hogy hány üldözőre van szükség egy adott gráf törléséhez, és hogy egy adott számú üldözőnek hogyan kell haladnia a grafikonon ahhoz, hogy a megtett távolságok minimális összegével törölje azt. vagy a játék befejezéséhez szükséges minimális idővel Nimrod Megiddo, S. L. Hakimi, Michael R. Garay, David S. Johnson és Christos H. Papadimitriou és R. Bori, K. Tovey és S. Koenig tanulmányozta [4] .
A többjátékos üldözéses-elkerülési játékok megoldása is egyre nagyobb figyelmet kap. Lásd R. Vidal és munkatársai [5] , Chang és Furukawa [6] , Espaniya, Kim és Sastri [7] cikkeit és az ezekben a cikkekben található hivatkozásokat. Marcos A. M. Vieira, Ramesh Govindan és Gaurav S. Sukatmi [8] olyan algoritmust javasoltak, amely minimális végrehajtási idővel egy stratégiát számol ki az üldözők számára, hogy megragadja az összes üldözőt, amikor minden játékos a teljes tudáson alapuló optimális döntést hoz. Ez az algoritmus olyan esetekben is használható, amikor az üldözöttek sokkal gyorsabbak, mint az üldözők. Sajnos ez az algoritmus nem skálázódik tovább, mint néhány robot. Ennek a problémának a leküzdésére Marcos A. M. Vieira, Ramesh Govindan és Gaurav S. Sukatmi egy particionáló algoritmust fejlesztettek ki és valósítottak meg, ahol az üldözők úgy ragadják meg az üldözöttet, hogy a játékot egy üldözött és több üldözővel rendelkező játékokra bontják.
Az üldözés-kerülő játékok folyamatos megfogalmazása során a környezetet geometrikusan modellezik, általában euklideszi sík vagy más sokaság formájában . A játékváltozatok korlátozhatják a játékosok manőverezhetőségét, például sebesség- vagy gyorsulási korlátokat. Akadályok is használhatók.
Az üldözés-kijátszás problémájának egyik első alkalmazása a rakétavezérlő rendszerek voltak. E rendszerek feladatait Rufus Isaacs , a RAND Corporation munkatársa fogalmazta meg [1] .