XY平面内两不等点集的最小总连接距离求解问询

嘿，这个问题其实是经典的分配问题的变种，更准确说是多对一的最小成本匹配问题——刚好我之前处理过类似场景，给你梳理下思路和实用解法：

第一步：先计算所有点对的距离 #

不管用哪种方法，第一步都是先算出A中每个点到B中每个点的距离。XY平面里最常用的是欧氏距离，公式很简单：
distance = sqrt((x_A - x_B)² + (y_A - y_B)²)
把这些距离整理成一个9×3的矩阵，行对应A的点，列对应B的点，每个元素就是对应点对的距离值。

方法一：暴力枚举（最适合你的小规模场景） #

因为9个A点每个有3种选择，总共有3^9 = 19683种分配方式——这个数量级对计算机来说完全是小菜一碟，暴力遍历所有可能绝对可行，而且能保证得到最优解。

代码示例（Python） #

假设你已经把点存在列表里了，比如points_A是9个(x,y)元组，points_B是3个(x,y)元组，代码可以这么写：

import math
from itertools import product

def calc_dist(p1, p2):
    # 计算两点欧氏距离
    return math.hypot(p1[0] - p2[0], p1[1] - p2[1])

# 预计算所有A到B的距离矩阵
dist_matrix = [[calc_dist(a, b) for b in points_B] for a in points_A]

min_total_dist = float('inf')
best_assignment = None

# 枚举所有可能的分配方案：每个A点选0/1/2对应B的三个点
for assignment in product(range(3), repeat=9):
    current_total = 0
    for a_idx, b_idx in enumerate(assignment):
        current_total += dist_matrix[a_idx][b_idx]
    # 更新最小总距离和最优分配
    if current_total < min_total_dist:
        min_total_dist = current_total
        best_assignment = assignment

print(f"最小总距离: {min_total_dist:.4f}")
print("每个A点对应的B点索引（0/1/2）:", best_assignment)

运行这段代码很快就能得到结果，而且绝对是最优的。

方法二：整数线性规划（ILP，适合未来规模扩大的情况） #

如果以后你的点集规模变大（比如A有100个点，B有20个），暴力法就吃不消了，这时候可以用整数线性规划建模求解。

建模思路 #

• 定义变量x_ij：如果A的第i个点连到B的第j个点，x_ij=1，否则为0
• 约束条件：
  • 每个A点必须且只能连一个B点：sum(j=1到3) x_ij = 1，对所有i=1到9
  • x_ij只能是0或1的整数
• 目标函数：min sum(i=1到9) sum(j=1到3) x_ij * d_ij（d_ij是A_i到B_j的距离）

你可以用PuLP、Gurobi这类Python库来实现，代码写起来也很直观，而且能高效处理大规模问题。

方法三：贪心+局部优化（快速近似，小规模没必要） #

先给每个A点分配到离它最近的B点，得到一个初始总距离，然后尝试把某个A点从当前B点切换到另一个B点，看总距离是否减少，反复迭代直到没法优化。这个方法速度极快，对于你的小规模场景，大概率直接就能得到最优解，不过暴力法已经足够简单，所以这个方法优先级稍低。

注意事项 #

• 允许B点无连接的情况：不管是暴力法还是ILP，都会自动处理——如果某个B点被分配的总距离比不使用它更大，算法会自动选择不把任何A点分配给它。
• 距离度量可以替换：如果你需要用曼哈顿距离或者其他度量，只需要修改calc_dist函数的计算逻辑就行。

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