给定一个由个点组成的集合，我们想要找到k，它使它们之间的总距离最大化。
在我的例子中，是一个布尔向量，考虑的距离是曼哈顿/汉明距离。
有没有什么有效的方法来解决这个问题？是否可以用另一种更简单的方式重写它？
在 n 之间找到使总距离最大化的 K 个元素的集合
计算科学
优化
2021-12-07 10:53:12
1个回答
这被称为最远点聚类问题。它是 NP-hard，但有一个近似算法：https ://en.wikipedia.org/wiki/Farthest-first_traversal 。该问题通常使用欧几里得距离度量进行研究，但您也可以将相同的贪心算法应用于汉明距离，以获得近似（但不一定是最佳）解决方案。