如何求解numpy数组每行最小值且各最小值来源列唯一

问题本质 #

你的需求属于经典的最小权指派问题：需要从n行n列的矩阵中选取n个元素，满足每行、每列仅选中一个元素，且选中元素的总和最小，完全匹配你要求的「每行选最小值、列不重复」的约束。

高效实现方案 #

直接调用scipy.optimize.linear_sum_assignment即可，它是匈牙利算法的工业级实现，时间复杂度为O(n³)，远优于递归枚举的O(n!)阶乘级复杂度。

示例代码 #

import numpy as np
from scipy.optimize import linear_sum_assignment

# 你给出的示例数组
a = np.array([
    [4, 5, 6],
    [1, 2, 3],
    [7, 8, 9]
])

# 计算最优行列匹配
row_indices, col_indices = linear_sum_assignment(a)

# 得到符合约束的结果
result = a[row_indices, col_indices]
print(result) # 输出 [5 1 9]

非方阵兼容处理 #

如果你的数组不是方阵（行数≠列数），可以做补全处理：

• 行数>列数：给矩阵补列，填充足够大的数值（比如np.inf），保证补的列不会被选中
• 列数>行数：给矩阵补行，填充足够大的数值即可

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