匈牙利算法详解

匈牙利算法(Hungarian Algorithm)是一种组合优化算法(combinatorial optimization algorithm)，用于求解指派问题(assignment problem)，算法时间复杂度为O(N^3)。Harold Kuhn发表于1955年，由于该算法基于两位匈牙利数学家的早期研究成果，所以被称作“匈牙利算法”。

假设有三位工人A,B和C，需要分配他们每人完成一件工作；对于不同的工作他们所需要花费的时间不同，如下表所示。问题就是要找到一套耗时最小的指派方案。用矩阵表示如下：
在这里插入图片描述

匈牙利算法包含四步。前两步一次执行完，第三步和第三步会重复执行直到最优分配出现。算法的输入是n*n的矩阵，只有非负数。
Step 1: Subtract row minima （减去行最小值）
对于每一行，找到该行的最小值，然后该行的数都减去这个最小值
Step 2: Subtract column minima（减去列最小值）
同样的，对于每一列，找到该列的最小值，然后该列的数都减去这个最小值

Step 3: Cover all zeros with a minimum number of lines（用最少的线覆盖所有的0）
用最少的水平线和垂直线覆盖掉矩阵的所有0元素。如果需要n条线，那么在这些0中就存在最优解。算法结束
如果需要的线<n，继续第四步
Step 4: Create additional zeros（创建额外的0元素）
在第三步的的矩阵中，找到没被线覆盖的行列中的最小的元素，记作k。所有没被覆盖的元素都减去k，被覆盖两次的元素加上k。

第一步，找出每一行中值最小的元素，然后把该行所有元素都减去这一最小值：

在这里插入图片描述
第二步，对于每一列，找到该列的最小值，然后该列的数都减去这个最小值

第三步，用最少的水平线和垂直线覆盖掉矩阵的所有0元素。如果需要n条线，那么在这些0中就存在最优解。算法结束

可以看到当前的覆盖所有的0需要两条线，<n，继续第四步

第四步，找到没被线覆盖的行列中的最小的元素，记作k。所有没被覆盖的元素都减去k，被覆盖两次的元素加上k
在这里插入图片描述此时刚好用3条线即可覆盖所有的0，算法结束

即最后指派A拖地，B擦桌，C扫厕所

二分图

1、一定不含有奇数环，可能包含长度为偶数的环，不一定是连通图
2、二分图是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交子集，使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分，则此图为一个二分图，如下图所示的全都是二分图：
在这里插入图片描述

2.二分图的匹配

二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
假设二分图的左边全为男生，右边全为女生，线连着的男女生为情侣关系，允许出现脚踏n条船等混乱的男女关系的情况，那么：

二分图的匹配：把二分图删除一些边使男女生之间的关系没有出现脚踏n条船的情况，就说删除边后得到的新图为一个匹配(允许出现单身狗的情况)
二分图的最大匹配：删除部分边使得保留的情侣数量最多，我们就称这个匹配为最大匹配。
比如在上面的4张图中，图1就是图3的一个最大匹配。

3、匈牙利算法的实现步骤

有如下图：

在这里插入图片描述
1.情况一（你是我的唯一）
首先我们看向男1，发现男1很纯情的只喜欢着女2，那么就成全他们吧。确定他们两个人的情侣关系。

2.情况二（你们都是我的翅膀）
接下来我们看向男2，发现男2喜欢着女1和女3两个女孩子。问问男2吧，他表示：我对这两个女孩子都是真心的，选谁都行！

选谁都行啊，那我们就随便选吧，把男2和女1牵上红线。
在这里插入图片描述
3.情况三（我会把你抢过来）
搞定，然后我们再看看男3，男3表示：我也喜欢女1啊！明明是我更加喜欢她！为什么？为什么她和别人在一起了啊！我不能接受！
嗯…看来我们的男3不想放弃啊，那我们尝试和男2交涉一下。
“男2呀，你有备胎吗？”
“有啊，怎么了？”
“男3看上了你女朋友，要不你和你备胎在一起，把你女朋友让给别人吧”
“嗯…好吧，记得让他请我吃饭”（作者对男2这种渣男表示强烈谴责！）
ok，这样的话事情就圆满解决了，可喜可贺可喜可贺。
在这里插入图片描述

4.情况四（我爱的人已经有了爱人）
解决了男2和男3的问题，我们再看向男4。

男4说：我喜欢女3！我想和女3在一起！
我看了看，女3不是男2的新女友吗？额…我再去找男2看看吧。

“什么？还要我换？大哥，我没别的备胎了，我拒绝！要是我还有备胎的话还差不多。”（作者对男2这种渣男表示强烈谴责！）

我们只好回头土脸的找到男4。那个，我们交涉失败了，女3是没戏了，要不你换一个追求对象我帮你争取一下？

男4低头沉思了一下，“我觉得吧，女4其实也挺可爱的。”

ok，安排！我们看了看，发现女4还是单身呢，那就成全你们吧。
在这里插入图片描述
最后，我们得到的最大匹配就是这样

总结：算法描述：
如果你想找的妹子已经有了男朋友，
你就去问问她男朋友，
你有没有备胎，
有备胎就把你女朋友让给我
你没有备胎我就只好找我的备胎
出处：1
2

代码：

在这里插入图片描述

#include <iostream>
#include <vector>using namespace std;// 使用DFS查找增广路径
bool dfs(vector<vector<int>>& graph, int u, vector<bool>& visited, vector<int>& match) {int m = graph.size();int n = graph[0].size();for (int v = 0; v < n; ++v) {if (graph[u][v] && !visited[v]) {visited[v] = true;// 如果v没有匹配或者可以找到增广路径if (match[v] == -1 || dfs(graph, match[v], visited, match)) {match[v] = u;return true;}}}return false;
}// 计算二分图的最大匹配数
int hungarian(vector<vector<int>>& graph) {int m = graph.size();int n = graph[0].size();vector<int> match(n, -1); // 存储匹配信息，match[i]表示右侧第i个节点的匹配节点编号int count = 0; // 最大匹配数for (int u = 0; u < m; ++u) {vector<bool> visited(n, false); // 记录每个节点的访问状态if (dfs(graph, u, visited, match)) {count++;}}return count;
}// 测试
int main() {vector<vector<int>> graph = {{1, 0, 1, 0},{1, 0, 0, 0},{0, 1, 1, 1},{0, 0, 1, 0}};int maxMatching = hungarian(graph);cout << "Maximum matching: " << maxMatching << endl;return 0;
}