algorithm - 选择最远元素子集的算法

Question

假设有一组对象S。假设为S中的每对对象定义一个距离函数，它具有度量的属性，即d(x, x) = 0 , d(x, y) = d(y, x)和d(x, z) <= d(x, y) + d(y, z)。

目标：找到一个集合S'，它是具有给定大小的 S 的子集，使得 S' 中的元素在所有可能的S'中彼此相距最远。

问题一：如何定义“相距最远”？请注意，只有距离函数，元素本身没有任何坐标等（它们可能是例如字符串，距离是 Levenshtein 距离）。一个明显的候选者是成对距离的总和，但我想知道是否还有其他（更好的？）方法，尤其是关于问题 2。

问题2：如何实际选择元素以形成S'？一种明显的方法是暴力破解，即尝试所有组合并选择元素相距最远的组合，但这听起来在计算上无效。有没有更好的方法，可能利用元素“最远”的一些巧妙定义。

标签： algorithmsetdistance

Answer 1

假设集合 S 中有N个元素，并将S中元素i的分离度量定义为到其最近邻居的距离，即l(i) = min(d(i, j))其中0 < = i, j <= N - 1, i != j。

因此，生成的子集S'将包含M个元素，其中的最大值为l(i)，其中M是子集S'的给定大小

这需要N * (N-1) / 2 次调用距离函数d。

Tis 算法可以进行一些优化。当我们看到距离d(i, k) < Cmin时，我们可以中止l(i)的计算，其中Cmin是已计算的子集S'候选中的最小l。我们将不得不保留和更新包含对(j, l(j))的候选列表

PS 这个问题等同于E. Dijkstra “最偏远村庄的问题”中描述的问题