论文标题
寻找不确定形状的战舰
Finding a Battleship of Uncertain Shape
论文作者
论文摘要
在战舰游戏的驱动下，我们考虑了在大型比赛中有效击中不确定形状的船的问题。正式地，我们修复了\ {1,2 \} $中的尺寸$ d \。船是$ \ mathbb {z}^d $的子集。给定了一个家庭$ f $的船只，我们说，如果它与$ f $的每艘船相交的每艘船的每艘翻译（由$ \ mathbb {z}^d $），则无限子集$ x \ subset $ x \ subset $ x \ subset $ x \ subset $ x \ subset $ x \ subset $ x \ subset $ x \ subset $ x \ subset \ mathbb {z}^d $ pureces $ f $）。在这项工作中，我们研究了这种穿孔子集的最低（渐近）密度$π（f）$。据我们所知，此问题以前仅在特殊情况下仅在$ | f | = 1 $（一艘船）中进行了研究。作为我们的主要贡献，当$ f $由2艘2艘尺寸2的船只组成时，我们提供了一个$π（f）$的公式，并且在其他几种情况下，我们确定了最艰难的家庭。我们还实施了一种算法，以在1D中找到$π（f）$。
Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension $d\in\{1,2\}$. A ship is a subset of $\mathbb{Z}^d$. Given a family $F$ of ships, we say that an infinite subset $X\subset\mathbb{Z}^d$ of the cells pierces $F$, if it intersects each translate of each ship in $F$ (by a vector in $\mathbb{Z}^d$). In this work, we study the lowest possible (asymptotic) density $π(F)$ of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case $|F|=1$ (a single ship). As our main contribution, we present a formula for $π(F)$ when $F$ consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding $π(F)$ in 1D.
