首页 > 代码库 > 从匈牙利算法到Kuhn-Munkres算法

从匈牙利算法到Kuhn-Munkres算法

    匈牙利算法要解决的是这样的问题,比如一群男生女生,男生是否有缘可以跟自己喜欢的人在一起。

当然我们简化成集合符号A和B, A和B的大小可以不同,我们只想知道最后按照喜欢的人在一起的话,最多有几对。

    匈牙利算法从0开始构建匹配的可能性。如果男生Ai喜欢女生Bj而且女生Bj未匹配,那么她当然可以跟男生Ai在一起了。

但是不要慌,后面的情况还可能变化,Ai可能Bj+1在一起,但是我们保证结果是每次都比原来的成功数要大的。

    匈牙利算法当然是解决图论的问题,这里不用A,B了——X和Y两个

    从X开始,每次找到一个未配对的点u

    抽象的说,是我们在X这边保存了已经访问过的点S,在Y这边类似有T,从u点开始S和T都不断增大,每次只增大1,增大

的规则是u的邻接点y如果已经匹配z,就把y加到T,z加到S,下一步的操作,是换个u, 再将T中没有访问过的点再次考查

一遍。如果y没有匹配,那正好,根据你的访问规则,这个时候u和y肯定可以配对的,这样就可以增加配对了。

    我们的工作是为了让配对的个数越来越多,直到最后不能再配对。不能配对的判定就是Hall定理,S的邻接点刚好是T。

    由于这个问题实在太过常见,以至于很多人还是像我10分钟前想的例子一样老掉牙。我们还是想个其他的抽象吧。

    可能有人会希望说我们可以改成公司面试应聘者,多个公司跟多个应聘者匹配啊。对哦,前提是你们不要拿了offer就跑掉了。

 对了你有没有想到前面说的是男生喜欢女生?如果是这样的话说明什么?我们忽略了方向。所以这个也是一厢情愿的说。

 好了另外一个例子,如果东南亚n国希望出口椰子岛中国各y省,但是一个省只能跟一国签约(现实中没有的)。这个也是

一种问题。那好的,我们现在定个价格,让总的价格最大(喂喂喂),这不是对我们来说的,是对东南亚各国来说的。

 这个就是可以抽象成Kuhn-Munkres算法了。

 对我来说这个问题比较好理解,但是算法比较难证明。看起来就是一个算法的问题。

 我们要设计一个给X,Y标号的函数l,比如 l(x) = 1,然后根据这个函数再多次应用匈牙利算法——多次是感觉得多大?

 当然,这个函数前人已经设计好了。在每次迭代的时候,我们要根据w(xy)跟l(x)+l(y)的关系得到一个生成子图G(就是满足条件的x和y和这些边),然后找最大匹配。当我们经过很多次的匈牙利算法就可以得到最终的结果了。

 文章需要配图吗?我随便写的。先这样吧。

    关于匈牙利算法,维基百科有很好的解释,离散数学的课本一般也有介绍。另外Byvoid也有说过。

从匈牙利算法到Kuhn-Munkres算法