三维网格图的零可视警察与强盗博弈算法  

A zero-visibility cops and robber game algorithm in the three-dimensional grid

作　　者：王佳慧 钟发荣 WANG Jia-hui;ZHONG Fa-rong(School of Mathematics and Computer Science,Zhejiang Normal University,Jinhua 321004,China)

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江金华321004

出　　处：《计算机工程与科学》2021年第9期1600-1607,共8页Computer Engineering & Science

基　　金：浙江省公益技术研究社会发展项目(2015C33085)。

摘　　要：警察与强盗博弈是一个图搜索问题,解决该问题的关键是确定能成功捕获强盗的最少警察数。在零可视警察与强盗博弈中强盗不可见:任意时刻警察都不知道强盗所在位置。通过建立顶点清理模型对三维网格图的性质进行分析,将三维网格图的顶点集划分成2个子集,导出划分中较小子集与边界的关系,并利用划分中的结论,给出三维网格图中最少警察数的下界。结合图搜索的单调性原则,给出一种可行的单调性搜索策略,确定三维网格图中最少警察数的上界。最后提出一种在三维网格图中最少警察数范围内可行的搜索算法。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.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]