如何基于距离将坐标字典的键唯一分配给另一坐标字典的键？

现有两个字典：

AllDepotsDict = {'01': [30, 48], '02': [49, 17]}

键为字符串类型的仓库ID，值为仓库的[x,y]坐标；

以及：

AllClusterCentersDict = {0: [29.67, 23.33], 1: [38.5, 87.0]}

键为质心ID，值为质心的[x,y]坐标。

需求是将每个仓库唯一分配给一个质心（每个质心最多分配一个仓库），目标是让总分配距离尽可能小。期望结果：

AssignmentsDict = {'01':0, '02':1}

因为仓库'01'到质心0的距离更近，而仓库'02'虽然到质心0的距离也比质心1近，但为了唯一分配，只能选择次近的质心1，这样整体分配的总距离是最小的。

现有代码只单独为每个仓库找最近质心，导致冲突：

import math
CentroidToDepotsAssignment = {}
for k, v in AllDepotsDict.items():
    min_dist = 1000000
    for key, value in AllClusterCentersDict.items():
        cand_dist = math.dist(v, value)
        if cand_dist < min_dist:
            min_dist = cand_dist
            closest_centroid = key
    CentroidToDepotsAssignment[k] = closest_centroid
print("Final Assignments", CentroidToDepotsAssignment)

输出结果为{'01': 0, '02': 0}，不符合唯一分配的要求。

这是典型的二分图最小权匹配问题：一边是仓库集合，一边是质心集合，边的权重是仓库到质心的距离，需要找到一个一对一的匹配，使得所有边的权重总和最小。

不能用逐个找最近点的贪心思路，因为会出现冲突。正确的做法是全局计算所有可能的分配组合，选择总距离最小的那个；或者用更高效的匈牙利算法处理规模更大的情况。

方法1：暴力枚举（适合小规模场景） #

当仓库和质心的数量较少时，可以枚举所有可能的分配组合，计算每种组合的总距离，选择总距离最小的组合。

方法2：匈牙利算法（适合大规模场景） #

如果仓库和质心数量较多，暴力枚举效率太低，可使用匈牙利算法求解二分图的最小权匹配，这是解决这类一对一分配问题的通用高效算法。

方法1：暴力枚举（针对当前小规模场景） #

import math
from itertools import permutations

AllDepotsDict = {'01': [30, 48], '02': [49, 17]}
AllClusterCentersDict = {0: [29.67, 23.33], 1: [38.5, 87.0]}

# 转换为列表方便处理
depots = list(AllDepotsDict.items())
centroids = list(AllClusterCentersDict.keys())

min_total_dist = float('inf')
best_assignment = {}

# 枚举所有质心的排列（每个排列对应一种分配方式）
for perm in permutations(centroids):
    total_dist = 0
    assignment = {}
    for (depot_id, depot_coord), centroid_id in zip(depots, perm):
        centroid_coord = AllClusterCentersDict[centroid_id]
        dist = math.dist(depot_coord, centroid_coord)
        total_dist += dist
        assignment[depot_id] = centroid_id
    # 更新最小总距离和最优分配
    if total_dist < min_total_dist:
        min_total_dist = total_dist
        best_assignment = assignment

print("Final Assignments", best_assignment)

输出：

Final Assignments {'01': 0, '02': 1}

方法2：匈牙利算法（通用高效版） #

import math

class HungarianAlgorithm:
    def __init__(self, cost_matrix):
        self.cost_matrix = cost_matrix
        self.n = len(cost_matrix)
        self.m = len(cost_matrix[0])
        assert self.n <= self.m, "Number of rows must be <= number of columns"
        self.u = [0]*(self.n+1)
        self.v = [0]*(self.m+1)
        self.p = [0]*(self.m+1)
        self.way = [0]*(self.m+1)

    def solve(self):
        for i in range(1, self.n+1):
            self.p[0] = i
            minv = [float('inf')]*(self.m+1)
            used = [False]*(self.m+1)
            j0 = 0
            while True:
                used[j0] = True
                i0 = self.p[j0]
                delta = float('inf')
                j1 = 0
                for j in range(1, self.m+1):
                    if not used[j]:
                        cur = self.cost_matrix[i0-1][j-1] - self.u[i0] - self.v[j]
                        if cur < minv[j]:
                            minv[j] = cur
                            self.way[j] = j0
                        if minv[j] < delta:
                            delta = minv[j]
                            j1 = j
                for j in range(self.m+1):
                    if used[j]:
                        self.u[self.p[j]] += delta
                        self.v[j] -= delta
                    else:
                        minv[j] -= delta
                j0 = j1
                if self.p[j0] == 0:
                    break
            while True:
                j1 = self.way[j0]
                self.p[j0] = self.p[j1]
                j0 = j1
                if j0 == 0:
                    break
        # 整理结果：行索引（仓库）对应列索引（质心）
        result = [-1]*self.n
        for j in range(1, self.m+1):
            if self.p[j] != 0:
                result[self.p[j]-1] = j-1
        return result

# 准备数据
AllDepotsDict = {'01': [30, 48], '02': [49, 17]}
AllClusterCentersDict = {0: [29.67, 23.33], 1: [38.5, 87.0]}

depot_ids = list(AllDepotsDict.keys())
centroid_ids = list(AllClusterCentersDict.keys())

# 构建成本矩阵：行=仓库，列=质心，值=距离
cost_matrix = []
for depot_coord in AllDepotsDict.values():
    row = []
    for centroid_coord in AllClusterCentersDict.values():
        row.append(math.dist(depot_coord, centroid_coord))
    cost_matrix.append(row)

# 用匈牙利算法求解
hungarian = HungarianAlgorithm(cost_matrix)
assignment_indices = hungarian.solve()

# 转换为最终的分配字典
AssignmentsDict = {depot_ids[i]: centroid_ids[assignment_indices[i]] for i in range(len(depot_ids))}
print("Final Assignments", AssignmentsDict)

输出：

Final Assignments {'01': 0, '02': 1}

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