给定一组二维点（数量较少）和一个最大距离，找到最小簇的数量，其中每个簇内部的所有点之间的距离都小于或等于最大距离。簇的中心应该是这些点之一。此外，给出每个簇内部的点数。
这似乎类似于k-means等算法，但有了最大距离的限制。我没有看到比测试所有可能性（最大簇数为点数）更好的解决方案。是否有更好的解决方案？
这似乎类似于k-means等算法，但有了最大距离的限制。我没有看到比测试所有可能性（最大簇数为点数）更好的解决方案。是否有更好的解决方案？
在给定一个二维点集和最大距离的情况下，找到以该点集中某个点为中心、距离小于等于最大距离的最小簇。
3
- XogoX
3
3对我来说，这更像是集合覆盖问题而不是聚类。 - Has QUIT--Anony-Mousse
所以你有一组点，你想在某些点周围画直径为D的圆，使得所有点都在圆内，并且你想找到使用最少数量圆的解决方案？ - m69 ''snarky and unwelcoming''
确切地说，在每个磁盘中，每个点之间的距离必须至少为D（如果使用直径而不是半径，则可以实现此目标）。 - XogoX
2个回答
1
正如Anony-Mousse所说，你的问题似乎与set cover problem有关。使用维基百科页面上相同的符号和术语，宇宙
现在，我所做的是将你的问题简化为集合覆盖问题。这不是我们想要执行缩减的方向，以展示你的问题可能很“困难”。为了实现这一点，需要证明集合覆盖问题的每个实例都可以重新表述为你的问题的一个实例。
然而，你说你有一个相当小的点集。您可以将集合
U是你的点集，而集合S包含|U|个集合，每个点u在U中对应一个这样的集合，其中包含所有在以u为圆心半径等于你的最大距离的圆内的点。因此，你的问题是找到S中集合的最小数量（相当于找到应该成为聚类中心的点），使得这些集合的并集为U。现在，我所做的是将你的问题简化为集合覆盖问题。这不是我们想要执行缩减的方向，以展示你的问题可能很“困难”。为了实现这一点，需要证明集合覆盖问题的每个实例都可以重新表述为你的问题的一个实例。
然而，你说你有一个相当小的点集。您可以将集合
S 定义为上述内容，然后进行蛮力计算（即尝试 S 的所有可能子集，并取其中具有最小集合数量的子集，导致指数级复杂度与|S|的大小有关）。关于这种方法，实际上您希望在 S 中有相当少的集合，点的数量并不那么重要。- cobarzan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接