关键词: 警察与强盗, 三维网格图, 最优搜索数, 划分, 单调性

Abstract: Cops and robber game is a graph searching problem. The goal is to determine the minimum cop number needed to capture the robber. The robber is invisible in the zero-visibility cops and robber searching model: the cops have no information about the location of the robber at any time. This problem can be abstracted into a vertex cleaning model. By studying the properties of the three-dimensional grid, the vertex set of the three-dimensional grid can be divided into two subsets, and the relationship between the smaller subset and the boundary is deduced. Then, the results in the partition can be applied to prove the lower bound of the minimum cop number, and a monotonic search strategy is constructed to determine the upper bound. Finally, a zero-visibility cops and robber game algorithm on the three-dimensional grid is proposed. 

Key words: cops and robber, three-dimensional grid, optimal search number, partition, monotonicity