【学习总结匈牙利算法到KM算法】

2022/2/11 22:13:23

本文主要是介绍【学习总结匈牙利算法到KM算法】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

          • 匈牙利算法概述
          • 匈牙利算法流程
          • 从匈牙利算法到KM算法
          • 小结
          • 参考

匈牙利算法概述

  网上已经存在很多介绍匈牙利算法与KM算法,但是很多都混为一谈。基本上没有进行区分开来,我也是混淆了许久。一是确实二者确实很类似,二是没有仔细分析拿来就用主义一直拖到现在????。本篇博文即为对匈牙利算法与KM算法的知识汇总与简单介绍一下,希望对各位看官有所帮助。

网上对于匈牙利算法介绍很通俗易懂的博文:趣写算法系列之–匈牙利算法重点是该文无任何公式比较容易理解匈牙利算法过程。

知乎上关于匈牙利算法的介绍与相关数学概念普及:简单理解增广路与匈牙利算法

知乎上关于匈牙利算法到KM算法介绍:从匈牙利算法到KM算法

  好了,上面引用很多匈牙利算法与KM算法介绍博文。下面该一句话总结一下:①匈牙利算法:使用增广路径寻找最大二分图匹配算法。②KM算法:解决带有权重的二分图来寻找最大匹配算法。这样就比较清晰了,KM算法是匈牙利算法拓展到具体应用层面的一种策略。

匈牙利算法流程

  按照博文趣写算法系列之–匈牙利算法所介绍的男女相亲那样,最大促成相亲对是匈牙利算法原理体现。其中这里面忽略一个问题:就是只要存在多个连线的没有任何偏倚,与谁都可以配对,不存在更喜欢一说????。

图片来源于趣写算法系列之--匈牙利算法侵权联系删除

  上述配对即通过增广路径搜索方式来求取最大二分图匹配,什么事增广路径?可能你可以看下博文简单理解增广路与匈牙利算法里面提及的概念。简单点说:就是在这些配对数中,如何最大化求取出匹配对数。可以用深度优先or广度优先搜索的方式来对其求取。【附:如果找寻到最大匹配对数,遵循先到优先原则进行配对】

我们知道,上面图片配对的话。最大能够促成3对相亲成功,可是存在一个问题就是到底是哪3对呢?有以下几种情况:

// 左边:man_1  man_2  man_3  man_4 
// 右边:women_1  women_2  women_3 women_4

// 匹配3对数

// 第一种:【man_1, women_2】 【man_2, women_3】 【man_3, women_1】
// 第二种:【man_1, women_1】 【man_2, women_2】 【man_4, women_3】
// 第三种:【man_1, women_1】 【man_3, women_2】 【man_4, women_3】
// ......

  可以看到,上面我写了几种3个配对成功情况,那么问题来了该如何选择哪一种配对方式呢?在无任何偏倚情况下,匈牙利算法遵从先到先得原则。即最先遍历到最大匹配对数之后就不在进行搜索。

  上述问题继续延伸:男女相亲总会存在更喜欢其中一方,稍微喜欢另外一个,这个是人之常情。那么我们如何在保证最大化促成相亲对数情况下,提高相亲双方的满意度呢?这时候匈牙利算法或许就无法解决了,该KM算法登场啦。

从匈牙利算法到KM算法

  上面介绍相亲如果存在男女双方对有个喜欢程度的排序,即每个连接线带有权重系数。那么我们该如何完成匹配对数呢?这个时候就该KM算法上场啦。

现在,我们对上述相亲对象之间的喜欢程度附上喜欢系数。最终会生成一个矩阵如下数值越小代表越喜欢

  上述图片基本介绍了KM算法在求解男女待权重的配对结果。或许,你已经发现一个问题?为什么最后会存在两种结果,即【step3最后生成的红色线条】那么,我们该如何选择呢?这个时候就需要GNN全局最小代价来进行选择啦。矩阵里面的喜欢系数可以理解为每个局部代价系数,最后为了获取最大的配对数可能存在多个解,这时候就采取全局代价最小的方式来进行选择。

  上图中step3是两种方案:其中第一种代价为:30。 第二种代价:35。因此,依据最小代价原则进行选择第一种配对方式。

// 第一种:【man_1, women_1】 【man_2, women_3】【man_3, women_2】
// 第二种:【man_1, women_1】 【man_4, women_3】【man_3, women_2】 

现在,我们来总结一下KM算法求解流程:

  1. 对于矩阵的每一行,该行每个元素都减去其中最小的元素。
  2. 对于矩阵的每一列,该列每个元素都减去其中最小的元素。
  3. 用最少的水平线或垂直线覆盖矩阵中所有的0。
  4. 如果线的数量等于min(N, M),【N,M代表矩阵行与列数】则找到了最优分配,算法结束。否则,进入步骤5。
  5. 找到没有被任何线覆盖的最小元素,每个没被线覆盖的行减去这个元素,每个被线覆盖的列加上这个元素,返回步骤3。

上述男女配对没有用到流程5步骤,如果想看完整的流程,请移步下面博文目标跟踪初探(DeepSORT)-- 匈牙利算法部分章节内容

小结

  上面基本上讲解了什么是匈牙利算法以及KM算法的具体应用。整体来说:匈牙利算法在求解最大分配原则基础上按照先到先得原则进行分配。KM算法在最大分配原则基础上使用全局最小代价来进行求解分配,如果全局最小代价值一致,那么按照先到先得原则进行分配获取最终结果。希望阅读后能够让你对匈牙利算法与KM算法有一定的区分。最后,若文章中内容有误,欢迎批评指正????。

参考

趣写算法系列之–匈牙利算法
简单理解增广路与匈牙利算法
从匈牙利算法到KM算法



这篇关于【学习总结匈牙利算法到KM算法】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程