匈牙利算法-最大匹配

匈牙利算法-最大匹配

定义复习

匈牙利算法是求二分图的最大匹配的算法,所求的最大匹配并不一定唯一,所以本质上是一个优化问题.

有趣的理解

在网上看到一个很有意思的理解.

假设你是一个红娘,想要给左边的4个小伙子找对象,右边是4个妹子,红线表示了小伙子对某个妹子有好感,现在你的需求是如何选择使得他们成为pair的对数更多,先不必考虑左边每个人的感受.

avator

具体做法

  • step1

先把左1和右1连上,再把左2和右2连上,目前比较正常,没有冲突

  • step2

左3连的时候发现问题了,因为左3喜欢的2个妹子已经名花有主了,但是我们的目的是有最大匹配,这时候可以将左3与右1匹配,而之前与右1匹配的左1可以去和右2匹配,而之前与右2匹配的左2可以与右3进行匹配,而且这时候左边3个小伙子都找到了妹子,没有发生冲突. 这时候的结果是 (左1,右2),(左2,右3),(左3,右1)

  • step3

左4只喜欢右3,但是右3已经分好了,而且如果想按照step2的办法来商量一下发现是行不通的,比如

(左4,右3),(左2,右2), (左1,右1),但是这时候左2单身了,而且匹配数量并没有增加.(由此也可以看出最大匹配并不一定唯 一.)

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