笼图的零可视警察强盗博弈和快速搜索
发布时间：2021-02-06 13:33
考虑到丰富的数学理论,图搜索问题的相关模型已被广泛应用于大量实际追逃问题。近年来,受查找计算机病毒、检索大型仓库货物以及移动机器人目标搜索等实际追逃问题的影响,图搜索中的零可视警察强盗博弈和快速搜索模型成为数学和计算机科学中的热门话题。相较于经典的警察强盗博弈模型,零可视警察强盗博弈模型更符合实际需求,在该模型中,强盗是不可见的,这为目标躲藏在“盲点”区域的搜索问题提供了有效解决方法;快速搜索模型中,搜索者只能沿可能包含入侵者的边移动,与边搜索模型相比,这减少了对边的重复搜索次数,极大地提高了搜索效率。为了更充分地利用零可视警察强盗博弈模型和快速搜索模型解决实际问题,需要在此两种模型下,研究更多不同结构的图,而笼图区域的零可视警察强盗博弈和快速搜索问题尚未被研究,本文针对笼图的零可视警察强盗博弈和笼图的快速搜索这两个问题分别进行研究;（1）笼图的零可视警察强盗博弈问题。考虑到经典的警察强盗博弈模型是完全信息博弈,并不适用于大量实际追逃问题,并且笼图的零可视警察强盗博弈未被研究。因此本文对笼图的零可视警察强盗博弈进行研究,首先提出笼图G3,g（3≤g≤12）、G4,g（3≤g≤8）的最小...
【文章来源】：浙江师范大学浙江省
【文章页数】：65 页
【学位级别】：硕士
【部分图文】：
图２．１哥尼斯堡七桥问题??假设是茼单无向图，其中心和分别表示图Ｇ的顶点集和边集，??
?２阁锼索的相义理论???■?ｍ＼?［ｉ｜５］??Ｈ——／！＝??｜ｒ??？＿?ａ??＾＾￣￣ｔ——ｌ??Ｈｈ??，图２．３迷宫与其对应的图??但是永远都不能将其捕获，但是两个幽灵就可以将其捕获。那么在这个矩形迷宮里，需??要的幽灵数就是两个。??从某种意义上说，鳖察强盗博弈模型是吃豆人的离散版，最小鳘察搜索数相当抓??住小精灵所需要的幽灵的最小数量。小精灵相当ｒ是强盗，而鳘察相当丨＇＿幽灵。这样就??将一个“吃豆人”游戏抽象为图搜索中的蹩察强盗博弈问题。??ＱｄｌｂｔＰｌ以及Ｎｍｖａｋｏｗｓｋｉ等ｍ最先提出的经典的蝥察强盗博弈是完全信息博弈，??搜索双方由对峙的瞥察玩家和强盗玩家ｔｌ成。蝥察玩家控制多个蝥察以单位速度从一个??顶点移动到另一个顶点去搜ｆ＃强盗，强盜玩家控制着一个强盗以单位速度去躲避蝥察的??追捕。瞥察和强盗分别在图上移动，瞀察先移动，然后两苒轮流移动，并Ｊ１每轮每万玩??家只能选择移动到其邻接顶点，并Ｊ１在移动过程中，双方完全知晓彼此的位罝１移动路??线等信息。如果经过有限轮次后，瞀察弓强盗移动到同一顶点，则称为鳘察获胜：如果??强盜可以一直躲避瞥察的追捕，则称强盗获胜。蝥察搜索策略即蹩察所移动的路线的集??合，强盗躲避策略即强盗为躲避搜索所移动的路线的集合。??下面通过一个简单ＩＸ有指导意义的例子来简单介绍鳖察强盗博弈模型。假设在一??个５罔上进行鳘察强盗博弈，将罔的每个顶点分别标记为１、２、３、４、５?（如图２．４）。??在顶点１上放罝一个蝥察。如果此时强盗也选择放在顶点则相当ｒ？自投罗网：如果??强盗选择顶点２或５?，那么他将在第一轮中被抓捕：如果强盗选择顶点３，则
?３笼围的零可视獠察强盗博弈???！Ｘ７Ｓ＼??，！３ａ?／Ｓ＾ＡｋＪ?ｒ，Ｘ?ｔＬ，Ｋ?／Ｓｖ－Ａ，Ｊ?广＼一??＾ｒ＼７＾＞〇?ｖ，ｊｆ＼＾?ＮｖＶ??聊聊聊■??（ａ）?ｉ—０?（ｂ）?ｉ＝?１?（ｃ）?＼—２?（ｄ）?ｉ＝３??山八厶Ｘ??Ｗ，、、义??ｖｉｉ＼－＾＼?，１＇?＾??ｖ?ｉ?ｆ??咖、ｚ??（ｅ）?ｉ＝４??图３．７搜索笼图ＧＭ过程示意圏??３．４．２总结与分析??在上述笼图实验中，根据第３Ｊ节给出的零可视蝥察搜索数，利用算法ＺＣＲＳＣ?（算??法〖）根据顶点关联的污染的边数放罝鳖察的个数，乂在搜索过程中遵循单调性完成在??整个笼图Ｅ域对Ｈ标的搜索。从图１７可见，经瞀察移动搜索后，图中的顶点皆为二角??形，边皆为虚线ｆ即顶点和边都被搜索过，实验表明算法Ｚ．ＣＲＳＣ可以有效完成对笼图??的搜索。??３．５本章小结??本章主要研究了笼图的零可视蝥察强盗博弈。??首先，通过研究笼图的性质给出了笼图１２）的零可视繁察搜索数的下??界：ｃ〇（Ｇ＼．？）》［１?／＇ｆｌｊ?－?１；??以及笼图８）的零可视鳘察捜索数的下界：。??其次，根据最小零可视鳖察搜索数的下界进一步给出笼图４?ｇ?＜?１２）、毛??沒＜?Ｓ）的最小单凋零可视鳖察搜索数。此外，还给出了笼图ａ；．．，｛３?ｄ?７）的单调零可??视蝥察搜索数的定理：ｒ＿｛ＧＭ）?＝?ｒ。??最后，在零可视彆察强盗博弈模型下提出了一种搜索笼图Ｓ?１２）、＜??２９??
【参考文献】：
期刊论文
[1]票贩子现象的原因和治理──基于警察与小偷博弈模型[J]. 张凌翼. 中南财经政法大学研究生学报. 2008(04)
本文编号：3020698
【文章来源】：浙江师范大学浙江省
【文章页数】：65 页
【学位级别】：硕士
【部分图文】：
图２．１哥尼斯堡七桥问题??假设是茼单无向图，其中心和分别表示图Ｇ的顶点集和边集，??
?２阁锼索的相义理论???■?ｍ＼?［ｉ｜５］??Ｈ——／！＝??｜ｒ??？＿?ａ??＾＾￣￣ｔ——ｌ??Ｈｈ??，图２．３迷宫与其对应的图??但是永远都不能将其捕获，但是两个幽灵就可以将其捕获。那么在这个矩形迷宮里，需??要的幽灵数就是两个。??从某种意义上说，鳖察强盗博弈模型是吃豆人的离散版，最小鳘察搜索数相当抓??住小精灵所需要的幽灵的最小数量。小精灵相当ｒ是强盗，而鳘察相当丨＇＿幽灵。这样就??将一个“吃豆人”游戏抽象为图搜索中的蹩察强盗博弈问题。??ＱｄｌｂｔＰｌ以及Ｎｍｖａｋｏｗｓｋｉ等ｍ最先提出的经典的蝥察强盗博弈是完全信息博弈，??搜索双方由对峙的瞥察玩家和强盗玩家ｔｌ成。蝥察玩家控制多个蝥察以单位速度从一个??顶点移动到另一个顶点去搜ｆ＃强盗，强盜玩家控制着一个强盗以单位速度去躲避蝥察的??追捕。瞥察和强盗分别在图上移动，瞀察先移动，然后两苒轮流移动，并Ｊ１每轮每万玩??家只能选择移动到其邻接顶点，并Ｊ１在移动过程中，双方完全知晓彼此的位罝１移动路??线等信息。如果经过有限轮次后，瞀察弓强盗移动到同一顶点，则称为鳘察获胜：如果??强盜可以一直躲避瞥察的追捕，则称强盗获胜。蝥察搜索策略即蹩察所移动的路线的集??合，强盗躲避策略即强盗为躲避搜索所移动的路线的集合。??下面通过一个简单ＩＸ有指导意义的例子来简单介绍鳖察强盗博弈模型。假设在一??个５罔上进行鳘察强盗博弈，将罔的每个顶点分别标记为１、２、３、４、５?（如图２．４）。??在顶点１上放罝一个蝥察。如果此时强盗也选择放在顶点则相当ｒ？自投罗网：如果??强盗选择顶点２或５?，那么他将在第一轮中被抓捕：如果强盗选择顶点３，则
?３笼围的零可视獠察强盗博弈???！Ｘ７Ｓ＼??，！３ａ?／Ｓ＾ＡｋＪ?ｒ，Ｘ?ｔＬ，Ｋ?／Ｓｖ－Ａ，Ｊ?广＼一??＾ｒ＼７＾＞〇?ｖ，ｊｆ＼＾?ＮｖＶ??聊聊聊■??（ａ）?ｉ—０?（ｂ）?ｉ＝?１?（ｃ）?＼—２?（ｄ）?ｉ＝３??山八厶Ｘ??Ｗ，、、义??ｖｉｉ＼－＾＼?，１＇?＾??ｖ?ｉ?ｆ??咖、ｚ??（ｅ）?ｉ＝４??图３．７搜索笼图ＧＭ过程示意圏??３．４．２总结与分析??在上述笼图实验中，根据第３Ｊ节给出的零可视蝥察搜索数，利用算法ＺＣＲＳＣ?（算??法〖）根据顶点关联的污染的边数放罝鳖察的个数，乂在搜索过程中遵循单调性完成在??整个笼图Ｅ域对Ｈ标的搜索。从图１７可见，经瞀察移动搜索后，图中的顶点皆为二角??形，边皆为虚线ｆ即顶点和边都被搜索过，实验表明算法Ｚ．ＣＲＳＣ可以有效完成对笼图??的搜索。??３．５本章小结??本章主要研究了笼图的零可视蝥察强盗博弈。??首先，通过研究笼图的性质给出了笼图１２）的零可视繁察搜索数的下??界：ｃ〇（Ｇ＼．？）》［１?／＇ｆｌｊ?－?１；??以及笼图８）的零可视鳘察捜索数的下界：。??其次，根据最小零可视鳖察搜索数的下界进一步给出笼图４?ｇ?＜?１２）、毛??沒＜?Ｓ）的最小单凋零可视鳖察搜索数。此外，还给出了笼图ａ；．．，｛３?ｄ?７）的单调零可??视蝥察搜索数的定理：ｒ＿｛ＧＭ）?＝?ｒ。??最后，在零可视彆察强盗博弈模型下提出了一种搜索笼图Ｓ?１２）、＜??２９??
【参考文献】：
期刊论文
[1]票贩子现象的原因和治理──基于警察与小偷博弈模型[J]. 张凌翼. 中南财经政法大学研究生学报. 2008(04)
本文编号：3020698
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3020698.html
