algorithm - 将点分成最大距离的集合

Question

我有一个 GPS 点列表...但我所要求的也适用于任何 X、Y 坐标。

在我的用例中，我想在集合中分配点。每个点只能属于一个集合，每个集合都有一个条件，即集合中任何两个点之间的距离不大于某个常数......这意味着，集合中的所有点都适合一个特定直径的圆。

对于点列表，我想找到最佳(或至少一些)排列，其中集合数量最少。

会有只有一个点的集合，因为周围的其他点已经在不同的集合中，或者仅仅是因为周围没有点(它们之间的距离大于集合的条件)......我想要的avoid 是低效的集合赋值，例如我没有找到理想的 2 组，每组有 30 分，而是找到 5 组，一组有 1 分，第二组有 40 分，等等......

我所能做的只是一个蛮力解决方案，计算所有距离，构建所有可能的集合排列，按集合数量对它们进行排序，然后选择集合数量最少的一个。

有没有更好的方法？

Answer 1

这里的问题是 NP 完全问题。您尝试解决的是最大团问题与集合覆盖问题的结合。

您的问题可以表示为图 G=(V,E)，其中顶点是您的坐标，边是距离上的连接。该图可以在 O(n^2) 时间内制作。然后过滤掉所有距离大于常数的边，给出图形 G'。

对于剩余的图 G'，您想要找到所有派系(有效解决最大派系问题)。团是一组完全连接的顶点。将此派系列表命名为 S。

现在找到覆盖所有顶点 V 的 S 的最小元素集是集覆盖问题。

集合覆盖问题和最大团都是 NP 完全问题。因此，找到最佳解决方案将花费指数时间。您可以查看这两个问题的近似算法。