Skip to content

求最大权二分匹配的KM算法

最大权二分匹配问题就是给二分图的每条边一个权值,选择若干不相交的边,得到的总权值最大。解决这个问题可以用KM算法。理解KM算法需要首先理解“可行顶标”的概念。可行顶标是指关于二分图两边的每个点的一个值lx[i]或ly[j],保证对于每条边w[i][j]都有lx[i]+ly[j]-w[i][j]>=0。如果所有满足lx[i]+ly[j]==w[i][j]的边组成的导出子图中存在一个完美匹配,那么这个完美匹配肯定就是原图中的最大权匹配。理由很简单:这个匹配的权值之和恰等于所有顶标的和,由于上面的那个不等式,另外的任何匹配方案的权值和都不会大于所有顶标的和。

但问题是,对于当前的顶标的导出子图并不一定存在完美匹配。这时,可以用某种方法对顶标进行调整。调整的方法是:根据最后一次不成功的寻找交错路的DFS,取所有i被访问到而j没被访问到的边(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。将交错树中的所有左端点的顶标减小d,右端点的顶标增加d。经过这样的调整以后:原本在导出子图里面的边,两边的顶标都变了,不等式的等号仍然成立,仍然在导出子图里面;原本不在导出子图里面的边,它的左端点的顶标减小了,右端点的顶标没有变,而且由于d的定义,不等式仍然成立,所以他就可能进入了导出子图里。

初始时随便指定一个可行顶标,比如说lx[i]=max{w[i][j]|j是右边的点},ly[i]=0。然后对每个顶点进行类似Hungary算法的find过程,如果某次find没有成功,则按照这次find访问到的点对可行顶标进行上述调整。这样就可以逐步找到完美匹配了。

值得注意的一点是,按照上述d的定义去求d的话需要O(N^2)的时间,因为d需要被求O(N^2)次,这就成了算法的瓶颈。可以这样优化:设slack[j]表示右边的点j的所有不在导出子图的边对应的lx[i]+ly[j]-w[i][j]的最小值,在find过程中,若某条边不在导出子图中就用它对相应的slack值进行更新。然后求d只要用O(N)的时间找到slack中的最小值就可以了。

如果是求最小权匹配,只需要把那个不等式反一下就行了。算法需要作出的改变是:lx的初值为所有临界边中的最小值,find中t反号。

示例程序(Ural 1076):
ural1076.cpp

8 Comments

  1. 王寅 wrote:

    O(n^4)的其实实际运用中效果也不错……

    Wednesday, July 11, 2007 at 21:01 | Permalink
  2. biran007 wrote:

    不好意思……问下你的示例程序(Ural 1076)里面
    if(visy[i])
    ly[i]+=d;
    else
    slack[i]-=d;
    这个else是做什么的?

    Sunday, April 19, 2009 at 18:16 | Permalink
  3. DMKaplony wrote:

    “如果是求最小权匹配,只需要把那个不等式反一下就行了。算法需要作出的改变是:lx的初值为所有临界边中的最小值,find中t反号。”

    这个还不够吧?
    应该:
    for(int i=0;i<N;++i){
    if(visx[i])
    lx[i]-=d;//这里应该变成+
    }
    for(int i=0;i<N;++i){
    if(visy[i])
    ly[i]+=d;//这里变成-
    else
    slack[i]-=d;//这里不变
    对么?
    谢谢你的文章,让我学会了KM,O(∩_∩)O~。
    :-)

    Saturday, April 10, 2010 at 17:42 | Permalink
  4. ymfoi wrote:

    回biran007,那个else后面的是因为Lx[i]变小了d 而slack[j] = max{Lx[i] + Ly[j] -w[i][j]} 所以slack[j](j不属于T)受影响也要减小d

    Friday, August 13, 2010 at 14:36 | Permalink
  5. taptree wrote:

    Could you please tell me, what if |X|!=|Y|? Will this algorithm still work? Or, I should add some vertaxs to make |X|=|Y|, then use KM algorithm? Many thx.(You can use Chinese to reply me)

    Monday, May 20, 2013 at 17:53 | Permalink
  6. https://www. wrote:

    In another ethnic realm, Louis, Mo. Your funeral katy landscaping
    home eventually decided to take into account.
    Now-a-days it is isolated from the hospice got here,” I’m going to be katy landscaping disposed of. There may be more than one source.

    Thursday, July 24, 2014 at 13:34 | Permalink
  7. 追梦 wrote:

    为什么取所有i被访问到而j没被访问到的边(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。
    请大神指教

    Monday, October 6, 2014 at 16:07 | Permalink
  8. visitor wrote:

    那个链接打不开了。。。

    Friday, September 4, 2015 at 22:34 | Permalink

5 Trackbacks/Pingbacks

  1. [...] 我们可以使用KM算法实现求二分图的最佳匹配。方法我不再赘述,可以参考tianyi的讲解。KM算法可以实现为O(N^3)。 [...]

  2. URAL 1076. Trash | `Alice Scarlett 的绝妙小屋 ., on Friday, August 20, 2010 at 19:14

    [...] URAL 1076. Trash 求最大权二分匹配的KM算法 – 翼若垂天之云 [...]

  3. [...] 我们可以使用KM算法实现求二分图的最佳匹配。方法我不再赘述,可以参考tianyi的讲解。KM算法可以实现为O(N^3)。 [...]

  4. […] 我们可以使用KM算法实现求二分图的最佳匹配。可以参考tianyi的讲解。KM算法可以实现为O(N^3)。 […]

  5. 关于二分图的最大权匹配 | conlan on Sunday, December 14, 2014 at 00:02

    […] http://cuitianyi.com/blog/%E6%B1%82%E6%9C%80%E5%A4%A7%E6%9D%83%E4%BA%8C%E5%88%86%E5%8C%B9%E9%85%8D%E&#8230; […]

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*