指派问题与匈牙利法讲解

桃扇骨 2023-09-24 17:55 69阅读 0赞

**指派问题概述：**

实际中，会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的1项，每个人完成任务的时间不一样。于是就有一个问题，如何分配任务使得花费时间最少。

通俗来讲，就是n\*n矩阵中，选取n个元素，每行每列各有1个元素，使得和最小。

如下图：

![d66b76da24b84a6d527073f8071cc802.png][]

**指派问题性质：**

指派问题的最优解有这样一个性质，若从矩阵的一行(列)各元素中分别减去该行(列)的最小元素，得到归约矩阵，其最优解和原矩阵的最优解相同．

#### **匈牙利法：** ####

![7971d70276398dc0d8c4ca67ace06141.png][]

**1.行归约：**

每行元素减去该行的最小元素

**2.列归约：**

每列元素减去该列的最小元素

**3.试指派：**

(1)找到未被画线的含0元素最少的行列，即，遍历所有未被画线的0元素，看下该0元素所在的行列一共有多少个0，最终选取最少个数的那个0元素。

(2)找到该行列中未被画线的0元素，这就是一个独立0元素。对该0元素所在行和列画线。

(3)暂时不看被线覆盖的元素，重复(1)(2)直到没有线可以画。

(4)根据(2)找到的0元素个数判断，找到n个独立0元素则Success，小于n个则Fail.（本例子中，n=5，可以看到，第一次试指派之后，独立0元素有4个，不符合）

**4.画盖0线：**

目标：做最少的直线数覆盖所有0元素，直线数就是独立0元素的个数。

注意：这跟3的线不同；不能用贪心法去画线，比如

1 0 0

1 1 0

1 0 1

若先画横的，则得画3条线，实际只需2条；若先画竖的，将矩阵转置后同理。

步骤3得出的独立0元素的位置

(1)对没有独立0元素的行打勾、

(2)对打勾的行所含0元素的列打勾

(3)对所有打勾的列中所含独立0元素的行打勾

(4)重复(2)(3)直到没有不能再打勾

(5)对打勾的列和没有打勾的行画画线，这就是最小盖0线。

**5.更新矩阵：**

(1)对没有被线划到的数中，找到最小的数。

(2)对没有被线划到的数中，减去最小的数。

(3)对被2条线划到的数中，加上最小的数。

**6.重复3-5直到成功。**

sum = 7+6+9+6+4 = 32

匈牙利算法（Hungarian Algorithm）

**分配问题：**假设有N个人N个任务，每个任务可以分配给任意不同的人，不同的人对不同的任务需要花费的代价也不相同，那么如何分配才能使花费总代价最少。假设现在有三个任务，三个人，每个人完成每个任务的**代价矩阵**如下（代价可以是时间或者金钱等）：

![9fb5bfeb9f6ee351987fde1fa30721e5.png][]

怎么才能找到一个分配方法使得任务花费代价最小呢？

匈牙利算法就是用来解决分配问题的一种方法，它基于理论：如果代价矩阵的某一行或某一列同时加或减某个数，则这个新的代价矩阵的最优分配任然是原代价矩阵的最优分配。

算法步骤（假设矩阵为NxN方阵）：

1.对于矩阵的每一行，减去其中最小的元素

2.对于矩阵的每一列，减去其中最小的元素

3.用最少的水平线或垂直线覆盖矩阵中所有的0

4.如果线的数量等于N，则找到了最优分配，算法结束，否则进入步骤5

5.找到没有被任何线覆盖的最小元素，每个**没被线覆盖的行**减去这个元素，个**被线覆盖的列**加上这个元素，返回步骤3

继续拿上面的例子演示：

1.每一行减去其最小元素得到：

![89441a568686dd2179143fc490d87ee3.png][]

2.每一列减去其最小元素得到：

![bb7e84386dd5deb4002cf608e1dc1f27.png][]

3.用最少的水平线或者垂直线覆盖所有的0得到：

![9aa1f55b41ef924f7eee28fb4d0064a2.png][]

4.线的数量为2，小于3，进入第五步：

5.现在没被覆盖的最小元素是5，没被覆盖的行（第一和第二行）减去5，得到：

![5ab700831a6eefbec61109359ab39171.png][]

6.被覆盖的列（第一列）加上5，得到：

![42f86fb871900705d066581622d8bc21.png][]

7.回到步骤3，用最少的线覆盖所有0：

![8e9516602aad6bcf82eff7e649ce897f.png][]

8.线的数量=3，算法结束，很显然，第一个任务给第二人，第二个任务给第一人，第三个任务给第三人，总代价最小（0+0+0）：

![18ec8d37b452b720795b3e871120f2d0.png][]

9.所以原矩阵最小代价为（40+20+25=85）：

![7a777fb8a21f0284c055fc71920b64aa.png][]

[d66b76da24b84a6d527073f8071cc802.png]: https://img-blog.csdnimg.cn/img_convert/d66b76da24b84a6d527073f8071cc802.png
[7971d70276398dc0d8c4ca67ace06141.png]: https://img-blog.csdnimg.cn/img_convert/7971d70276398dc0d8c4ca67ace06141.png
[9fb5bfeb9f6ee351987fde1fa30721e5.png]: https://img-blog.csdnimg.cn/img_convert/9fb5bfeb9f6ee351987fde1fa30721e5.png
[89441a568686dd2179143fc490d87ee3.png]: https://img-blog.csdnimg.cn/img_convert/89441a568686dd2179143fc490d87ee3.png
[bb7e84386dd5deb4002cf608e1dc1f27.png]: https://img-blog.csdnimg.cn/img_convert/bb7e84386dd5deb4002cf608e1dc1f27.png
[9aa1f55b41ef924f7eee28fb4d0064a2.png]: https://img-blog.csdnimg.cn/img_convert/9aa1f55b41ef924f7eee28fb4d0064a2.png
[5ab700831a6eefbec61109359ab39171.png]: https://img-blog.csdnimg.cn/img_convert/5ab700831a6eefbec61109359ab39171.png
[42f86fb871900705d066581622d8bc21.png]: https://img-blog.csdnimg.cn/img_convert/42f86fb871900705d066581622d8bc21.png
[8e9516602aad6bcf82eff7e649ce897f.png]: https://img-blog.csdnimg.cn/img_convert/8e9516602aad6bcf82eff7e649ce897f.png
[18ec8d37b452b720795b3e871120f2d0.png]: https://img-blog.csdnimg.cn/img_convert/18ec8d37b452b720795b3e871120f2d0.png
[7a777fb8a21f0284c055fc71920b64aa.png]: https://img-blog.csdnimg.cn/img_convert/7a777fb8a21f0284c055fc71920b64aa.png