[论文阅读报告] On the Fast Searching Problem, AAIM '08
本文介绍了一种新的博弈问题- “Fast Searching”作为 Edge Searching的一种变体。研究了该问题在树上和二分图上的性质，
并给出了该博弈在树上的一个线性时间算法以及一个general cost function用来衡量search strategies在Fast Searching和Edge Searching问题上优劣。
Edge Searching(Basic Problem)
给定图$G=(V,E)$，其中$G$是简单联通图。假设一开始每条边都是被污染的，我们的目标是清理整个图，清理的动作如下：先选取一些点，在这些点上放$k$个searchers，允许一个点上放多个searchers。接下来的每一步，我们可以选择将一个searcher从一个点移动到任意一个点(jump)，或者让一个searcher从当前点沿着边移动到相邻点(slide)。一个seacher沿着边$e=uv$从$u$移动到$v$, 如果满足：(1) 有另一个seacher在$u$ 或者 (2) 与u相连的所有边都是clean的了，我们说$e$是clean。一个seacher在$v$，我们说$v$ 是 guarded。如果一条路径不包含不包含 guarded vertice，那么称这条路径是 unguarded path。在一条unguared path上，显然，如果有一条干净边的端点以及一条污染边的端点，那么这条干净边就会被污染。
在这样的定义下，求清洁整张图的最小seacher个数。
如果一个策略能在博弈的过程中保证已经被清洁的边保持干净，那么我们称这个策略就是是单调的。类似的，如果一个策略能在博弈的过程中保证被清洁的边导出一个联通子图，我们称这个决策是联通的。
Fast Searching(Main problem)
基本的定义与上面保持一致，同时要求每条边只经过一次且只能使用slide操作，另外要求策略单调。求在满足上述策略的前提下最小的searcher数量，记为$S_f(G)$。