基于距离的点分组算法需求：将200个点分成间距合规的20点批次

嘿，这个问题我之前帮人处理过类似的，你的树分支法确实会因为逐个校验所有节点导致效率拉胯——毕竟200个点的话，每次加新点都要和分支里所有点算距离，时间复杂度直接飙到O(N²)，完全没必要。针对你的需求，我整理了几个兼顾效率和可行性的方案，从快速实现到更优解都有：

本质上这是个带约束的空间分组问题，等价于把200个点划分为10个独立集：每个集合内的点两两距离≥n厘米，且每个集合恰好20个点。这属于图着色问题的变种，只不过固定了“颜色数”（10组）和每个颜色的使用次数（20次）。

1. 空间索引+贪心分组（最快落地） #

这是最适合快速实现的方案，核心是用空间索引减少距离校验的次数：

• 先给所有点构建KD-Tree/R树，查询某个点附近n厘米内的点时，不用遍历全部点，时间复杂度降到O(logN)
• 贪心策略：按点的“冲突度”（距离它<n的点的数量）从小到大排序，优先处理冲突少的点，这样更容易找到能容纳它的批次
• 分配逻辑：依次把点加入第一个还没满（<20个点）且所有现有成员与它距离≥n的批次

2. 图着色+启发式算法（更优解） #

如果贪心策略遇到局部最优卡壳（比如某个点找不到合适批次），可以用这个方法：

• 把每个点看作图的节点，若两点距离<n则连一条边（表示这两个点不能同组）
• 问题转化为：用10种颜色给图着色，每种颜色恰好涂20个节点
• 用模拟退火/遗传算法这类启发式方法求解，能在合理时间内跳出局部最优，找到可行解

3. 预处理：提前排查无解情况 #

在开始分组前先做两步校验，避免做无用功：

• 统计每个点的冲突点数量，如果某个点的冲突点≥10，直接判定无解（因为它不能和这10个点同组，而总共只有10组，必然会冲突）
• 统计所有冲突边的数量，结合图着色的必要条件（比如每个颜色类的最大可能大小）判断是否有解

步骤1：读取Input.csv数据 #

import pandas as pd
import numpy as np

# 读取输入文件
df = pd.read_csv('Input.csv')
points = df[['X', 'Y']].values
point_names = df['点名称'].values
n = 5  # 替换为你的实际n厘米值

步骤2：构建KD-Tree加速查询 #

from scipy.spatial import KDTree

# 构建空间索引
kdtree = KDTree(points)

步骤3：贪心分组实现 #

# 初始化10个空批次
batches = [[] for _ in range(10)]
# 标记点是否已被分配
assigned = [False] * len(points)

# 计算每个点的冲突数量并排序（冲突少的先处理）
conflict_list = []
for idx in range(len(points)):
    # 查询距离<n的点数量（减去自身）
    conflict_cnt = len(kdtree.query_ball_point(points[idx], n)) - 1
    conflict_list.append((conflict_cnt, idx))
# 按冲突数量升序排序
conflict_list.sort()

# 开始分配点
for _, idx in conflict_list:
    if assigned[idx]:
        continue
    # 遍历所有批次，找第一个能容纳当前点的批次
    for batch in batches:
        if len(batch) >= 20:
            continue
        # 校验当前点与批次内所有点的距离
        is_valid = True
        for p_idx in batch:
            dist = np.linalg.norm(points[idx] - points[p_idx])
            if dist < n:
                is_valid = False
                break
        if is_valid:
            batch.append(idx)
            assigned[idx] = True
            break

# 转换为点名称并输出
output_lines = []
for batch_num, batch in enumerate(batches, 1):
    batch_point_names = [point_names[idx] for idx in batch]
    output_lines.append(f"批次{batch_num}: {', '.join(batch_point_names)}")

# 保存结果到文件
with open('批次列表.txt', 'w', encoding='utf-8') as f:
    f.write('\n'.join(output_lines))

• 原树分支法：时间复杂度O(N²)，200个点要做40000次距离计算
• 优化后的贪心+KD-Tree：冲突数量计算是O(NlogN)，分组阶段总计算量约40000次，但实际因为排序后大部分点能快速找到批次，实际计算次数远低于这个数，效率提升非常明显

内容的提问来源于stack exchange，提问作者user9795427