8 邻域中的最小点 link

Question

这是我的问题，我有一个矩阵中的点列表，我想 link 所有这些点并最小化这个覆盖。我在 8-neighborhood 工作，link 也一定是对的。

例如一种解法：

╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
║   ║ * ║*2 ║   ║   ║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ 5*║   ║   ║   ║   ║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║ * ║   ║   ║ 3*║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║ * ║   ║   ║ * ║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║   ║ * ║ * ║   ║ * ║   ║ * ║ * ║*4 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║ 1*║   ║   ║   ║   ║ 6*║   ║   ║   ║
╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝

另一个：

╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
║   ║   ║*2 ║   ║   ║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ 5*║ * ║   ║   ║   ║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║   ║ * ║   ║ 3*║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║   ║   ║ * ║   ║ * ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║   ║ * ║   ║   ║   ║ * ║ * ║ * ║*4 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║ 1*║   ║   ║   ║   ║ 6*║   ║   ║   ║
╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝

所以我搜索了一种算法来找到我的点集的这个最小覆盖。我在互联网上搜索但没有找到我需要的东西，但类似的问题如最小生成树、最小顶点覆盖...

一些想法将不胜感激

Answer 1

这是 Steiner tree problem 和 NP-hard。

在您的示例中，由于允许使用对角线，因此您似乎在这里得到了一个 8 邻域网格。在4邻域的情况下，有一个特殊版本叫做Rectilinear Steiner tree （仍然是 NP-hard）。

您的问题似乎是 Steiner tree in graphs 变体的示例。

Answer 2

直线斯坦纳算法不是您想要的；它主要取决于可用移动的正交性。

相反，我认为您需要 Bresenham 的直线算法（正如您已经说过的那样）来连接通过添加的基本属性 Steiner 节点找到的点：每个 Steiner 节点具有三个以 120 度角相交的边. The node is the Fermat point of a triangle with appropriately chosen vertices (such that those vertices form a minimal triangle in the Steiner tree).

在您的示例中，您的最小三角形是节点 2、3、5；费马点 A（四舍五入到格子）就在 5 的右边，如第二张图中所示。您连接的树是节点 2、3、5、A。

下一个包含新节点的"best"三角形是A, 3, 1。费马点B将与节点2在同一列，在节点3下方一行。连接的树是现在是 1、2、3、5、A、B。

扩展这个过程，你剩下的三角形将是3、B、6（加点C）和（我认为）C、6、4。然后会有少量的格子抖动来达到最终的结果（从树中删除 B 和 C）。这是你的第二个例子。请注意，原始连接 AB 和 B1 可以选择左侧一个单位的点；抖动需要让它们更接近节点 3，然后从树中移除 B。

╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗
║   ║   ║*2 ║   ║   ║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║ 5*║ A*║   ║   ║   ║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║   ║ * ║   ║ 3*║   ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║   ║ B ║ * ║ C ║ * ║   ║   ║   ║   ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║   ║ * ║   ║   ║   ║ D*║ * ║ * ║*4 ║
╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣
║   ║ 1*║   ║   ║   ║   ║ 6*║   ║   ║   ║
╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝

8 邻域中的最小点 link

Minimum point link in 8-neighborhood

algorithm

matrix

optimization

cover