求满足20km最小距离约束的最大城市点集的高效Python解法

问题本质 #

你的问题是在满足初始点间距≥10km的约束下，找出最大的点子集，使得子集中任意两点间距≥20km。这属于单位圆盘图的最大独立集问题，但由于初始约束的存在，我们可以避开一般情况下NP难的复杂度，找到高效的解决方案。

可行的算法方案 #

1. 网格划分+邻域过滤（大规模点集首选） #

利用初始点间距≥10km的特性，用网格划分快速缩小邻域查询范围，避免遍历所有点对：

• 网格设计：将平面划分为边长为10√2 ≈14.14km的正方形网格。由于初始点间距≥10km，每个网格内最多只会有1个点（同一网格内两点最大距离为对角线14.14km，符合初始约束）。
• 邻域查询：距离≤20km的点必然落在当前点所在网格的3x3邻域内（3x3网格的对角线约28.28km，覆盖所有可能的近邻点）。
• 图构建与求解：将点转化为图节点，两点间有边当且仅当距离<20km。由于初始约束，每个节点的邻居数量有限（20km范围内最多十几个点），可以对每个连通分支用回溯法求最大独立集，最终合并所有分支的结果。

2. 改进贪心算法（高效近似，适合快速求解） #

你考虑的贪心算法虽然不能保证绝对最优，但在这个场景下有1/2的近似比（即结果大小至少是最优解的一半），且实际运行中常能得到最优解：

• 策略优化：按坐标排序（如x轴从小到大）后，每次选择当前未被排除的点，移除所有20km范围内的点，重复直到无点剩余。
• 可选升级：如果想提升近似效果，可以优先选择周围覆盖点最多的点（加权贪心），但复杂度会略有上升。

3. 精确算法（中小规模点集） #

如果点集规模在数千以内，可采用分支定界+回溯的精确解法：

• 每次分支为“选当前点（移除所有近邻）”或“不选当前点（保留近邻）”两种情况。
• 记录当前已找到的最大子集大小，剪枝那些不可能超过该大小的分支，提升效率。

Python实现示例（网格划分+贪心） #

import math

def max_city_subset(points, min_required_dist=20):
    # 网格大小：10√2 km，保证单网格最多1个初始点
    grid_size = 10 * math.sqrt(2)
    # 构建网格映射：(网格坐标) -> (点坐标, 索引)
    grid = {}
    for idx, (x, y) in enumerate(points):
        grid_key = (int(x // grid_size), int(y // grid_size))
        grid[grid_key] = (x, y, idx)
    
    selected = []
    visited = set()
    
    # 遍历所有网格中的点
    for (gx, gy), (x, y, idx) in grid.items():
        if idx in visited:
            continue
        # 选中当前点
        selected.append((x, y))
        # 检查3x3邻域内的所有点，排除距离不足20km的
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                neighbor_grid = (gx + dx, gy + dy)
                if neighbor_grid not in grid:
                    continue
                nx, ny, n_idx = grid[neighbor_grid]
                if n_idx in visited:
                    continue
                # 计算实际欧氏距离
                dist = math.hypot(x - nx, y - ny)
                if dist < min_required_dist:
                    visited.add(n_idx)
        visited.add(idx)
    return selected

# 测试用例
test_points = [(0,0), (15,0), (30,0), (0,15), (15,15), (30,15)]
result = max_city_subset(test_points)
print("选中的城市子集：", result)

额外优化建议 #

• 超大规模点集（百万级）可使用rtree库构建空间索引，替代网格划分加速邻域查询。
• 若需精确解，可将点按连通分支拆分，对每个分支用回溯法求最大独立集，再合并结果。

内容的提问来源于stack exchange，提问作者Wismar Günther