二分图最大匹配

问题来源：腾讯SNG雏鹰计划要求做的mini项目，绪聊app中需要根据用户的性别、年龄、喜欢的tag等综合因素对其他用户打分，需要寻找一个最佳的方法使得用户整体满意度最大。 解决方案： （1）根据需求：对一个用户寻找候选用户时，如果性别不符合用户喜好直接淘汰。先进行第一级划分，根据用户对性别的偏好划分为两个集合：喜欢男生的集合X，喜欢女生的集合Y。 （2）贪心策略，即：对元素少的集合X中的每一个元素x对元素多的集合Y中的每一个尚未匹配的元素进行打分，排序，选出分数最高的，这两个用户即匹配成功。该算法能够保证集合少的每个元素都能得到匹配。 算法如下（C++描述）：

void greedy(const vector<vector<int>>& tagCheck, vector<Person>& x, vector<Person>& y, vector<pair<int, int>>& resultMatch) { for (int i = 0;i < x.size();++i) { pair<int, int> m; vector<pair<int, double>> points; score(x, y, i, points); if (!points.empty()) { m.first = x[i].id; m.second = points[0].first; for (auto it = y.begin();it != y.end();++it) { if (it->id == points[0].first) it->hasMatched = 1; } resultMatch.push_back(m); } } }

（3）二分图最大匹配：上述算法存在很大程度的不足。如图1所示如果按照贪心算法来的话就会出现4号和C是一个最佳匹配却无法匹配，原因在于在4匹配之前C已经匹配过了。 图1 发生这种情况在所难免，如何才能避免这种情况的发生，尽可能提升用户最大满意度？我们可以为每个人选出其打分表前几位的候选人作为“可以忍受的”匹配，我们得到图2，两个人之间有边表示这两个人可以匹配，至少是一个不错的匹配。 图2 现在已经很明显了，这就是一个二分图，不信看看下面的图3. 图3 对于二分图，关于二分图的定义，准确的定义感兴趣的可以参考组合数学的教材，简单来说，就是一个图的顶点被分成两个集合，集合内的顶点之间没有边，只有集合间的顶点之间有边。二分图的最大匹配即一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。对于寻找二分图的最大匹配问题，比较经典的就是匈牙利算法了，匈牙利算法有一个概念叫增广路径，所谓增广路，即是从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。简单来说就是“未匹配-匹配-未匹配”这样的路径，所以很明显，未匹配边比匹配边多一条。因此，只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质，也就是不会有一个人同时匹配到两个人。交换后，匹配的对数比原来多了一条。匈牙利算法就是通过这种策略使用深度优先遍历的方式来寻找增广路径，直到找不到这样的路径也就是找到最大匹配为止。 算法如下：

int path(map<int, vector<int>>& candidate, vector<pair<int, int>>& cx, vector<pair<int, int>>& cy, vector<int>& visited, int u) { int v; for (v = 0;v<cy.size();v++) { if (find(candidate[u].begin(),candidate[u].end(),cy[v].first)!=candidate[u].end() && !visited[v]) { visited[v] = 1; if (cy[v].second == -1 || path(candidate, cx, cy, visited, cy[v].first)){ cx[u].second = cy[v].first; //找到增广路，修改匹配M cy[v].second = cx[u].first; return 1; } } } return 0; } int maxmatch(vector<Person>& onlinePerson, vector<pair<int, int>>& resultMatch) { vector<Person> x, y; split(onlinePerson, x, y); if (x.size() > y.size()) exchange(x, y); map<int, vector<int>> candidate; if (y.size() < 24) { greedy(tagCheck, x, y, resultMatch); return x.size(); } addEdge(x,y,candidate,tagCheck); vector<pair<int, int>> cx, cy; init(x, y, cx, cy); int res = 0; for (int i = 0;i != cx.size();++i) { if (cx[i].second == -1) { //还没被匹配，执行内部代码 vector<int> visited(cy.size(), 0); res += path(candidate, cx, cy, visited, i); //以i为起点开始查找增广路，返回true ，匹配数+1 } } for (int i = 0;i<res;++i) { pair<int, int> p; p.first = cx[i].first; p.second = cx[i].second; resultMatch.push_back(p); } if (res != x.size()) { vector<Person> lx, ly; for (int i = res;i != x.size();++i) { lx.push_back(x[i]); } for (int i = 0;i != y.size();++i) { if (y[i].hasMatched == 0) ly.push_back(y[i]); } greedy(tagCheck, lx, ly, resultMatch); } return x.size(); }