带权二分图的最优匹配 Kuhn-Munkres算法 收藏.docx
版权申诉
20 浏览量
2022-05-06
19:16:08
上传
评论
收藏 21KB DOCX 举报
带权二分图的最优匹配 算法 收藏
分工问题如下：某公司有工作人员 他们去做工作 每人适合做其中的
一项或几项工作，每个人做不同的工作的效益不一样，我们需要制定一个分工方案，使公
司的总效益最大，这就是所谓最佳分配问题， 它们数学模型如下：
数学模型：
是加权完全二分图，的二分图划分为 ，； 是
工作人员 做 工作时的效益，求权最大的完备匹配，这种完备匹配称为最佳匹配。
这个问题好象比较的棘手，用穷举法的话举也举死了，效率很低。本节给出一种有效算法
为此，先引入一个定义和一个定理。
定义 映射 !，满足：任意 ∈ 任意 ∈ 成立
"
则称 #是二分图 的可行顶标；令
$% $"∈
称以 $ 为边集的 之生成子图为相等子图，记为
可行顶标是存在的，例如
&' (∈
∈
定理 的完备匹配即为 的最佳匹配。
证：设 )是 的一个完备匹配，因 是 的生成子图，故 )也是 的完备匹配。)中
的边之端点集合含 的每个顶点恰一次，所以
*)++# )# ∈ ∈
另一方面，若 是 中任意一个完备匹配，则
*+,+# # ∈ ∈
所以
*)*，
即 )是最佳匹配，证毕。
定理 告知，欲求二分图的最佳匹配，只需用匈牙利算法求取其相等子图的完备匹配；问
题是，当 中无完备匹配时怎么办？ 和 ' 给出修改顶标的一个算法，使新的相
等子图的最大匹配逐渐扩大，最后出现相等子图的完备匹配。
' 算法：
选定初始的可行顶标 确定 在 中选取一个匹配 。
中顶皆被 许配，止， 即为最佳匹配；否则，取 中未被 许配的顶 令 -.
为空。
若 /-真包含 .，转0；若 /-.，取
'&" - .∈ ∈
#'# -(∈
##"'# .(∈
#其它。
。
0选 /-. 中一顶 若 已被 许配，且 1 ∈ 则 -- 1.. ∪ ∪ 转；否则，取 中
资源评论
