以最短距离覆盖圆中所有点的最佳算法

Question

找到覆盖圆中最小距离的所有点的路径的最佳算法。从（0,0）开始，不需要返回（0,0），不像TSP

Answer 1

您可以使用动态编程。它使用所有组合来检查所有AZ距离。然后你可以检查最短的AZ路线。我在gebweb tsp solver的javascript中找到了一个工作示例。

Answer 2

如果不需要返回，那么它不是一个循环/循环，而是一条路径。

通过图中所有顶点的路径称为哈密尔顿路径，您所描述的问题是“最小权重哈密尔顿路径”，它与TSP一样硬。所以你不会找到比任何可用的TSP算法更好的算法（但你可以使用已知的TSP算法进行小的调整来解决这个问题，例如动态规划和分支和界限）。

Answer 3

我想你的意思是遍历一个圆内的所有点（夫妻x，y），并可以选择包含或排除圆（等高线）。我在这里回顾这些定义。 CIRCLE：与点C（中心）的距离为R> 0的平面上的点。DISK：与中心的距离为< = R> 0的平面的点。 从这种意义上讲，您希望移动所有点的DISK。

有很多方法可以“触摸”一个圆圈内的所有点（不是圆的所有点，这是另一个问题）。我认为“最好”意味着：不要重复一个观点并且走最短的路线。

如果这是问题，我可以建议启发式算法。