Diplomová práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Složitost řešení patrolovacích her na orientovaných grafech

Computational Complexity of Patrolling Games on Oriented Graphs

Bc. Matúš Abaffy, učo 359420
Anotace

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 …více

Abstract

Patrolling games are two-player games played on graphs. One player, the attacker, aims at attacking some of the nodes, while the other player, the defender, tries to protect those nodes by visiting them. The defender has to randomize as her strategy and position are both known to the attacker. We present a quadratically exponential algorithm which computes an ε-optimal defender’s strategy for a given …více

Klíčová slova
patrolling games game theory complexity algorithm optimal strategy ε-optimality oriented graph multiple robots characteristic Stackelberg model
Zadání práce
Cílem práce je rozšířit výsledky diplomové práce Michala Abaffyho, která se zabývá řešením patrolovacích her na grafech. Práce Michala Abaffyho uvažuje pouze jednoduchý model patrolovacích her s jedním útočníkem a jedním obráncem. Navíc prezentovaný algoritmus pro řešení těchto her má dvojitě exponenciální časovou složitost. Práce by se měla zaměřit na - zobecnění modelu patrolovacích her (více útočníků, více obránců apod.) s ohledem na stávající literaturu o patrolovacích hrách, - zefektivnění algoritmu pro řešení (zobecněných) patrolovacích her, v ideálním případě by měl být formulován algoritmus pro řešení těchto her v exponenciálním čase.
Administrativní informace
Práce zkontrolována:
29. 1. 2015 18:31, doc. RNDr. Tomáš Brázdil, Ph.D., MBA, učo 4074
Plný text práce
590,3 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
11. 2. 2015
Práce byla úspěšně obhájena

Vedoucí

doc. RNDr. Tomáš Brázdil, Ph.D., MBA, učo 4074
ITI FI MU

Oponent

doc. RNDr. Vojtěch Řehák, Ph.D., učo 3721
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.