匈牙利算法的简单介绍和校验(不含代码)

简介

匈牙利算法是矩阵中行列配对算法,每行和每列只有一个单位有效。比较好的应用于资源匹配。

参考论文

邱梦凯. (2019). 基于匈牙利算法的企业节假日值班优化策略. 电子世界(08), 66-67
DOI:10.19353/j.cnki.dzsj.2019.08.032

例题

有四个小姐姐,要在四天上班,每天安排一个小姐姐。小姐姐对于四天中的哪一天上班是有情绪化的反应,比如有的人周一非常非常不想上班,但是如果周一没去上班,周二也没去上班,反而周三会很想去上班。

初始矩阵

每行减去行中最小值后的结果

每列减去一列中的最小值的结果

TIPS

A1,1 A1,2 两个0构成了一个路径 A2,3 A4,3 两个0构成了一个路径(从A1,1 ~ A1,4)。一共4 * 4 的矩阵有两个路径 < 4 继续迭代,那现在如何迭代了呢
找到全局中除了覆盖的路径,的非0最小值,然后所有 未覆盖区域行减去 0.1 (个人猜测论文中可能会出现错误,比如行列交叉路径0.2 最后变为了0.3)。

被覆盖区域每列 + 0.1

最后路径分布结果


绿色,粉红,黄色,双下划线 4条路径 == 4
划分结束。

Hope is a good thing,maybe the best of things,and no good thing ever dies.----------- Andy Dufresne
原文地址:https://www.cnblogs.com/eat-too-much/p/13409628.html