未加星标

匈牙利算法详解

字体大小 | |
[开发(python) 所属分类 开发(python) | 发布者 店小二05 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏

“匈牙利算法”最早是由匈牙利数学家D.Koning用来求矩阵中0元素的个数的一种方法,由此他证明了“矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数”。1955年由W.W.Kuhn在求解著名的指派问题时引用了这一结论, 并对具体算法做了改进,仍然称为“匈牙利算法”。

指派问题是人员调度问题中的经典问题―――m个人完成n项工作,且每个人完成每项工作的效率不一样,确定任务指派方案使得完成任务总的效率最高。本文研究最简单的指派问题,即假设任务效率一样,如何获得最大指派数目,这也是图论中的最大匹配问题。

图论中相关概念

二分图:简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交集U和V,使得每一条边都分别连接U、V中的顶点。如果存在这样的划分,则此图为一个二分图。二分图的一个等价定义是:不含有「含奇数条边的环」的图。图 1 是一个二分图。为了清晰,我们以后都把它画成图2的形式。


匈牙利算法详解

匹配:在图论中,一个「匹配」(matching)是一个边的集合,其中任意两条边都没有公共顶点。例如,图 3、图 4 中红色的边就是图 2 的匹配。


匈牙利算法详解

我们定义 匹配点、匹配边、未匹配点、非匹配边 ,它们的含义非常显然。例如图 3 中 1、4、5、7 为匹配点,其他顶点为未匹配点;1-5、4-7为匹配边,其他边为非匹配边。

最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。图 4 是一个最大匹配,它包含 4 条匹配边。

完美匹配:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。图 4 是一个完美匹配。显然,完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突)。但并非每个图都存在完美匹配。

举例来说:如下图所示,如果在某一对男孩和女孩之间存在相连的边,就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对,使得每对儿都互相喜欢呢?图论中,这就是 完美匹配 问题。如果换一个说法:最多有多少互相喜欢的男孩/女孩可以配对儿?这就是 最大匹配 问题。
匈牙利算法详解

最大匹配数:最大匹配的匹配边的数目。

最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择。最小覆盖要求用最少的点($X$集合或$Y$集合的都行)让每条边都至少和其中一个点关联。可以证明:最少的点(即覆盖数)=最大匹配数

最大独立数:选取最多的点,使任意所选两点均不相连。

最小路径覆盖数:对于一个 DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径,路径长可以为 0(即单个点)。也就是说用尽量少的不相交简单路径覆盖DAG的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个:$X$结点集中的$i$和$Y$结点集中的$i’$,如果有边$i\rightarrow j$,则在二分图中引入边$i\rightarrow j’$,设二分图最大匹配为m,则结果就是n-m。

从上述概念描述中可以得到三个定理:

定理1:最大匹配数 = 最小点覆盖数(这是 Konig 定理)

定理2:最大匹配数 = 最大独立数

定理3:最小路径覆盖数 = 顶点数 - 最大匹配数

匈牙利算法相关概念

求解最大匹配问题的一个算法是匈牙利算法,下面讲的概念都为这个算法服务。


匈牙利算法详解

交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。例如,图 5 中的一条增广路如图 6 所示(图中的匹配点均用红色标出)
匈牙利算法详解

增广路有一个重要特点:非匹配边比匹配边多一条。因此,研究增广路的意义是 改进匹配 。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边,所以这样做不会破坏匹配的性质。交换后,图中的匹配边数目比原来多了 1 条。

我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到最大匹配(这是增广路定理)。匈牙利算法正是这么做的,这也是算法的核心。在给出匈牙利算法 DFS 和 BFS 版本的代码之前,先讲一下匈牙利树。

匈牙利树一般由 BFS 构造(类似于 BFS 树)。从一个未匹配点出发运行 BFS(唯一的限制是,必须走交替路),直到不能再扩展为止。例如,由图 7,可以得到如图 8 的一棵BFS树:


匈牙利算法详解

这棵树存在一个叶子节点为非匹配点(7 号),但是匈牙利树要求所有叶子节点均为匹配点,因此这不是一棵匈牙利树。如果原图中根本不含 7 号节点,那么从 2 号节点出发就会得到一棵匈牙利树。这种情况如图 9 所示(顺便说一句,图 8 中根节点 2 到非匹配叶子节点 7 显然是一条增广路,沿这条增广路扩充后将得到一个完美匹配)。

代码实现

为了简单起见代码采用矩阵方式存储,换成邻接表也一样。下面采用两个版本,一个是DFS版本,采用递归方式,当然用栈实现也一样,另一种是BFS版本,主要用队列和prev数组。这里python中的队列虽然用list也可以轻松实现,但pop(0)实际上开销还是很大的,因此还是用链式存储结构Deque。

测试图采用图4数据。

