匈牙利算法
匈牙利算法
- 1 概念
- 2 依据
- 3 目的
- 4步骤
- 5 案例
- 6 测试
1 概念
匈牙利算法基于代价矩阵找到最小代价的分配方法，是解决分配问题中最优匹配(最小代价)的算法。
2 依据
代价矩阵的行或列同时加或减一个数，得到新的代价矩阵的最优匹配与原代价矩阵相同。
3 目的
寻找最优匹配。
4步骤
（1）如果代价矩阵不为方阵，则在相应位置补0使得代价矩阵为方阵。
（2）首先代价矩阵每一行减去此行最小值，每一列减去此列最小值。
（3）用最少的横线或竖线覆盖代价矩阵中的所有0元素。
（4）如果线的条数小于方阵维数，找出步骤3中未被覆盖元素的最小值，且未被覆盖元素减去该最小值；对覆盖直线交叉点元素加上该最小值。
（5）重复步骤(3)、(4)，直到覆盖线的数量等于对应方阵的维度数。
（6）当线的条数等于方阵维数时，从行或列中找0数最小的匹配对，以此类推，找到所有匹配的行和列。
5 案例
6 测试
import numpy as np
cost_matrix = np.array(
[[ 5, 2, 5],
[ 2, 13, 8],
[ 1, 13, 4],
[12, 3, 7]])
x, y = scipy.optimize.linear_sum_assignment(cost_matrix)
# x, y
# (array([0, 1, 2]), array([1, 0, 2]))