匈牙利算法原理与二分图描述

匈牙利算法简单来说其实就是一个最优分配的问题，举个例子：
你有三个工人：小明，小红和小亮。 你需要其中一个清洁浴室，另一个打扫地板，第三个洗窗，但他们每个人对各项任务要求不同数目数量的钱。 以最低成本的分配工作的方式是什么？ 可以用工人做工的成本矩阵来表示该问题。表内为某个人完成某项工作所需的金额。例如：

.	小明	小红	小亮
W1	2	3	4
W2	3	2	5
W3	4	3	2

以上表格就是一个简单的匈牙利算法应用问题。三个人去分配三个工作，每个人擅长的工作不同，用最少的话费去完成这个匹配。
上表很简单，总花费最低6元可以完成三个工作。

匈牙利算法是怎么做的呢？
给定n 个工人和任务，以及一个包含分配给每个工人一个任务的成本的矩阵，寻找成本最小化分配。

首先把问题写成下面的矩阵形式

第 1 步

接下来我们对矩阵的行进行操作。将所有行中最小的元素取走，并将该行每个元素都减去刚刚取走的元素。这会让该行至少出现一个零（当一行有两个相等的最小元素时会得到多个零）。对此过程为所有行重复。我们现在得到一个每行至少有一个零的矩阵。现在我们尝试给工人指派任务，以使每个工人只做一项任务，并且每个情况的耗散都为零。说明如下。

0	a2’	a3’	a4’
b1’	b2’	b3″	0
c1’	0	c3’	c4’
d1’	d2’	0	d4’

用 0’ 表示的零为已指派的任务。
如果一次操作不能使每一行都有不同列的0元素，则继续重复操作知道有零元素。

匈牙利算法是一个最优组合的问题，比如有5个工人，每个工人不同工作效率不同，如何组合让他们一起工作效率最高,归根结底是个矩阵问题。可用二分图描述

本文地址：https://blog.csdn.net/weixin_42331859/article/details/110224768