成都网站建设好,建筑施工组织设计毕业设计,大型网站有哪些用php做的,网页图片不能另存为怎么办匈牙利算法算法简介算法原理算法实现(附代码)测试算法简介下面摘用百度百科中的解释。匈牙利算法(Hungarian method)是由匈牙利数学家Edmonds于1965年提出#xff0c;因而得名。匈牙利算法是基于Hall定理中充分性证明的思想#xff0c;它是二分图匹配最常见的算法#xff0c…匈牙利算法算法简介算法原理算法实现(附代码)测试算法简介下面摘用百度百科中的解释。匈牙利算法(Hungarian method)是由匈牙利数学家Edmonds于1965年提出因而得名。匈牙利算法是基于Hall定理中充分性证明的思想它是二分图匹配最常见的算法该算法的核心就是寻找增广路径它是一种用增广路径求二分图最大匹配的算法。简单来说匈牙利算法就是为了解决匹配问题的一种算法。可以设想这样一个问题有三个工人要共同完成三件任务。每个人只能专注完成一件任务。且工人完成不同任务所需要的时间是不一样的。当然这里可以直接通过枚举的方式来遍历所有的分配方式来进行求解。但当求解的问题的维度变得比较大时这样处理就显得不太明智了。所以为了解决这一类问题匈牙利算法得以提出。算法原理算法的输入时一个代价矩阵c c其中cij c i j表示工人i在任务j上的工作时长。算法总的来说分成几步。step1将矩阵c c化为每行每列都至少有一个0的矩阵。例如输入矩阵c(1243) c ( 1 4 2 3 )首先处理行找到每行中的最小1元素如第一行中找到的是1第二行中是2。每行中所有元素都减去该最小元素得(0031) ( 0 3 0 1 )。之后处理列这里检查列发现第二列中没有0元素。故继续找到第二列总最小元素并用第二列中的元素减去该最小元素得(0020) ( 0 2 0 0 ).step2检查矩阵中是否有相互独立0的元素。也就是说能否找到与矩阵维度相同数目的0它们占据不同的行列位置。如上的例子就可以找到这样的两个零元素c11 c 11和c22 c 22。当然也有不是这种情况的例子。如[⎛⎝⎜⎜⎜⎜⎜⎜02090531086005032070620542⎞⎠⎟⎟⎟⎟⎟⎟ ( 0 5 0 2 2 2 3 0 0 0 0 10 5 7 5 9 8 0 0 4 0 6 3 6 2 ) ]如果在该步能找到独立零则算法就可在此结束。如上的例子可以输出(1122) ( 1 2 1 2 ) .表示工人1完成任务1工人2完成任务2。否则继续执行下面步骤。step3以每一个0元素为中心画十字架(即选中所有零元素所在的行元素和列元素)。找出没有被选中的元素。然后将没有被选中的元素所在的行进行标记。然后执行以下两个步骤1. 对以标记的行中的零元素所在的列进行标记。2. 对已标记的列中的零元素所在的行进行标记。重复进行上述操作直至不能再进行标记为止。可以证明没有标记的行以及标记了的列可以覆盖所有的零元素。step4对没有覆盖的元素找到里面值最小的一个。将标记了的行中的所有元素减去这个值将标记了的列中的元素加上这个值。这样的操作可以确保在未被覆盖的区域内至少产生一个0且原本的0元素不会改变。之后跳转到step2。代码传送门简要说明一下。Hungarian.m文件是主程序。两个辅助程序1. fix.m用于查找最佳分配如果答案则可在all中得到所有最佳匹配。否则all为空result中保存次最佳匹配。2. findMin.m用于找到指定下标范围内的最小元素。测试结果输入输出 输入输出
