algorithm - 如何在完全连接的图中选择 k 个节点，其中任何一对节点之间的距离最大？

Question

假设我有一个由 N 个节点组成的全连接图，并且我知道任意两对节点之间的权重。如何选择 k 节点以使任何一对节点之间的最小距离最大化？

我将此问题映射为我实际想要解决的问题的更一般情况，我称之为作弊学生问题(我不知道它是否有实际名称) .

---

作弊问题:

给定一个 N.M 矩阵，如何选择 k 个单元格，其中任意一对单元格之间的距离最大？您可以假设矩阵是一个教室，k 作弊的学生正在其中进行测试。任何一对学生都不应彼此靠近，因此我们希望最大化任何一对学生之间的最小距离。

Answer 1

您的广义图问题似乎与 https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 中描述的最大独立集问题密切相关，这是 NP 完全的。我可以通过运行 binary chop 找到最大的 k 来找到最大独立集，解决你的图形问题的算法返回的最小距离大于 1。由于找到最大独立集很难，我认为你的广义问题很难。

我也没有看到解决矩阵问题的简单方法，但是在无限大的二维表面上尽可能高效地包装圆的相关问题已经解决了，答案就是所谓的六边形堆积 (https://en.wikipedia.org/wiki/Circle_packing) 令人困惑地基于三角形拼贴(https://en.wikipedia.org/wiki/Triangular_tiling - “三角形拼贴的顶点是最密集的圆形堆积的中心”)。

因此，对于有限矩阵和学生数量，可以将学生安排在间隔较远的行中，行交错排列，以便每个学生都位于他们前面和后面一排距离他们最近的一对学生之间，离最佳位置不远 - 或者至少是开始某种爬山尝试的好地方。