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

来源：计算机工程与科学杂志2021年第9期北京时间：

作者：王佳慧, 钟发荣

单位：（浙江师范大学数学与计算机科学学院，浙江 金华 321004）

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

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

基金资助：浙江省公益技术研究社会发展项目（2015C33085）