专栏名称: 程序IT圈
一个学习编程技术和读者福利共存的公众号，每天推送高质量的优秀博文和原创文章，开源项目，实用工具，面试技巧等 。公众号每月至少一次读者送书福利！ 关注置顶，不错过精彩推送！
目录
相关文章推荐
程序猿  ·  450万虚假Star曝光，最低0.7元/个？ ... ·  20 小时前  
OSC开源社区  ·  DeepSeek-V3满血版在国产沐曦GPU ... ·  昨天  
程序员小灰  ·  如何用DeepSeek来变现？90%的人都不知道 ·  2 天前  
程序员小灰  ·  DeepSeek的处境极其危险 ·  4 天前  
码农翻身  ·  强烈建议尽快搞个软考证！（2025重大红利） ·  5 天前  
51好读  ›  专栏  ›  程序IT圈

算法：单身男女问题的科学解决方案

程序IT圈  · 公众号  · 程序员  · 2021-03-04 10:00

正文

点击上方蓝字 关注我，涨知识


以下场景太过真实，但都是虚构，为了讲清楚理论的过程。如有雷同，纯属我瞎编，还望勿对号入座。

01
婚恋市场，明码实价
中国如今男女比例严重失衡，2021年预计将有9200万单身贵族。为了帮助解决这个社会性问题，提升整体人民的幸福感，小K打算投身到这份伟大的事业中。
“几何思维”婚恋所，用最科学的方法，帮你脱单。通过概率论寻找最佳匹配对象，再通过微积分精确计算好感上升曲线，最后用数值分析无限逼近对方的理想型。最可怕的是，还包邮呢亲，关注一波了解一下？
上班第一天，老板给了小K一份单身男女好感的数据资料。如下图，连线表示双方互有好感，可以尝试处对象。突然有一个问题，怎样才能找出最大匹配呢？


02
不要怂，就是干
很多时候不是你比别人差，而是你执行力不够，在犹豫中丧失机会。
大家就先行动起来吧。
快看，男1号选手在小K的鼓励(怂恿)下，率先对女1号发起了进攻。在离失败只有0.01公分的时候，他竟然奇迹般的完成反杀，没错，他成功啦，这种高超的技巧，娴熟的手法简直如同教科书一般，值得在座的每个同学深入研究反复琢磨啊。
男2号选手也不甘落后，也对女2号选手发起了进攻，没错，又一次成功啦。
男3号选手：我勒个去，我上我也行啊。于是也对自己心动的女1号发起了进攻，毫无意外，他阵亡了。。。
中间彩蛋。
男3号不甘心，原地复活，想再战一回。在一个地方跌倒，咱们就换一个地方再跌。。。
于是对女2号发起了进攻。
几经波折。
男3号终于也成为了有牵绊的男人，不论未来有多久，只在乎曾经拥有过。
男4一看：这也没我啥事儿了啊。
以上的过程其实就是经典的匈牙利算法，求解二分图的最大匹配问题。

03
匈牙利算法
二分图
定义：设G=(V,E)是一个无向图，顶点集V可分割为两个互不相交的子集X，Y，并且图中每条边关联的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
判断是否为二分图的充要条件：G至少有两个顶点,且其所有回路的长度均为偶数。
判断方法：染色法
  • 开始对任意一未染色的顶点染色
  • 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色；
  • 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断
可用bfs或者dfs。
匹配
在二分图G的子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
饱和点
匹配M的边集所关联的点为饱和点，否则为非饱和点。如上图：
  • 的饱和点：。
  • 的饱和点：。
交错路
定义：图G的一条路径，且路径中的边在属于M和不属于M中交替出现。
增广路(非网络流中的定义)
定义：一条交错路，且该交错路的起点和终点都为匹配M的非饱和点。
如上图，交错路1是增广路；交错路2不是增广路，因为终点不是非饱和点。
由增广路推出以下结论：
  • 路径的边数为奇数，第一条边和最后一条边都不属于M
  • 将路径中的边的匹配方式取反操作，会得到更大的匹配M'，匹配数加1
  • M为图G的最大匹配等价于不存在M的增广路
匈牙利算法核心思想：
  • 1) 初始匹配M为空
  • 2) 找出一条增广路径p，取反操作得到更大的匹配M'代替M

  • 3) 重复步骤2)，直到找不出增广路为止


04






请到「今天看啥」查看全文

推荐文章
程序猿  ·  450万虚假Star曝光，最低0.7元/个？GitHub星标造假潮，多数在恶意软件仓库中！
20 小时前
OSC开源社区  ·  DeepSeek-V3满血版在国产沐曦GPU首发体验上线
昨天
程序员小灰  ·  如何用DeepSeek来变现？90%的人都不知道
2 天前
程序员小灰  ·  DeepSeek的处境极其危险
4 天前
码农翻身  ·  强烈建议尽快搞个软考证！（2025重大红利）
5 天前
十点读书会  ·  最精致的时光美学，献给热爱生活的你
8 年前
韩剧  ·  戳中你的少女心！看完这部戏不信你不心动！
7 年前
思想聚焦  ·  曲筱绡这5个特点，学会1个你都是赢家
7 年前
兰州大学学生会公共主页  ·  如何在兰大收到第一份情书
7 年前
材料人  ·  另辟蹊径：氮掺杂石墨烯\/二硫化钼\/氮掺杂石墨烯异质结的巧妙制备及其在锂离子电池中的应用
7 年前
Sov5搜索   ·   小百科   ·   今天看啥   ·   移动版
51好读 - 好文章就要读起来!