趣写算法系列之--匈牙利算法
【书本上的算法往往讲得非常复杂,我和我的朋友计划用一些简单通俗的例子来描述算法的流程】
匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。
-------等等,看得头大?那么请看下面的版本:
通过数代人的努力,你终于赶上了剩男剩女的大潮,假设你是一位光荣的新世纪媒人,在你的手上有N个剩男,M个剩女,每个人都可能对多名异性有好感(惊讶-_-||暂时不考虑特殊的性取向),如果一对男女互有好感,那么你就可以把这一对撮合在一起,现在让我们无视掉所有的单相思(感觉快哭了),你拥有的大概就是下面这样一张关系图,每一条连线都表示互有好感。
本着救人一命,胜造七级浮屠的原则,你想要尽可能地撮合更多的情侣,匈牙利算法的工作模式会教你这样做:
==================================================
一: 先试着给1号男生找妹子,发现第一个和他相连的1号女生还名花无主,got it,连上一条蓝线
==================================================
二:接着给2号男生找妹子,发现第一个和他相连的2号女生名花无主,got it
==================================================
三:接下来是3号男生,很遗憾1号女生已经有主了,怎么办?
我们试着给之前1号女生匹配的男生(也就是1号男生)另外分配一个妹子。
(黄色表示这条边被临时拆掉)
与1号男生相连的第二个女生是2号女生,但是2号女生也有主了,怎么办呢?我们再试着给2号女生的原配(发火QAQ)重新找个妹子(注意这个步骤和上面是一样的,这是一个递归的过程)
此时发现2号男生还能找到3号女生,那么之前的问题迎刃而解了,回溯回去
2号男生可以找3号妹子~~~
1号男生可以找2号妹子了~~~
3号男生可以找1号妹子
所以第三步最后的结果就是:
四: 接下来是4号男生,很遗憾,按照第三步的节奏我们没法给4号男生腾出来一个妹子,我们实在是无能为力了……香吉士同学走好。
其原则大概是:有机会上,没机会创造机会也要上
【code】
bool find(int x){ int i,j; for (j=1;j<=m;j++){ //扫描每个妹子 if (line[x][j]==true && used[j]==false) //如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题,但是没有成功,所以就不用瞎费工夫了) { used[j]=1; if (girl[j]==0 || find(girl[j])) { //名花无主或者能腾出个位置来,这里使用递归 girl[j]=x; return true; } } } return false; }
在主程序我们这样做:每一步相当于我们上面描述的一二三四中的一步
for (i=1;i<=n;i++) { memset(used,0,sizeof(used)); //这个在每一步中清空 if find(i) all+=1; }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Dubbo Mesh | 阿里巴巴中间件团队在 Service Mesh 的实践和探索(附PPT)
精彩观点导读:» 我们去探索一项技术,并不会仅仅因为其先进性,而是因为我们目前遇到了一些无法解决的问题,而这项技术正好能解决这个问题。 » 所有软件最重要的使命不是满足功能要求,而是演进,从而持续成长。 » 微服务本质是对服务的拆分,微服务架构符合工程领域常用的“分而治之”范式。 近日,在Aliware Open Source•成都站-Apache Dubbo 开发者沙龙上,阿里巴巴中间件高级技术专家李云(至简)向开发者们分享了阿里巴巴中间件团队在Service Mmesh领域的探索和最新实践。本文是根据至简的现场分享所整理,为大家回顾分享中的精彩内容。 嘉宾介绍:李云(至简),阿里巴巴中间件高级技术专家,是阿里巴巴集团Service Mesh方向的重要参与者和推动者。 “阿里巴巴中间件”公众号后台发送“成都沙龙PPT”,下载全场PPT。 “
- 下一篇
直播源码怎样搭建直播系统LNMP环境——PHP配置
前面两篇内容我们聊过了直播平台搭建前需要准备的内容,一切准备就绪之后就要进入正式的搭建部署环节了,本篇就先简单介绍下LNMP环境下的PHP配置。 PHP编译安装 1.解决php安装的库依赖关系 cp-frp /usr/lib64/libjpeg.* /usr/lib cp-frp /usr/lib64/libpng* /usr/lib cp -frp /usr/lib64/libldap* /usr/lib/ echo /usr/local/mysql/lib >> /etc/ld.so.conf.d/mysql-x86_64.conf ldconfig -v 2.编译安装php tar xf php-5.6.17.tar.gz cd php-5.6.17 ./configure --prefix=/usr/local/php --with-mysql=/usr/local/mysql --with-mysqli=/usr/local/mysql/bin/mysql_config --with-iconv-dir=/usr/local --with-openssl --en...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS6,CentOS7官方镜像安装Oracle11G
- CentOS关闭SELinux安全模块
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Windows10,CentOS7,CentOS8安装Nodejs环境