#!/Users/Trucy/anaconda/bin/python # coding: utf-8 import timeit from collections import deque #============================================================================== # 匈牙利算法 #============================================================================== class HungarianAlgorithm(object): def __init__(self,graph): """ @graph:图的矩阵表示 """ self.graph=graph self.n=len(graph) def find(self,x): for i in range(self.n): if self.graph[x][i]==1 and not self.used[i]: self.used[i]=1#放入交替路 if self.match[i]==-1 or self.find(self.match[i])==1: self.match[i]=x self.match[x]=i print(x+1,'->',i+1) return 1 return 0 def hungarian1(self): """递归形式 """ self.match=[-1]*self.n#记录匹配情况 self.used=[False]*self.n#记录是否访问过 m=0 for i in range(self.n): if self.match[i]==-1: self.used=[False]*self.n print('开始匹配:',i+1) m+=self.find(i) return m def hungarian2(self): """循环形式 """ match=[-1]*self.n#记录匹配情况 used=[-1]*self.n#记录是否访问过 Q=deque() #设置队列 ans=0 prev=[0]*self.n #代表上一节点 for i in range(self.n): if match[i]==-1: Q.clear() Q.append(i) prev[i]=-1#设i为出发点 flag=False #未找到增广路 while len(Q)>0 and not flag: u=Q.popleft() for j in range(self.n): if not flag and self.graph[u][j]==1 and used[j]!=i: used[j]=i if match[j]!=-1: Q.append(match[j]) prev[match[j]]=u#记录点的顺序 else: flag=True d=u e=j while(d!=-1):#将原匹配的边去掉加入原来不在匹配中的边 t=match[d] match[d]=e match[e]=d d=prev[d] e=t print('mathch:',match) print('prev:',prev) print('deque',Q) if match[i]!=-1:#新增匹配边 ans+=1 return ans def do1(): graph=[(0,0,0,0,1,0,1,0), (0,0,0,0,1,0,0,0), (0,0,0,0,1,1,0,0), (0,0,0,0,0,0,1,1), (1,1,1,0,0,0,0,0), (0,0,1,0,0,0,0,0), (1,0,0,1,0,0,0,0), (0,0,0,1,0,0,0,0)] h=HungarianAlgorithm(graph) print (h.hungarian1()) def do2(): graph=[(0,0,0,0,1,0,1,0), (0,0,0,0,1,0,0,0), (0,0,0,0,1,1,0,0), (0,0,0,0,0,0,1,1), (1,1,1,0,0,0,0,0), (0,0,1,0,0,0,0,0), (1,0,0,1,0,0,0,0), (0,0,0,1,0,0,0,0)] h=HungarianAlgorithm(graph) print (h.hungarian2())

运行do1(),可以看到结果:

开始匹配: 1 1 -> 5 开始匹配: 2 1 -> 7 2 -> 5 开始匹配: 3 3 -> 6 开始匹配: 4 4 -> 8 4

首先从1开始匹配一直到4(代码中到8实际不影响,因为接下来5,6,7,8都不会进入到递归了),遍历1~8(实际上遍历5~8即可),扩展第一个增广路为(1->5),然后从2开始匹配,5是匹配点,于是找5的匹配点1,发现一条增广路(2->5->1->7),修改匹配,得到(2->5)(1->7),下面以此类推。

运行do2(),可以看到结果:

mathch: [4, -1, -1, -1, 0, -1, -1, -1] prev: [-1, 0, 0, 0, 0, 0, 0, 0] deque deque([]) mathch: [6, 4, -1, -1, 1, -1, 0, -1] prev: [1, -1, 0, 0, 0, 0, 0, 0] deque deque([]) mathch: [6, 4, 5, -1, 1, 2, 0, -1] prev: [1, 2, -1, 0, 0, 0, 0, 0] deque deque([1]) mathch: [6, 4, 5, 7, 1, 2, 0, 3] prev: [3, 2, -1, -1, 0, 0, 0, 0] deque deque([0]) 4

其中match用来保存匹配点,prev用来保存增光路非匹配点顺序,其功能相当于递归方法中的隐式栈。

###匈牙利算法的要点如下 1. 从左边第 1 个顶点开始,挑选未匹配点进行搜索,寻找增广路。 1. 如果经过一个未匹配点,说明寻找成功。更新路径信息,匹配边数 +1,停止搜索。 2. 如果一直没有找到增广路,则不再从这个点开始搜索。事实上,此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去,而不影响结果。 2. 由于找到增广路之后需要沿着路径更新匹配,所以我们需要一个结构来记录路径上的点。DFS 版本通过函数调用隐式地使用一个栈,而 BFS 版本使用 prev 数组。

性能比较

两个方法各运行一千次:

print (timeit.Timer('do1()','from __main__ import do1').timeit(1000)) print (timeit.Timer('do2()','from __main__ import do2').timeit(1000))

结果:

0.01775275500040152 0.013543492999815498

两个版本的时间复杂度均为$O(VE)$。DFS 的优点是思路清晰、代码量少,但是性能不如 BFS。测试了两种算法的性能。对于稀疏图,BFS 版本明显快于 DFS 版本;而对于稠密图两者则不相上下。在完全随机数据 9000 个顶点 4,0000 条边时前者领先后者大约 97.6%,9000 个顶点 100,0000 条边时前者领先后者 8.6%, 而达到 500,0000 条边时 BFS 仅领先 0.85%。

ref 常庭懋, 韩中庚. 用”匈牙利算法”求解一类最优化问题[J]. 信息工程大学学报, 2004, 5(1):60-62. 张云华. 论匈牙利算法在指派问题管理工作中的应用[J]. 价值工程, 2016, 35(25). Renfei Song. 二分图的最大匹配[OL]. http://www.renfei.org/blog/bipartite-matching.html,2014. RichardXG. 匈牙利算法求二分图的最大匹配[OL]. http://blog.csdn.net/xuguangsoft/article/details/7861988,2012.

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

分页:12
转载请注明
本文标题:匈牙利算法详解
本站链接:http://www.codesec.net/view/480687.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(77)