考虑到丰富的数学理论,图搜索问题的相关模型已被广泛应用于大量实际追逃问题。近年来,受查找计算机病毒、检索大型仓库货物以及移动机器人目标搜索等实际追逃问题的影响,图搜索中的零可视警察强盗博弈和快速搜索模型成为数学和计算机科学中的热门话题。相较于经典的警察强盗博弈模型,零可视警察强盗博弈模型更符合实际需求,在该模型中,强盗是不可见的,这为目标躲藏在“盲点”区域的搜索问题提供了有效解决方法;快速搜索模型中,搜索者只能沿可能包含入侵者的边移动,与边搜索模型相比,这减少了对边的重复搜索次数,极大地提高了搜索效率。为了更充分地利用零可视警察强盗博弈模型和快速搜索模型解决实际问题,需要在此两种模型下,研究更多不同结构的图,而笼图区域的零可视警察强盗博弈和快速搜索问题尚未被研究,本文针对笼图的零可视警察强盗博弈和笼图的快速搜索这两个问题分别进行研究;(1)笼图的零可视警察强盗博弈问题。考虑到经典的警察强盗博弈模型是完全信息博弈,并不适用于大量实际追逃问题,并且笼图的零可视警察强盗博弈未被研究。因此本文对笼图的零可视警察强盗博弈进行研究,首先提出笼图G3,g(3≤g≤12)、G4,g(3≤g≤8)的最小零可视警察搜索数下界定理:其次,利用笼图的最小零可视警察搜索数下界定理,并在零可视警察强盗博弈模型下设计合适的搜索策略,确定笼图的最小单调零可视警察搜索数;最后在零可视警察强盗博弈模型下,提出一种搜索笼图G3,g(3≤g≤12)、G4,g(3≤g≤8)的搜索算法,并将此算法在例图上进行实验验证。(2)笼图的快速搜索问题。与边搜索模型相比,快速搜索模型中减少了对边的重复搜索次数,提高了搜索效率,并且笼图的快速搜索问题尚未被研究,因此本文对笼图的快速搜索问题进行研究,首先提出笼图G3,g(3≤g≤12)、G4,g(3≤g≤8)的快速搜索数的相关下界定理;其次,利用笼图的快速搜索数的下界定理,并在快速搜索模型下设计合适的搜索策略,确定笼图的快速搜索数;最后在快速搜索模型下,提出一种搜索笼图G3,g(3≤g≤12)、G4,g(3≤g≤8)的搜索算法,并将此算法在例图上进行实验验证。