王佳慧,钟发荣

(浙江师范大学数学与计算机科学学院，浙江 金华 321004)

1 引言

图搜索[1,2]是数学、计算机等领域热门的话题，它为现实生活中的很多问题提供了数学模型。在图搜索中有2类玩家：搜索者和入侵者。根据玩家占据的图中位置、移动速度和可见性等因素可将图搜索分为边搜索、点搜索、混合搜索和快速搜索等[3,4]。警察与强盗博弈就是图搜索的一种，研究的主要问题是确定能成功捕获强盗的最少警察数。该问题最早于1978年由Quilliot[5]提出，后被Nowakowski和Winkler单独研究[6]。上述研究只分析了1个警察就可完成搜索的情况；之后又有学者对有多个警察的情况展开了研究[7 - 9]。Bonato等[10]总结了传统博弈模型下有关最少警察数的大量结论。最新的研究结果可查看文献[11,12]。

零可视警察与强盗博弈是传统博弈模型的一种变形，与传统博弈模型唯一的区别是强盗不可见。通常考虑在一个连通图G中的零可视警察与强盗博弈，有2类玩家：1个强盗，多个警察。零可视警察与强盗博弈按照轮次进行。首轮，警察先选定初始顶点位置，之后强盗选择初始顶点位置。每一轮按照先警察后强盗的顺序交替行动，玩家每次只可以移动到邻接顶点或者停留在原顶点。整个博弈过程中，强盗在任一时刻都知道警察的位置，而警察不知道强盗位置。若在有限轮数内，警察与强盗在同一顶点，强盗被捕获。我们把在零可视警察与强盗博弈中能成功捕获强盗的最少警察数称为最优搜索数，用c0(G)表示，且在最优搜索数下的策略称为最优搜索策略。……