给定K个点集，从每个集合中选择一个点，使得所选点之间的配对距离之和最小化。

Question

给定K个点集，从每个集合中选择一个点，使得所选点之间的配对距离之和最小化。

algorithmgraphdynamic-programming

4

这个问题与选择每个给定n个整数集合中的一个整数，使其配对距离之和最小非常相似，但不同之处在于我们有多维特征向量及任意的距离函数来衡量它们的相似性。

那个发帖人声称他已经找到了一个多项式时间解决方案来解决他的问题，而且这个方案看起来也适用于我的问题，但我无法理解他的答案，而且它是否正确也不清楚。

我的问题等价于这个问题，其中图的权重等于相似函数的输出。

完全k部分图中的最大权重k团

但是不清楚k部分图是否比一般的最大权重团问题更容易解决。

编辑：

从David Eisenstat的回答中，原问题似乎不能在多项式时间内解决。但如果目标是最小化所选点之间的最大配对距离，是否会有所改变呢？

- gokva

也许我没有完全正确地理解这个问题，但是这不是可以通过两遍线性算法来解决吗？1）对所有集合中的所有点进行一次遍历，计算所有点的质心，然后2）对于每个集合，迭代集合中的所有点，找到距离质心最近的点。在二维情况下，似乎至少可以这样做。在三维及以上的情况下可能不太容易想象... - twalberg

考虑一种情况，即每个集合的第一个元素相同。因此，最佳解决方案是选择每个集合的第一个元素。但是，这些集合包含许多其他点，它们将质心拉得远离该解决方案，因此距离质心最近的点不是最佳解决方案。 - gokva

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

另一个答案可能是使用整数的特定属性，因为这个版本是NP-hard的。给定k和一个无向图G =（V，E），我们可以通过让点V×{1，…，n}存在，并且当{v，w}∈E且i≠j时，设置d（（v，i），（w，j））= 1，否则d（（v，i），（w，j））= 2来检测G是否具有k-clique。每个集合都由某些i的点V×{i}组成。

Evgeny Kluev的局部搜索算法可能是值得尝试的合理方法。使用随机点初始化解决方案，然后反复执行以下操作。对于一些随机集合（或集合的集合），确定在其他集合中的点保持不变的约束条件下的最优解。重新尝试整个计算几次以避免局部最小值。