How Many Lions Are Needed to Clear a Grid?

Algorithms

Florian Berger¹  Alexander Gilbers²  Ansgar Grüne² 

[1] Institute of Computer Science, University of Bonn, 53117 Bonn, Germany;

关键词: lion and man;    safe path planning;    avoidance number;    pursuit games;    graph separator;    graph search;    isoperimetric inequality;   

DOI  :  10.3390/a2031069

来源: mdpi

【 摘 要 】

We consider a pursuit-evasion problem where some lions have the task to clear a grid graph whose nodes are initially contaminated. The contamination spreads one step per time unit in each direction not blocked by a lion. A vertex is cleared from its contamination whenever a lion moves to it. Brass et al. [5] showed that -grid. Furthermore, we analyze a problem variant where the lions are also allowed to jump from grid vertices to non-adjacent grid vertices.

【 授权许可】

CC BY   
© 2009 by the authors; licensee Molecular Diversity Preservation International, Basel, Switzerland.