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

摘要：

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

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

所属期刊栏目：43

分类号：TP18(自动化基础理论)

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

在线出版日期：2021-09-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1600-1607