## 匈牙利算法详解

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

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

#!/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())

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

###匈牙利算法的要点如下 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

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.

tags: 匹配,self,match,增广,prev,gt,graph,匈牙利,算法,deque,BFS,print,used,二分

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。