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