algorithm - 除了求解大小为 n*m 的矩阵外，是否有与匈牙利方法类似的算法？

Question

除了求解大小为 n*m 的矩阵外，是否有与匈牙利方法类似的算法？

（n - 工人，m - 任务，m > n，每个工人必须至少有 1 个任务）

添加虚拟工作者的变体是不正确的，因为在这种情况下，至少有 1 个任务将没有工作者。

例子：

	T1	T2	T3	T4
W1	2	9	6	3
W2	2	3	5	7
W3	5	5	7	2

结果是：

W1 - T2

W2 - T4

W3 - T1, T3

标签： algorithmhungarian-algorithm

Answer 1

如果您希望将每个任务分配给一个工作人员，即使这意味着为每个工作人员分配了多个任务，那么使用一个虚拟行运行一次算法

	T1	T2	T3	T4
W1	2	9	6	3
W2	2	3	5	7
W3	5	5	7	2
D1	0	0	0	0

这会将 W1 分配给 T1，W2 分配给 T2，W3 分配给 T4，D1 分配给 T3。由于 T3 被分配给了一个假工人，因此它基本上没有被分配。如果您删除分配给工作人员的所有任务并添加虚拟列，您可以再次运行它

	D1	D2	T3
W1	0	0	6
W2	0	0	5
W3	0	0	7

这会将 T3 分配给 W2。所以最终的分配是：
W1 到 T1
W2 到 T2 和 T3
W3 到 T4