Vyhýbání se pronásledování (jehož variantami jsou policisté a lupiči a vyhledávání v grafu ) je skupina problémů v matematice a počítačové vědě , ve kterých se jedna skupina pokouší chytit členy jiné skupiny do konkrétního prostředí. Rané práce na problémech tohoto druhu modelovaly prostředí geometricky [1] . V roce 1976 Torrens Parsons představil formulaci, ve které jsou pohyby omezeny na graf [2] . Geometrická formulace se někdy nazývá kontinuální pronásledování-vyhýbání se a grafová formulace diskrétní pronásledování-vyhýbání se (někdy také vyhledávání grafů ). Současný výzkum se obvykle omezuje na jednu z těchto dvou formulací.
V diskrétní formulaci problému pronásledování-úniku je prostředí modelováno jako graf .
Existuje nespočet variant vyhýbání se stopkám, i když mají tendenci sdílet mnoho prvků. Typickým základním příkladem takového úkolu je hra policajtů a lupičů. Pronásledovatelé a pronásledovaní zaujímají vrcholy grafu. Protivníci se pohybují střídavě a každý pohyb spočívá v tom, že se buď nepohybují, nebo se pohybují podél hrany k sousednímu uzlu. Pokud pronásledovatel obsadí stejný uzel jako pronásledovaný, je považován za zajatého a odstraněného ze hry. Otázka je obvykle položena takto: kolik pronásledovatelů je potřeba k zachycení všech pronásledovaných. Pokud je pronásledování úspěšné, graf se nazývá vítězný graf policisty . V tomto případě lze jeden sledovaný vždy zachytit v lineárním čase z počtu vrcholů n grafu. K zachycení r pronásledovaného k pronásledovaným dochází v době pořadí rn , ale přesné hranice pro více než jednoho pronásledovatele nejsou známy.
Pravidla provozu se často mění změnou rychlosti pronásledovaného. Rychlost je maximální počet hran, které může pronásledovaný projít jedním tahem. Ve výše uvedeném příkladu má pronásledovaná osoba rychlost rovnou jedné. Dalším extrémem je koncept nekonečné rychlosti, který umožňuje pronásledovaným přesunout se do libovolného uzlu, ke kterému vede mezi počáteční a koncovou polohou cesta, která neobsahuje uzly s pronásledovateli. Podobně některé varianty poskytují pronásledovatelům „vrtulníky“, které jim umožňují přesun na jakýkoli vrchol.
Ostatní možnosti ignorují omezení, že pronásledovatelé a pronásledovaní musí být v uzlu a umožňují, aby byl někde uvnitř okraje. Tyto varianty se často označují jako zametací úlohy, přičemž předchozí varianty pak spadají do kategorie vyhledávacích úloh.
Některé možnosti jsou ekvivalentní důležitým parametrům grafu. Konkrétně zjištění počtu pronásledovatelů potřebného k zachycení pronásledovaného nekonečnou rychlostí na grafu G (když pronásledovatelé a pronásledovaní nejsou omezeni na pohyby pohyb po pohybu, ale mohou se pohybovat současně) je ekvivalentní zjištění šířky stromu graf G a vítěznou strategii pro pronásledované lze popsat pomocí skrytí v grafu G. Pokud je toto pronásledovatelé neviditelné, pak je problém ekvivalentní nalezení šířky cesty nebo oddělení vrcholů [3] . Zjištění počtu pronásledovatelů potřebného k zachycení jednoho neviditelného pronásledovatele v grafu G jedním tahem je ekvivalentní nalezení počtu nejméně dominantní množiny grafu G za předpokladu, že pronásledovatelé mohou být zpočátku kdekoli, kde chtějí.
Desková hra "Scotland Yard" je variantou problému pronásledování a úniků.
Složitost některých variant problémů pronásledování-vyhýbání se, konkrétně kolik pronásledovatelů je potřeba k vyčištění daného grafu a jak se daný počet pronásledovatelů musí pohybovat po grafu, aby jej vyčistili, buď s minimálním součtem jejich ujetých vzdáleností nebo s minimálním časem na dokončení hry, studovali Nimrod Megiddo, S. L. Hakimi, Michael R. Garay, David S. Johnson a Christos H. Papadimitriou a R. Bori, K. Tovey a S. Koenig [4] .
Stále větší pozornosti se dostává také řešení her pronásledování-vyhýbání se pro více hráčů . Viz články R. Vidala a kol. , [5] , Chang a Furukawa [6] , Espaniya, Kim a Sastri [7] a odkazy v těchto článcích. Marcos A. M. Vieira, Ramesh Govindan a Gaurav S. Sukatmi [8] navrhli algoritmus, který vypočítává strategii s minimální dobou provádění pro pronásledovatele k zachycení všech pronásledovatelů, když všichni hráči učiní optimální rozhodnutí na základě úplných znalostí. Tento algoritmus lze také použít v případech, kdy jsou pronásledovaní mnohem rychlejší než pronásledovatelé. Bohužel tento algoritmus neškáluje dále než jen malý počet robotů. K překonání tohoto problému Marcos A. M. Vieira, Ramesh Govindan a Gaurav S. Sukatmi vyvinuli a implementovali rozdělovací algoritmus, kde pronásledovatelé zachycují pronásledované tím, že hru rozloží na hry s jedním pronásledovaným a více pronásledovateli.
V nepřetržité formulaci her o pronásledování-vyhýbání se prostředí je modelováno geometricky, obvykle ve formě euklidovského letadla nebo jiné rozmanitosti . Varianty hry mohou omezovat ovladatelnost hráčů, jako jsou limity rychlosti nebo zrychlení. Lze použít i překážky.
Jednou z prvních aplikací problému pronásledování-úniku byly systémy řízení raket. Úkoly pro tyto systémy formuloval Rufus Isaacs z RAND Corporation [1] .