论文标题
战舰的有效算法
Efficient Algorithms for Battleship
论文作者
论文摘要
我们考虑了一个受战舰游戏启发的算法问题。在我们研究的问题的变体中，有一艘独特的形状$ s \ subset z^2 $的船，该船已在晶格$ z^2 $中翻译。我们假设一名球员已经用第一杆击中了船，而目标是使用尽可能少的射击来降低船，即通过最大程度地减少错过的投篮次数。虽然玩家知道Shape $ s $，但尚不清楚$ S $的哪个位置。 鉴于形状$ s $的$ n $晶格点，在最坏情况下，任何算法都可以实现的最小遗漏数量称为Shape $ s $的战舰复杂性，并表示为$ c（s）$。我们证明了$ c（s）$的三个界限，每个范围都考虑了不同的形状。首先，我们有$ c（s）\ leq n-1 $用于任意形状，而无平行四边形形状的界限紧密。其次，我们提供了一种算法，该算法表明$ c（s）= o（\ log n）$如果$ s $是hv-convex polyomino。第三，我们提供了一种算法，该算法表明$ c（s）= o（\ log \ log n）$如果$ s $是数字凸集。通过新的离散版本的Blaschke-Lebesgue不平等现象与任何凸形体的宽度相关的blaschke-Lebesgue不平等，获得了最后的结果。
We consider an algorithmic problem inspired by the Battleship game. In the variant of the problem that we investigate, there is a unique ship of shape $S \subset Z^2$ which has been translated in the lattice $Z^2$. We assume that a player has already hit the ship with a first shot and the goal is to sink the ship using as few shots as possible, that is, by minimizing the number of missed shots. While the player knows the shape $S$, which position of $S$ has been hit is not known. Given a shape $S$ of $n$ lattice points, the minimum number of misses that can be achieved in the worst case by any algorithm is called the Battleship complexity of the shape $S$ and denoted $c(S)$. We prove three bounds on $c(S)$, each considering a different class of shapes. First, we have $c(S) \leq n-1$ for arbitrary shapes and the bound is tight for parallelogram-free shapes. Second, we provide an algorithm that shows that $c(S) = O(\log n)$ if $S$ is an HV-convex polyomino. Third, we provide an algorithm that shows that $c(S) = O(\log \log n)$ if $S$ is a digital convex set. This last result is obtained through a novel discrete version of the Blaschke-Lebesgue inequality relating the area and the width of any convex body.
