赞
踩
在上一篇文章中,介绍了二分图的最大匹配问题及其算法,但是分配问题和二分图最大匹配似乎关联不大,为什么要详细介绍二分图最大匹配呢? 其实如果给二分图中的边加上权重,那么这个二分图就是分配问题的图形式,如果分配问题的目标是最大值目标,那么对应的图论问题就是求二分图的最大权重匹配,具体来说:
因为分配问题大多数情况是要让总的cost最小,所以本文还是以二分图最小完美匹配作为对象进行叙述(分配的结果应该是让所有的对象都有分配值,所以要强调是完美匹配)
二分图最大匹配其实是权重都是1的特殊情况,我们可以使用搜索增广路径的算法来求解二分图最大匹配问题;那么对于更为一般的权重二分图,该方法还可以使用吗? 其实算法的核心还是和增广路径相关,不过需要在原始的权重二分图上扩充一下
需要介绍两个非常关键的算法术语:Feasible Labeling(不知道怎么用中文描述,有的资料里会称对偶变量)和Equality Graph
我们用一个例子来帮助理解:假设一个二分图的权重矩阵如下表所示:
y1 | y2 | y3 | |
---|---|---|---|
x1 | 0 | 1 | 0 |
x2 | 2 | 1 | 3 |
x3 | 0 | 1 | 2 |
用图表示:
然后:
对于一个权重二分图,我们如果设定了 f e a s i b l e l a b e l i n g feasible\ labeling feasible labeling,并得到了相应的 E q u a l i t y G r a p h Equality\ Graph Equality Graph,我们有下面这个定理:
其证明过程如下:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。