选择具有增加的最小距离约束的最大点子集

Question

我正在用Python解决一个空间分析问题，其中我有一个2D点坐标的无序列表。每个点代表一个城市，所有城市之间保证有最小距离 10 公里。我的目标是找到这些城市的最大子集，使得子集中的每个城市与子集中的每个其他城市的最小距离为 20 公里。

这是我挑战的核心：

• 初始约束：每个城市与其他城市至少相距 10 公里。
子集的新约束：每个城市必须与子集中的所有其他城市
• 至少相距 20 公里。
任意两点

(x1, y1)

和 (x2, y2) 之间的距离是使用标准欧几里德距离公式计算的。考虑到潜在的大量点，我正在寻找一种有效的 Python 算法或方法来解决这个问题。 我正在用Python解决一个空间分析问题，其中我有一个

2D点坐标

的无序列表。每个点代表一个城市，所有城市之间保证有最小距离 10 公里。我的目标是找到这些城市的最大子集，使得子集中的每个城市与子集中的每个其他城市的最小距离为 20 公里。 这是我挑战的核心：

初始约束：每个城市与其他城市

至少相距 10 公里。
• 子集的新约束：每个城市必须与子集中的所有其他城市至少相距 20 公里。
• 任意两点 (x1, y1)
和

(x2, y2)

之间的距离是使用标准欧几里德距离公式计算的。考虑到潜在的大量点，我正在寻找一种有效的 Python 算法或方法来解决这个问题。 我考虑过一种贪婪的方法，迭代地选择一个城市并排除其 20 公里范围内的所有城市。然而，我担心由于贪婪选择的性质，这可能不会产生最大可能的子集。 有人对可以有效找到满足 20 公里最小距离约束的点的最大子集的算法或方法有建议吗？

任何见解或指示将不胜感激！

这是最大派系问题。城市是节点，每对节点都会获得一条边，前提是它们满足距离约束。

Answer 1

来自维基百科，Bron-Kerbosch 算法可能会有所帮助

。

这是用于在无向图中查找所有最大团的 Bron-Kerbosch 算法。 初始化R & X 为空集，P 为图的顶点集。

algorithm BronKerbosch2(R, P, X) is
    if P and X are both empty then
        report R as a maximal clique
    choose a pivot vertex u in P ⋃ X
    for each vertex v in P \ N(u) do
        BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

效率：O(3^(n/3))