三角多面体和完全分割图上的零可视度警察和小偷博弈

论文摘要

图搜索亦被称为追逃问题,是指一组搜索者在图上尽力抓捕入侵者,可以分为两类:搜索博弈、警察和小偷博弈。最初的警察和小偷博弈是一个完美信息的双人博弈。在现实生活中,警察不可能随时都掌握小偷的下落。因此,研究者提出了一些更贴近现实生活的模型。零可视度警察和小偷博弈作为一个变体,其与最初的警察和小偷博弈有一个明显的区别:小偷是不可见的。当且仅当有警察和小偷占据同一个顶点时,警察才能看见小偷。人们感兴趣的问题是求解小偷被警察抓获需要的最小警察数,而三角多面体和完全分割图的单调零可视度最小警察数及其相关搜索算法尚未被解决。本文针对这些问题展开研究,主要研究内容如下:（一）三角多面体上的零可视度警察和小偷博弈问题。首先提出连通图的一个单调零可视度最小警察数下界;其次提出构造三角多面体和基图的定义;接着应用归纳法证得构造三角多面体与其基图的单调零可视度最小警察数相等;然后提出一个计算凸三角多面体的单调零可视度最优警察策略的线性时间算法。（二）完全分割图上的零可视度警察和小偷博弈问题。首先提出triangle-free图的一个单调零可视度最小警察数下界;其次研究了圈、完全图和完全二部图的单调零可视度最小警察数;在此基础上,根据系数m、n分情形研究完全分割图Sm,n,得出其单调零可视度最小警察数mc0（Sm,n）=[m+1/2];然后提出一个计算完全分割图的单调零可视度最优警察策略的线性时间算法。

论文目录

文章来源

类型: 硕士论文

作者: 韩小东

导师: 钟发荣

关键词: 图搜索,警察和小偷博弈,最小警察数,三角多面体,完全分割图

来源: 浙江师范大学

年度: 2019

分类: 基础科学

专业: 数学,数学

单位: 浙江师范大学

分类号: O157.5;O225

DOI: 10.27464/d.cnki.gzsfu.2019.000840

总页数: 51

文件大小: 2563k

下载量: 2

相关论文文献

• [1].营销的可视度[J]. 销售与市场(管理版) 2013(02)
• [2].透明黏土可视度及物理力学特性研究[J]. 岩土工程学报 2019(S2)
• [3].增强可视度,提升实验教学的效率[J]. 中学教学参考 2019(14)
• [4].基于道路可视度的高层交通噪声影响因素初探[J]. 电声技术 2019(01)
• [5].用于浅水养殖的低可视度水下摄像系统研究[J]. 渔业现代化 2020(05)
• [6].基于实时优化单光子干涉可视度的相位编码量子密钥分发[J]. 量子光学学报 2016(03)
• [7].镜面反射综合孔径成像方法研究[J]. 微波学报 2020(03)
• [8].饮料陈列对销量的影响[J]. 现代商业 2015(34)
• [9].基于信息可视度的供应链治理机制与供应链柔性相互作用研究[J]. 珞珈管理评论 2016(01)
• [10].叠书图的零可视度警察和强盗博弈算法[J]. 信息与电脑(理论版) 2018(20)
• [11].综合孔径干涉辐射计中模数转换信噪比约束分析方法[J]. 探测与控制学报 2020(05)
• [12].无法从记忆中撤走那同桌的礼[J]. 课堂内外(初中版) 2016(Z1)
• [13].水体景观可视度对住宅地价溢出效应研究——以深圳市为例[J]. 北京大学学报(自然科学版) 2018(01)
• [14].有效提高故障指示仪的可视度[J]. 农村电气化 2013(04)
• [15].情感的空间[J]. 城市环境设计 2013(09)
• [16].基于三维累积可视的展陈空间观看行为研究[J]. 南方建筑 2020(01)
• [17].再见“雄猫”——实拍F-14细节[J]. 航空世界 2016(06)
• [18].奥运特警便装里的乾坤[J]. 青年科学 2008(10)
• [19].谈多媒体在物理教学中的妙用[J]. 考试周刊 2014(91)
• [20].一种扩大8mm波段综合孔径辐射计成像视场的方法[J]. 红外与毫米波学报 2013(01)
• [21].微课在高职教法课教学实践中的应用[J]. 辽宁师专学报(自然科学版) 2016(02)
• [22].路的味道[J]. 时代青年(悦读) 2016(04)
• [23].低可视度龙纹涂装歼-11B战斗机[J]. 模型世界 2013(08)
• [24].办公室开放布“局”不仅是为了时尚[J]. 现代班组 2010(03)
• [25].多媒体在初中物理实验课中的应用[J]. 新课程(上) 2011(08)
• [26].基于红外图像和普通图像对比的高速公路可视度分析[J]. 交通运输系统工程与信息 2016(04)
• [27].运营商正在制定SIEM标准[J]. 通信世界 2013(26)
• [28].Porsche Informatik选择Dynatrace驱动软件创新进程[J]. 计算机与网络 2020(03)
• [29].陕西黄龙山自然保护区冬季褐马鸡沙浴地选择[J]. 林业科学 2011(11)
• [30].基于燃烧热计算模型的火灾烟气分布数值模拟[J]. 中国胶粘剂 2018(12)

标签：图搜索论文;  警察和小偷博弈论文;  最小警察数论文;  三角多面体论文;  完全分割图论文;