Hungarian

@AikenHong 2021
@Code: Scipy（repo）
@Reference: 匈牙利算法&KM算法

该篇笔记用来介绍匈牙利算法和KM算法(Kuhn-Munkres Algorithm)，这两个算法通常用来做目标之间的匹配问题。
常用于：多目标跟踪，和深度聚类中的标签匹配问题。

Method

这两种方法实际上解决的问题都是： 二分图的最大匹配问题；
首先需要对二分图有个基本的了解：

实际上就是将数据分为两组，各组的每一个点都去另一个组找对应的匹配，我们希望将两组中，相关的数据尽可能的准确的匹配起来。

可以想象成，是同一个数据在不同的映射下的不同表征需要做这样的匹配关系。

解决这种问题的方式就是使用匈牙利算法或者KM算法

匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法

匈牙利算法可以将二分图中的连线，看成是我们认为可能是相同的目标（不带权值），实际上就是从上到下假想成立，然后进行唯一匹配的搜索，有点像BackTrack的过程。

整体算法的成功率或者准确率实际上十分依赖与连线的准确率，对算法输出预测的准确度要求更高。