寻找旧位置到新位置的最小移动匹配算法方案

问题背景 #

• 有3至20个带2D坐标的对象，需匹配等量的新2D坐标点，核心要求是总移动距离最小
• 使用Unity引擎，无内置工具支持该需求，计划通过Python/Pandas脚本实现

现有方案的问题 #

最初通过计算对象到新点的距离矩阵，取行列最小值匹配，存在以下冲突：

• 单个对象被多个新点选为最近匹配目标
• 单个新点被多个对象选为最近匹配目标
• 部分对象无匹配点、部分新点无对应匹配对象

示例数据 #

0          1          2   ...         9          10         11
18     7.305648   8.026363   5.710035  ...  17.495671  23.595815  17.204084
86    25.021771  29.697289  21.702557  ...  26.896933  40.934203  38.877976
201   34.131078  25.249168  25.399301  ...  45.216286  42.278724  24.386605
284   11.190541  20.365760  22.147781  ...   2.798607  18.822864  26.294566
351   34.563530  28.478652  21.878108  ...  45.000284  48.300513  33.026741
393   33.080871  33.124070  22.894585  ...  39.383093  50.000740  41.647761
586   22.026731  15.960542   9.826235  ...  32.721902  35.796940  21.730920
657   22.539747  26.626457  34.888454  ...  18.464566   6.979699  24.862667
664   18.628092  18.880408   8.922881  ...  26.259204  35.471028  27.797514
1067  21.810369  12.634722  17.729529  ...  32.417406  27.951390  10.075525
1113  16.393673  24.246701  20.782216  ...  14.116179  29.544246  32.455269
1196  17.042118  13.581524  23.814823  ...  23.102679  12.043330   7.017820

0       18
1       18
2       18
3       18
4     1067
5      351
6      393
7       86
8     1113
9      284
10     657
11    1196

18       2
86       7
201      4
284      9
351      5
393      6
586      5
657     10
664      2
1067     4
1113     8
1196    11

解决方案：二分图最小权完美匹配（匈牙利算法） #

你的问题属于二分图最小权完美匹配场景，贪心取行列最小值的方法无法解决冲突，而scipy库中的linear_sum_assignment函数（实现了匈牙利算法）专门处理这类问题，能确保每个对象匹配唯一新点，每个新点被唯一对象匹配，且总移动距离最小。

Python/Pandas实现步骤 #

1. 将距离矩阵加载为Pandas DataFrame（行是对象ID，列是新点ID）
2. 调用linear_sum_assignment计算最优匹配
3. 转换为可读的匹配结果

代码示例 #

import pandas as pd
from scipy.optimize import linear_sum_assignment

# 加载距离矩阵（替换为你的实际数据读取逻辑）
distance_matrix = pd.DataFrame(
    [
        [7.305648, 8.026363, 5.710035, 17.495671, 23.595815, 17.204084],
        [25.021771, 29.697289, 21.702557, 26.896933, 40.934203, 38.877976],
        [34.131078, 25.249168, 25.399301, 45.216286, 42.278724, 24.386605],
        [11.190541, 20.365760, 22.147781, 2.798607, 18.822864, 26.294566],
        [34.563530, 28.478652, 21.878108, 45.000284, 48.300513, 33.026741],
        [33.080871, 33.124070, 22.894585, 39.383093, 50.000740, 41.647761],
        [22.026731, 15.960542, 9.826235, 32.721902, 35.796940, 21.730920],
        [22.539747, 26.626457, 34.888454, 18.464566, 6.979699, 24.862667],
        [18.628092, 18.880408, 8.922881, 26.259204, 35.471028, 27.797514],
        [21.810369, 12.634722, 17.729529, 32.417406, 27.951390, 10.075525],
        [16.393673, 24.246701, 20.782216, 14.116179, 29.544246, 32.455269],
        [17.042118, 13.581524, 23.814823, 23.102679, 12.043330, 7.017820]
    ],
    index=[18, 86, 201, 284, 351, 393, 586, 657, 664, 1067, 1113, 1196],
    columns=[0,1,2,9,10,11]
)

# 计算最优匹配：返回对象索引和新点索引的对应关系
obj_row_indices, new_point_col_indices = linear_sum_assignment(distance_matrix)

# 构建匹配结果字典
matching_result = dict(
    zip(
        distance_matrix.index[obj_row_indices],
        distance_matrix.columns[new_point_col_indices]
    )
)

# 输出结果
print("最优匹配结果：")
for obj_id, new_point_id in matching_result.items():
    distance = distance_matrix.loc[obj_id, new_point_id]
    print(f"对象{obj_id} → 新点{new_point_id}，距离：{round(distance, 4)}")

说明 #

• linear_sum_assignment算法时间复杂度为O(n³)，对于3-20的数据集来说效率极高
• 该算法会直接输出无冲突的完美匹配，完全解决你遇到的多个对象抢同一新点、部分对象/新点无匹配的问题
• 可以直接将匹配结果导出为Unity可读取的格式（如JSON、CSV），在Unity中加载使用

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