>>> Complexity Seminar のお知らせ <<<

　日時：４月２５日（木），３時〜５時
　場所：東京工業大学 本館 H122 教室

　題名: grid 上の pursuit-evasion problem に関する survey

　発表:   田中 圭介

　概要:   

　以下のような cop と robber のゲームは, pursuit-evasion problem 
と呼ばれています.
  G を finite connected graph とします. まず, 複数の cop が G のある頂点に
配置されます. 次に, robber も G の ある頂点に配置されます. その後, robber 
と複数の cop が, 互いの strategy によって, 交互に (あるいは同時に) G の辺
にそって動きます (この動きは, 辺の上をトコトコ歩く感じで, 頂点から頂点へ飛
び移るのではありません). cop の一人が robber と同じ頂点を占めれば cop の勝
ちとなり, そうでなければ robber の 勝ちとなります.
  この問題は,
 a) G の形 (grid や tree など),
 b) cop の数,
 c) 相手の動きがわかる場合とわからない場合,
 d) cop と robber の動く速さ,
などによっていろいろなバリエーションがあります. また, この問題の応用として
は, エージェントを使ったソフトウェアやなども考えられます. 本発表では, 特に 
G が grid であるときの研究に関して survey を行います.