文档章节

数学:匈牙利算法

pricker
 pricker
发布于 2015/09/12 21:54
字数 418
阅读 279
收藏 12

匈牙利算法:它由匈牙利数学家Edmonds于1965年提出,因而得名。此算法的核心就是寻找增广路径,通过增广路径来求二分图最大匹配的一种算法。

   通过这个图片来讲述一下。黑色代表A\B\C\D四只小狗,红色代表四种口味的骨头,每一条线表示的是小狗喜欢吃这个口味的骨头。

我们按照顺序给小狗们分配骨头,先给A分配,很明显a无人占用并且小A狗很喜欢,分配,博主最喜欢成人之美。(????)

现在给小B狗分配,小B喜欢b,前提b无人占用并且小B心仪很久,又成全一只小狗,哇哈哈~~

轮到小C狗了,小C等了好久了,但是小C喜欢的骨头全都被占了,好可怜有木有,但是没关系,我们想办法来帮助他。如下图。

 

通过这张图,我们可以很清晰的知道,我们把A的先拿掉,但是还是要给找一个,不然岂不是太偏心,给A找到b,但是b被占了,同理,也先拿掉,这样A满足了,在给B继续找, 这样我们就找到c,ok大家都可以找到后备胎了,那么小C可以吃a!!!同理对d一样,但是发现如果满足d,其他的都会被破坏,综上,得到最大的匹配值为3。

 

匈牙利算法的流程就是上述的方案。

 

http://blog.csdn.net/dark_scope/article/details/8880547  这个地址有精确描述,附加代码

© 著作权归作者所有

pricker
粉丝 7
博文 56
码字总数 33145
作品 0
渭南
私信 提问
读《思维的乐趣matrix67数学笔记》

今天是我第一次听说这个故事。 1933 年,匈牙利数学家 George Szekeres 还只有 22 岁。那时,他常常和朋友们在匈牙利的首都布达佩斯讨论数学。这群人里面还有同样生于匈牙利的数学怪才——P...

pricker
2015/09/24
73
0
全球程序员编程水平排行榜TOP50,中国排名第一

导读:我们已经有了世界上最棒的程序员,俄罗斯和东欧人才崛起,网络安全受冷 哪个国家的程序员水平最高?这个容易引发弹幕混战的问题可不好回答。最近软件工程师水平测定平台HackRank发起了...

达尔文
2016/09/15
12.8K
38
【算法篇】二分图匹配之匈牙利算法

二分图匹配,自然要先从定义入手,那么二分图是什么呢? 二分图: 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图...

沧海无雨
2018/07/26
0
0
二分图匹配算法(最大流匈牙利)

二分图匹配 相关概念 无向二分图(G(Ubigcup V,E)):U是一个顶点集合,V是另一个顶点集合,对于一个集合内的点无边直接相连,而对于不同集合的点可以连边,即((u,v)in E)。 匹配:两两不含公共...

小张人
08/08
0
0
【I'm Telling the Truth】【HDU - 3729】 【匈牙利算法,DFS】

思路 题意:该题主要说几个同学分别说出自己的名次所处区间,最后输出可能存在的未说谎的人数及对应的学生编号,而且要求字典序最大。 思路:刚刚接触匈牙利算法,了解的还不太清楚,附一个专...

KeepZ
08/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
38分钟前
3
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
41分钟前
3
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0
JAVA 利用时间戳来判断TOKEN是否过期

import java.time.Instant;import java.time.LocalDateTime;import java.time.ZoneId;import java.time.ZoneOffset;import java.time.format.DateTimeFormatter;/** * @descri......

huangkejie
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部