论文标题
任何高素质晶格的最小链路覆盖道
Minimum-Link Covering Trails for any Hypercubic Lattice
论文作者
论文摘要
1994年，Kranakis等。发表了一个猜想，内容涉及每条直线覆盖道路的最小链接长度，用于$ k $二维网格$ p（n，k）：= \ {0,1，\ dots，n-1 \} \} \} \ times \ times \ {0,1，\ {0,1，\ dots，\ dots，n-d dots，n-1 \} \} \ cdots \ cdots \ cdots \ cdots \ n $ n $ n。在本文中，我们考虑了一般的NP完整，线条问题，其中不需要边缘与轴平行，这表明Kranakis等人的原始定理1。当忽略上述约束时，不再存在。此外，对于任何大于两个$ n $的$ n $，随着$ k $接近无穷大，任何最小（非线性）多边形链的链接长度均不超过kranakis的肯定价值$ \ frac {k} {k-frac {k-1} {k-1} {k-1} \ cdot n^{k-1} {k-1}+e（k-1}+o（n^k-n^^k-k-2 $ a）对于较低的术语（例如，如果我们选择$ n = 3 $，并假设$ c <1.5 $，从足够大的$ k $开始，则不可能访问$ p（n，k）$的所有节点，并具有链接的$ \ frac {k} {k-1} {k-1} {k-1} {k-cdot n^{k-cdot n^{k-1} $ c \ c \ cdoot node。
In 1994, Kranakis et al. published a conjecture about the minimum link-length of every rectilinear covering path for the $k$-dimensional grid $P(n,k) := \{0,1, \dots, n-1\} \times \{0,1, \dots, n-1\} \times \cdots \times \{0,1, \dots, n-1\}$. In this paper, we consider the general, NP-complete, Line-Cover problem, where the edges are not required to be axis-parallel, showing that the original Theorem 1 by Kranakis et al. no longer holds when the aforementioned constraint is disregarded. Furthermore, for any $n$ greater than two, as $k$ approaches infinity, the link-length of any minimal (non-rectilinear) polygonal chain does not exceed Kranakis' conjectured value of $\frac{k}{k-1} \cdot n^{k-1}+O(n^{k-2})$ only if we introduce a multiplicative constant $c \geq 1.5$ for the lower order terms (e.g., if we select $n=3$ and assume that $c<1.5$, starting from a sufficiently large $k$, it is not possible to visit all the nodes of $P(n,k)$ with a trail of link-length $\frac{k}{k-1} \cdot n^{k-1}+c \cdot n^{k-2}$).
