目录
一、匈牙利算法
1、算法背景及思想
匈牙利算法，是基于Hall定理中充分性证明的思想，它是
部图匹配最常见的算法
，该算法的核心就是寻找增广路径，由匈牙利数学家Edmonds于1965年提出，因而得名。
匈牙利算法（Hungarian Algorithm）与KM算法（Kuhn-Munkres Algorithm）做多目标跟踪很容易在论文中见到的两种算法。他们都是用来解决多目标跟踪中的数据关联问题。
上述利用增广路找最大匹配的算法，就叫做匈牙利算法。
2、最大匹配
结合情侣配对问题，男生女生之间互生情愫的有很多，甚至
有的人对多个人都有意向
，因此潜在的情侣组合方式有很多种。所谓的“任意两条边都不依附于同一个顶点”，意思就是只要我们撮合的时候，不要给某个人安排两个对象就行。作为牵线人，我们可以撮合一对，也可以撮合两对，这样
每一种撮合方式，都叫一个匹配
。撮合成功的这些情侣就是所谓的子图M。
按照上面的匹配方式，我们既不能把没有意向的两个人撮合在一起，有的人又对多个人有意向，因此可以花一点心思，尽可能地协调一下大家的意向，做到多撮合成功几对。这样，成功撮合的情侣最多的这种撮合方式，就叫最大匹配。
3、最优匹配/完美匹配
解释：如果非常幸运，在我们的安排下，
每个人都找到了自己心仪的对象
。这种撮合方式，叫做最优匹配或完美匹配。
4、增广路径
（非匹配边） (匹配边) (非匹配边)
B————–a—————-A—————–c
B和c都是
没有被匹配过
的点，而它又是这条交替路的起点和终点。这条交替路就是增广路。
5、代码实现
匈牙利算法有一个很明显的问题，按它的思路找到的最大匹配往往不是我们心中的最优。匈牙利算法
将每个匹配对象的地位视为相同
，在这个前提下求解最大匹配。这个和我们研究的多目标跟踪问题有些不合，因为每个匹配对象不可能是同等地位的，总有一个真实目标是我们要找的最佳匹配，而这个
真实目标应该拥有更高的权重
，在此基础上匹配的结果才能更贴近真实情况。
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;
}
class graph:
def __init__(self,gi,bo): # 输入二部图两个顶点集合的数目，每个集合的顶点均用1, ... , n表示
self.numg=gi # 女孩数量
self.numb=bo # 男孩数量
self.boy={i:[]for i in range(1,bo+1)} # 男孩的可连接对象，建图
self.viag=[0 for i in range(gi+1)] # 记录当前匹配女孩的对象
self.use=[0 for i in range(gi+1)] # 检查女孩是否被搜索过
def add(self,u,v):
self.boy[v].append(u)
def find(self,j): # 寻找 j 男孩起始的增广路
if j==0:
return 1
for i in self.boy[j]:
if self.use[i]==0: # 女孩没有被搜索过
self.use[i]=1
if self.find(self.viag[i]): # 检查 j 匹配女孩后，女孩原男友是否有其它的女友，有则表示存在增广路
self.viag[i]=j
return 1
return 0
def Hungarian(self):
sum=0
for i in range(1,self.numb+1): # 检查每个男孩是否能找到女有
self.use = [0 for i in range(self.numg + 1)] # 初始化为0
if self.find(i):
sum+=1
return sum,self.viag[1:]
if __name__=="__main__":
n,girlnum,boynum = map(int, input().split())
dic = graph(girlnum,boynum)
for i in range(n):
a, b = map(int, input().split())
dic.add(a,b)
print(dic.Hungarian())
6、匈牙利算法总结
6.1、深度优先
每个点从另一个集合里挑对象，没冲突的话就先安排上，
要是冲突了就用增广路径重新匹配
。重复上述思路，直到所有的点都找到对象，或者找不到对象也找不到增广路。
上述是深度优先匈牙利算法。就是冲突了立刻用增广路来解决。
6.2、 广度优先
另外一种是广度优先匈牙利算法。思路是，冲突了就换一个心仪对象，
看另一个心仪对象是不是也配对了，要是都配对了，再用增广路来解决
。
广度优先的流程是这样的：
（1）A和a连上。
（2）B也想连a，但是a被连了，
就找下一个心仪对象b
。
（3）b没有被连上，B和b就连在一起。
（4）轮到C的时候，C找心仪对象c。
（5）c也没被连上，所以C和c连一起。
二、KM算法思想及局限性
KM算法解决的是带权二分图的最优匹配问题。
匈牙利算法得到的最大匹配并不是唯一的，预设匹配边、或者匹配顺序不同等，都可能会
导致有多种最大匹配情况
，所以有一种替代KM算法的想法是，我们只需要用匈牙利算法找到所有的最大匹配，比较每个最大匹配的权重，再
选出最大权重的最优匹配
即可得到更贴近真实情况的匹配结果。但这种方法时间复杂度较高，会随着目标数越来越多，消耗的时间大大增加，实际使用中并不推荐。
代码示例
1、定义KM方法类
import numpy as np
class KM_Algorithm_4:
def __init__(self, Bipartite_Graph):
self.Bipartite_Graph = Bipartite_Graph
# 左右结点数量记录
self.left = self.Bipartite_Graph.shape[0] # 以左边为主
# print(self.Bipartite_Graph)
# print(self.Bipartite_Graph[0])
self.right_true = self.Bipartite_Graph.shape[1]
self.right = self.Bipartite_Graph.shape[1] + self.left
self.reshape_graph()
# 初始化顶标
self.label_left = np.max(self.Bipartite_Graph, axis=1) # 设置左边顶标为权重最大值（每行的最大值）
self.label_right = np.zeros(self.right) # 右边集合的顶标设置为0
# 初始化辅助变量——是否已匹配
self.visit_left = np.zeros(self.left, dtype=bool)
self.visit_right = np.zeros(self.right, dtype=bool)
# 初始化右边的匹配结果.如果已匹配就会对应匹配结果
self.match_right = np.empty(self.right) * np.nan
# 用inc记录需要减去的权值d，不断取最小值故初始化为较大值。权值都为负数，应该不用很大也行
self.inc = 1000*1000*1000
self.fail_boy = list() # 每次匹配重新创建一个二分图匹配对象，所以这个也不用手动重置了
def reshape_graph(self):
new = np.ones((self.left, self.left)) * 0
self.Bipartite_Graph = np.column_stack((self.Bipartite_Graph, new))
# print(self.Bipartite_Graph)
def match(self, boy):
# print("---------------我是boy%d----------------------" % boy)
boy = int(boy)
# 记录下这个boy已经被寻找
self.visit_left[boy] = True
for girl in range(self.right):
# 如果这个女生还没访问过
if not self.visit_right[girl] and self.Bipartite_Graph[boy][girl] >= 0: # 女孩仍未匹配并且男女之间存在匹配的可能性(不可匹配的点设置为负数，取反后变正数,故正数不可取)
gap = self.label_left[boy] + self.label_right[girl] - self.Bipartite_Graph[boy][girl] # gap也不会取到不能匹配的那条边
if gap == 0: # 差值为0，是可行的替换。所以可以直接尝试替换。后面不行再去将这个一起减去gap。这个列表是记录希望匹配的
self.visit_right[girl] = True
# 女生未被匹配，或虽然已被匹配，但是已匹配对象(男生)有其他可选备胎。这里那些是否已访问的列表不需要重置，因为不改变前面的尝试匹配
if np.isnan(self.match_right[girl]) or self.match(self.match_right[girl]):
self.match_right[girl] = boy
# print(self.match_right)
# 递归匹配，匹配成功
return 1
# 找到权值最小的差距
elif self.inc > gap:
self.inc = gap # 等于0的gap不会存在这，所以只要存在可能匹配的情况，gap就不会等于原来的inc
return 0
def Kuh_Munkras(self):
self.match_right = np.empty(self.right) * np.nan
# 寻找最优匹配
for man in range(self.left):
while True:
self.inc = 1000*1000 # the minimum gap
self.reset() # 每次寻找过的路径，所有要重置一下
# 可找到可行匹配
if self.match(man):
break
# 不能找到可行匹配
# (1)将所有在增广路中的boy方点的label全部减去最小常数
# (2)将所有在增广路中的girl方点的label全部加上最小常数
for k in range(self.left):
if self.visit_left[k]:
self.label_left[k] -= self.inc
for n in range(self.right):
if self.visit_right[n]:
self.label_right[n] += self.inc
return self.fail_boy
def calculateSum(self):
sum = 0
boys_girls = []
self.fail_boy = [i for i in range(self.left)]
for i in range(self.right_true):
if not np.isnan(self.match_right[i]):
sum += self.Bipartite_Graph[int(self.match_right[i])][i]
boy_girl = (int(self.match_right[i]), i)
boys_girls.append(boy_girl)
self.fail_boy.remove(int(self.match_right[i]))
print("最短路径：", sum)
return boys_girls, self.fail_boy
def getResult(self):
return self.match_right
def reset(self):
self.visit_left = np.zeros(self.left, dtype=bool)
self.visit_right = np.zeros(self.right, dtype=bool)
2、定义权重数值，执行主函数
# 定义权重数值
def data():
graph = [[8,6,-1,-1],
[-1,3,9,-1],
[9,8,-1,-1],
[-1,-1,2,-1]]
#print(graph)
km = KM_Algorithm_4(np.array(graph))
km.Kuh_Munkras() # 匹配
boys_girls, fail_boys = km.calculateSum() # 匹配结果元组,以及失败的男孩们
print("匹配男女列表", boys_girls)
print("失败男孩列表", fail_boys)
if __name__ == '__main__':
data()
参考文献
https://blog.csdn.net/dark_scope/article/details/8880547
https://zhuanlan.zhihu.com/p/208596378
https://aistudio.baidu.com/aistudio/projectdetail/2040378