The minimum firing time of the generalized firing squad synchronization problem for squares
The minimum firing time of the generalized firing squad synchronization problem for squares
复制标题
方格广义行刑队同步问题的最小开火时间
DOI：
10.1016/j.tcs.2014.06.016
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Kojiro Kobayashi
中科院分区：
文献类型：
--
作者：
Kojiro Kobayashi
对于几乎所有的基本几何图形，如线，环，正方形，矩形和立方体的射击队同步问题的变化，最小时间的解决方案是已知的。然而，在2012年，Umeo和Kubo介绍了这种类型的一个非常简单的变体，并指出它的最小时间解是未知的。在该变体中，问题实例是n列n行的正方形阵列，并且一般的位置是任意的。对于这个变分，他们构造了一个解，对于一般的任何位置，它在时间2 n − 2处激发，并写道，不知道这个解是否是最小时间的。我们确定了这个变化的最小点火时间的精确值。对于某些问题，这个值小于2 n − 2，因此2 n − 2时间解不是最小时间解。我们的结果并没有解决变分最小时间解的存在性或不存在性问题。然而，结果给出了一个必要条件，了解是最小时间。
For almost all variations of the firing squad synchronization problem for elementary geometric figures such as lines, rings, squares, rectangles, and cubes, minimal-time solutions are known. However, in 2012 Umeo and Kubo introduced a very simple variation of this type and pointed out that its minimal-time solutions are unknown. In that variation, a problem instance is a square array of n columns and n rows and the position of the general is arbitrary. For this variation they constructed a solution that fires at time 2 n− 2 for any position of the general and wrote that it is not known whether this solution is minimal-time or not. We determine the exact value of the minimum firing time of this variation. For some problem instances this value is smaller than 2 n− 2 and hence the 2 n− 2 time solution is not minimal-time. Our result does not solve the problem of existence or non-existence of minimal-time solutions of the variation. However the result gives one necessary condition for solutions to be minimal-time.