3

在二维空间中给出了一组点。所有点的 X 坐标都是唯一的。

这些点必须由斜率在 -1 到 +1 之间的线连接。现在，如果两条或更多这样的线相互连接，如果整条线没有“转身”，它将被计为一条线。

连接 (0,0) (1,1) 和 (0,2) 的线在 (1,1) 处“转身”。在这种情况下，连接线 (0,0) & (1,1) 和 (1) ,1) & (0,2) 是两条独立的行，不能算作一条。

如何确定此类“整体”行的全局最小数量（或至少近似解决方案）？它是一些已知的算法吗？

所有最终数量的“整体”线不需要相互接触或相交。

例如，如果我有点 {(1,1)(3,3)(5,5)} 答案是 1

如果我有点 {(1,1)(2,5)(3,3)(4,6)(5,1)} 答案是 2。一条连接线 (2,5)&(4,6)和其他加入其他点。

谢谢。

编辑：关于“周转”。

“整体线”由斜率在-1到+1之间的线段组成。每条这样的“整体线”都必须使得不存在将“整体线”切割到多个位置的线 x=const。

目标是找到这样的“整体线”的最小数量。

4

2 回答 2

1

让我们将给定的点集视为有向图，其中点是顶点，并且两点之间有一条边，如果它们可以与斜率在 -1 和 1 之间的线段连接。为了解决没有转弯的问题，每个边缘都将朝上（这将限制向下移动，从而导致转弯）。很明显，符合您条件的一条线对应于该图中的一条路径。

所以有了这样的图表，你的问题就会变成一个著名的问题。任务是用最少的方式覆盖一个有向无环图。你可以通过互联网找到很多关于这个主题的材料，例如看看这个：

编辑： 最初我错误地认为转弯条件，我正在考虑y=const线路。实际上，边缘必须向右 (x1 < x2) 或向左 (x1 > x2)。

于 2013-10-25T17:49:06.830 回答
0

可以产生的可能性有很多，不可能全部测试！我首先想到的是遗传算法。

不知道如何实现，但我认为它可能很方便。

于 2013-10-24T22:26:47.620 回答