Python中使用匈牙利算法处理非方形成本矩阵实现矩阵重排

问题描述 #

需要对6行7列的非方形numpy数组执行匈牙利分配算法，实现最大化成本的列重排，输入矩阵如下：

import numpy as np
X = np.array([[0.26, 0.64, 0.16, 0.46, 0.5 , 0.63, 0.29],
              [0.49, 0.12, 0.61, 0.28, 0.74, 0.54, 0.25],
              [0.22, 0.44, 0.25, 0.76, 0.28, 0.49, 0.89],
              [0.56, 0.13, 0.45, 0.6 , 0.53, 0.56, 0.05],
              [0.66, 0.24, 0.61, 0.21, 0.47, 0.31, 0.35],
              [0.4 , 0.85, 0.45, 0.14, 0.26, 0.29, 0.24]])

期望重排后的输出矩阵为：

X_desired_output = np.array([[0.63, 0.5 , 0.29, 0.46, 0.26, 0.64, 0.16], 
                             [0.54, 0.74, 0.25, 0.28, 0.49, 0.12, 0.61], 
                             [0.49, 0.28, 0.89, 0.76, 0.22, 0.44, 0.25], 
                             [0.56, 0.53, 0.05, 0.6 , 0.56, 0.13, 0.45], 
                             [0.31, 0.47, 0.35, 0.21, 0.66, 0.24, 0.61], 
                             [0.29, 0.26, 0.24, 0.14, 0.4 , 0.85, 0.45]])

已通过munkres库实现最大化成本的匈牙利算法调用，代码如下：

from munkres import Munkres

m = Munkres()
indices = m.compute(-X)
# 输出的匹配索引为 [(0, 5), (1, 4), (2, 6), (3, 3), (4, 0), (5, 1)]
jj = [j for (i,j) in indices]

当前问题为：得到的jj仅包含6个元素，比原矩阵的7列少，无法直接用于列重排。

解决方案 #

匈牙利算法处理行数小于列数的非方阵时，仅会为每一行匹配一个唯一的列，因此返回的匹配列索引仅包含和行数相等的6个元素，剩余未被匹配的列需要手动补到重排列表的末尾。

完整重排代码如下：

# 1. 提取匹配到的列索引
jj = [j for (i,j) in indices]
# 2. 筛选未被匹配的列索引，按原有顺序排列
remaining_cols = [col for col in range(X.shape[1]) if col not in jj]
# 3. 拼接得到完整的列重排顺序
full_col_order = jj + remaining_cols
# 4. 按顺序重排列
X_reordered = X[:, full_col_order]

此时得到的X_reordered和给出的期望输出完全一致，其中生成的full_col_order为[5,4,6,3,0,1,2]，刚好对应期望的列重排规则。

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