最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

KM算法学习笔记

XAMPP新闻 admin 1021浏览 0评论

二分图定义
图的顶点恰好可以分成两个集合,同一个集合内的顶点间不允许有边,处在不同集合的顶点允许有边相连。

问题分类
最大匹配问题:匈牙利算法、Hopcroft–Karp算法
最优权值匹配问题:Kuhn-Munkras算法
关键思想
增广路(augmenting path):假设目前已有一个匹配结果,存在一组未匹配定点的OD,能够找到一条路径,这条路径上匹配和未匹配的定点交替出现,称为增广路

增广路上的匹配和未匹配取反,则匹配数增加1。

KM算法
基本思想:通过引入顶标,将最优权值匹配转化为最大匹配问题。

clipboard.png

步骤1:将边权值转化为顶标/标杆,一般来讲,初始化时,X集合的元素取对应权重的最大值,Y集合的元素取0。取出满足以下条件的边,构建二分图:weight(i,j) = label(i) + label(j);该二分图称为相等子图

clipboard.png

步骤2:寻找增广路,从X0开始,找到X0Y4;在X1,找不到增广路,需要调整顶标,扩大相等子图;当找不到增广路径时,对于搜索过的路径上的XY点,设该路径上的X顶点集为S,Y顶点集为T,对所有在S中的点xi及不在T中的点yj,计算d=min{(L(xi)+L(yj)-weight(xiyj))},从S集中的X标杆中减去d,并将其加入到T集中的Y的标杆中;本例寻找增广路的过程中,访问了X1、Y4、X0三个节点,因此对应的边是X1Y0,d为2(从贪心选边的角度看,我们可以为X0选择新的边而抛弃原先的二分子图中的匹配边,也可以为X1选择新的边而抛弃原先的二分子图中的匹配边,因为我们不能同时选择X0Y4和X1Y4,因为这是一个不合法匹配,这个时候,d=min{(L(xi)+L(yj)-weight(xiyj))}的意义就在于,我们选择一条新的边,这条边将被加入匹配子图中使得匹配合法,选择这条边形成的匹配子图,将比原先的匹配子图加上这条非法边组成的非法匹配子图的权重和(如果它是合法的,它将是最大的)小最少,即权重最大了);此时再次为X1寻找增广路,得到X1Y0.

clipboard.png

步骤3:对X2寻找增广路,搜索范围如上图蓝色路径所示,找不到增广路,需要扩大相等子图;按照步骤2同一规则,会将边X0Y2、X2Y1加入,d=1.

clipboard.png

步骤4:在新的相等子图上,对X2重新寻找增广路。如果是深度优先,得到的路线是X2Y0->Y0X1->X1Y4->Y4X0->X0Y2,此时将匹配结果取反,则得到X2Y0、X1Y4、X0Y2三个匹配;如果是宽度优先,得到的匹配结果是X0Y4、X1Y0、X2Y1,如下图:

clipboard.png

Python实现

import numpy as np

# 声明数据结构
adj_matrix = build_graph() # np array with dimension N*N

# 初始化顶标
label_left = np.max(adj_matrix, axis=1) # init label for the left set
label_right = np.zeros(N) # init label for the right set

# 初始化匹配结果
match_right = np.empty(N) * np.nan

# 初始化辅助变量
visit_left = np.empty(N) * False
visit_right = np.empty(N) * False
slack_right = np.empty(N) * np.inf

# 寻找增广路,深度优先
def find_path(i):
visit_left[i] = True
for j, match_weight in enumerate(adj_matrix[i]):
if visit_right[j]: continue # 已被匹配(解决递归中的冲突)
gap = label_left[i] + label_right[j] – match_weight
if gap == 0:
# 找到可行匹配
visit_right[j] = True
if np.isnan(match_right[j]) or find_path(match_right[j]): ## j未被匹配,或虽然j已被匹配,但是j的已匹配对象有其他可选备胎
match_right[j] = i
return True
else:
# 计算变为可行匹配需要的顶标改变量
if slack_right[j] < gap: slack_right[j] = gap
return False

# KM主函数
def KM():
for i in range(N):
# 重置辅助变量
slack_right = np.empty(N) * np.inf
while True:
# 重置辅助变量
visit_left = np.empty(N) * False
visit_right = np.empty(N) * False

# 能找到可行匹配
if find_path(i): break
# 不能找到可行匹配,修改顶标
# (1)将所有在增广路中的X方点的label全部减去一个常数d
# (2)将所有在增广路中的Y方点的label全部加上一个常数d
d = np.inf
for j, slack in enumerate(slack_right):
if not visit_right[j] and slack < d:
d = slack
for k in range(N):
if visit_left[k]: label_left[k] -= d
for n in range(N):
if visit_right[n]: label_right[n] += d
res = 0
for j in range(N):
if match_right[j] >=0 and match_right[j] < N:
res += adj_matrix[match[j]][j]
return res

转载请注明:XAMPP中文组官网 » KM算法学习笔记

您必须 登录 才能发表评论!