论文标题
树木和完整网络的最佳巡逻策略
Optimal Patrolling Strategies for Trees and Complete Networks
论文作者
论文摘要
我们为网络上玩的连续巡逻游戏提供了解决方案。在这个零和游戏中，攻击者选择了一个时间和地点来攻击网络的固定时间。巡逻者巡逻网络的目的是以最大的概率拦截攻击。我们的主要结果是证明了最近对树木最佳巡逻策略的猜想。猜想断言，一种称为电子胶卷策略的特定巡逻策略对于所有树网络都是最佳的。在有限类别的特殊情况下，以前已知该猜想是正确的。电子胶卷策略具有直接计算和实施的优势。我们通过为攻击者展示$ \ varepsilon $最佳策略来证明猜想，该策略为游戏的价值提供了上限，该策略是任意接近E-Patrolling策略所提供的下限。在某些情况下，我们还为完整的网络解决了巡逻游戏。
We present solutions to a continuous patrolling game played on network. In this zero-sum game, an Attacker chooses a time and place to attack a network for a fixed amount of time. A Patroller patrols the network with the aim of intercepting the attack with maximum probability. Our main result is the proof of a recent conjecture on the optimal patrolling strategy for trees. The conjecture asserts that a particular patrolling strategy called the E-patrolling strategy is optimal for all tree networks. The conjecture was previously known to be true in a limited class of special cases. The E-patrolling strategy has the advantage of being straightforward to calculate and implement. We prove the conjecture by presenting $\varepsilon$-optimal strategies for the Attacker which provide upper bounds for the value of the game that come arbitrarily close to the lower bound provided by the E-patrolling strategy. We also solve the patrolling game in some cases for complete networks.
