如何求解最小权重的单射/满射映射及对应的Python实现？

问题前提 #

给定对应完全二分图$K_{m,n}$边权重的$m \times n$矩阵w，需求是找到从集合${1,…,m}$到${1,…,n}$的最小权重映射，映射要求为单射或满射。映射的规则等价于为${1,…,m}$中的每个顶点$v$，恰好选取一条与$v$关联的边。

m≤n场景：最小权重单射求解 #

该场景下最小权重单射等价于二分图的最小权完美匹配，可直接调用scipy的linear_sum_assignment接口实现，示例代码如下：

import numpy as np
import scipy.optimize

# 示例：m=5，n=10，生成随机权重矩阵
w = np.random.rand(5, 10)
# 返回值分别为左边节点索引数组、匹配到的右边节点索引数组
left_ind, right_ind = scipy.optimize.linear_sum_assignment(w)
print("匹配结果：", list(zip(left_ind, right_ind)))
print("总权重：", w[left_ind, right_ind].sum())

m≥n场景：最小权重满射求解 #

实现思路 #

满射要求右边n个节点每个至少被匹配一次，我们可以通过构造扩展权重矩阵的方式，将问题转化为标准的最小权完美匹配问题，复用linear_sum_assignment接口求解：

• 将右边的n个节点重复复制，直到右边总节点数等于左边的m个，生成m×m的扩展权重矩阵，扩展位置的权重和原对应节点的权重一致
• 对扩展矩阵调用最小权完美匹配算法
• 将匹配得到的扩展右边节点索引映射回原始的n个节点编号，得到最终满射结果

完整实现代码 #

import numpy as np
import scipy.optimize

def min_weight_surjection(w):
    m, n = w.shape
    assert m >= n, "该方法仅适用于m≥n的满射求解场景"
    # 构造m*m的扩展权重矩阵
    extended_w = np.tile(w, (1, (m // n) + 1))[:, :m]
    # 求解扩展矩阵的最小权完美匹配
    left_ind, extended_right_ind = scipy.optimize.linear_sum_assignment(extended_w)
    # 映射回原始右边节点编号
    right_ind = extended_right_ind % n
    return left_ind, right_ind, w[left_ind, right_ind].sum()

# 测试示例
if __name__ == "__main__":
    # 示例：m=5，n=3，生成随机权重矩阵
    w = np.random.rand(5, 3)
    left_ind, right_ind, total_weight = min_weight_surjection(w)
    print("左边节点索引：", left_ind)
    print("匹配的右边节点索引：", right_ind)
    print("是否满足满射（右边所有节点都出现）：", set(right_ind) == set(range(3)))
    print("总权重：", total_weight)

结果说明 #

返回的right_ind数组长度和左边节点数m一致，每个元素对应左边节点匹配的右边节点编号，保证右边所有n个节点都至少出现一次，且总权重为所有满足满射的映射中的最小值。

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