匈牙利算法学习笔记

参考链接：
1. 14-4：匈牙利算法 Hungarian Algorithm

1. 前言

1.1 二分图

二分图通常针对无向图问题。假设G=(V,E)是一个无向图，节点集合V VV可以分割为两个互不相交的子集，并且图中每条边依附的两个节点都分属于这两个互不相交的子集，两个子集内的节点不相邻。

1.2 二分图匹配

给定二分图的边集M，F是边集M中的一个子集，如果F中的每条边的两个节点只有该条边与这两个节点相连，则F称为一个匹配。

2. 匈牙利算法(Hungarian Algorithm)

2.1 基础概念

匈牙利算法(Hungarian algorithm)，主要用于解决一些与二分图匹配有关的问题，例如无权重二分图的最大匹配问题和有权值二分图的最小权值匹配问题等。

2.2 实现步骤

以一个有权值二分图的最小权值匹配问题为例。首先定义一个有权二分图（如下图），每个集合中都包含3个节点。匈牙利算法中要求两个集合中的节点数量相同。

根据二分图构建邻接矩阵，矩阵中的元素表示两个节点之间的权值。

步骤一: 找到邻接矩阵中每一行的最小元素，并且将每一行中的元素都减去该行中的最小元素。

步骤二: 在剩下的矩阵中找到每一列的最小元素，并且将每一列中的元素都减去该列中的最小元素。

步骤三: 用最少的横线或竖线来覆盖矩阵中的所有零元素。如果线条的最少数量等于n，则停止运行；如果线条的最少数量小于n，则继续下一步。（在本案例中n=3）

步骤四: 在没有被覆盖的元素中找到最小值，并且将没有被覆盖的元素减去这个最小值，同时将不同线条交叉位置上的元素加上这个最小值。

步骤五: 回到步骤三，即继续用最少的横线或竖线来覆盖矩阵中的所有零元素。如果线条的最少数量等于n，则停止运行；如果线条的最少数量小于n，则执行步骤四。

步骤六: 最后从剩余的矩阵元素中找到最合适的零元素作为匹配结果。这里每个零元素对应筛选后的两个节点之间的边。

1.节点u 3只能与节点v 1匹配。

 2.节点u 2 能够与节点v 3 匹配，但是考虑到节点v 2 只能与节点u 2 匹配，因此将节点u 2 分配给节点u 2 。

3. 最后只剩下节点u 1与节点v 3匹配。

4. 因此最小权值匹配为{(u 3 ,v 1 ),(u 1 ,v 3 ),(u 2,v 2 )}，最小的权值之和为50 + 35 + 22 = 107 50+35+22=10750+35+22=107。