Patrolovacie hry sú hry dvoch hráčov hrané na grafoch. Jeden
hráč, útočník, má za cieľ zaútočiť na niektoré uzly grafu,
zatiaľ čo druhý hráč, obranca, sa snaží ochrániť tieto uzly
svojou návštevou. Obranca musí "randomizovať", pretože jeho
stratégia i pozícia sú útočníkovi známe.
My prezentujeme kvadraticky exponenciálny algoritmus, ktorý
počíta ε-optimálnu stratégiu pre obrancu pre danú patrolovaciu
hru a danú presnosť ε. Ďalej rozšírime model patrolovacích hier
tým, že umožníme viacero patrolovacích robotov. Prezentujeme
algoritmus, ktorý vypočíta ε-optimálnu stratégiu v dvojito
exponenciálnom čase voči počtu robotov.