分配问题及匈牙利算法

【算法题】任务分配问题---匈⽛利算法⼀、问题描述问题描述：N个⼈分配N项任务，⼀个⼈只能分配⼀项任务，⼀项任务只能分配给⼀个⼈，将⼀项任务分配给⼀个⼈是需要⽀付报酬，如何分配任务，保证⽀付的报酬总数最⼩。

问题数学描述：⼆、实例分析---穷举法在讲将匈⽛利算法解决任务问题之前，先分析⼏个具体实例。

以3个⼯作⼈员和3项任务为实例，下图为薪酬图表和根据薪酬图表所得的cost矩阵。

利⽤最简单的⽅法(穷举法)进⾏求解，计算出所有分配情况的总薪酬开销，然后求最⼩值。

total_cost1 = 250 + 600 + 250 = 1100; x00 = 1,x11 = 1,x22 = 1;total_cost2 = 250 + 350 + 400 = 1000; x00 = 1,x12 = 1,x21 = 1;total_cost3 = 400 + 400 + 250 = 1050; x01 = 1,x10 = 1,x22 = 1;total_cost4 = 400 + 350 + 200 = 950; x01 = 1,x12 = 1,x20 = 1; //最优分配total_cost5 = 350 + 400 + 400 = 1150; x02 = 1,x10 = 1,x21 = 1;total_cost6 = 350 + 600 + 250 = 1150; x02 = 1,x11 = 1,x22 = 1;对于任务数和⼈员数较少时，可利⽤穷举法计算结果。

若将N任务分配给N个⼈员，其包含的所有分配情况数⽬为N!，N增⼤时，穷举法将难以完成任务。

三、匈⽛利算法下⾯简要介绍匈⽛利算法。

其基本的理论基础是针对cost矩阵，将cost矩阵的⼀⾏或⼀列数据加上或减去⼀个数，其最优任务分配求解问题不变。

算法的基本步骤如下：四、实例分析---匈⽛利算法下⾯结合具体实例，分析匈⽛利算法如何解决任务分配问题。

以N = 4为实例，下图为cost列表和cost矩阵。

匈牙利算法求解原理的应用什么是匈牙利算法匈牙利算法是一种用于解决二分图最大匹配问题的算法。

所谓二分图，就是一个节点集合可以分为两个不相交的子集，而且每个子集内的节点之间不存在边。

在二分图中，最大匹配问题就是寻找最大的边集合，使得每个节点都和边集合中的某条边相邻接。

匈牙利算法的原理是通过增广路径的方法来求解最大匹配问题。

其中增广路径是指在匹配图中的一条未被匹配的边交替经过未被匹配的节点，最终到达另一个未被匹配的节点的路径。

匈牙利算法的应用匈牙利算法有许多实际应用场景。

以下列举了一些典型的应用案例：1.婚姻匹配问题：假设有n个男人和n个女人，每个人都有一个倾向表，表明他们对各种婚姻选择的偏好程度。

那么如何进行匹配，使得每个人都得到一个满意度最高的选择，同时保证没有不合适的匹配？这就可以使用匈牙利算法进行求解。

2.任务分配问题：假设有m个任务和n个工人，每个任务对于每个工人都有不同的技能要求和报酬。

如何将任务分配给工人，使得任务总报酬最大化，并满足每个任务的要求？这也可以使用匈牙利算法进行求解。

3.运输问题：在某个地区有n个供应点和n个需求点，以及不同供应点到需求点之间的运输成本。

那么如何选择合适的运输方案，使得总运输成本最小？同样可以使用匈牙利算法进行求解。

4.社交网络匹配问题：在一个社交网络中，每个人都有一定的朋友圈和交往偏好。

如何将这些人进行匹配，使得每个人都能够找到最适合的交往对象？匈牙利算法也可以应用于这种情况。

匈牙利算法的实现步骤下面是匈牙利算法的具体实现步骤：1.在匹配图中选择一个未匹配的顶点作为起始点，并为其标记为已访问。

2.对于当前顶点的每一个邻接顶点，如果该邻接顶点未被匹配，则找到一条增广路径。

如果该邻接顶点已被匹配，但可以通过其他路径找到一条增广路径，则将该邻接顶点的匹配权转移到当前顶点的匹配边上。

3.继续选择下一个未匹配的顶点，重复步骤2，直到无法找到增广路径为止。

4.返回当前匹配图的最大匹配。

分配问题与Hungarian算法分配问题与Hungarian算法分配问题指派问题匈⽛利算法匈⽛利⽅法是⼀种能够在多项式时间内解决分配问题(assignment problem)的组合优化算法。

它由Harold Kuhn 与1955年发展并提出，由于该算法很⼤程度上依赖于先前两位匈⽛利数学家:Denes Konig 和 Jeno Egervary,所以被命名为“匈⽛利⽅法”。

1957年James Munkres重新审视了这个⽅法，证明发现该⽅法是严格polynomial的，所以之后该⽅法也被称为Kuhn-Munkres 算法或者Munkres分配算法。

原始的匈⽛利算法的时间复杂度是,然⽽之后Edmonds和Karp，以及Tomizawa独⽴发现经过⼀定的修改，该算法能改达到的时间复杂度。

Ford和Fulkerson将该⽅法扩展到⼀般运输问题的求解上。

2006年，研究发现Carl Custav Jacobi在19实际就解决了assignment问题，并且在其逝世后的1890年求解过程被以拉丁语形式发表。

指派问题匈⽛利法解决的指派问题应该具有两个约束条件workes 和tasks的数⽬应该相同，即o2o问题。

求解的是最⼩化问题，如⼯作时间的最⼩化、费⽤的最⼩化等等指派问题⽰例：有三个workers: Jim, Steve和Alan，现在有3个⼯作：clean the bathroom, sweep the floors和wash the windows需要交给这三个⼈，每个⼈只能完成⼀个任务，对应的cost matrix如下---Clean bathroom Sweep floors Wash windowsJim$2$3$3Steve$3$2$3Alan$3$3$2那么如何分配任务是开销最⼩就是⼀个指派问题匈⽛利法步骤问题： 假定某单位有甲、⼄、丙、丁、戊五个员⼯，现需要完成A、B、C、D、E五项任务，每个员⼯完成某项任务的时间如下图所⽰，应该如何分配任务，才能保证完成任务所需要的时间开销最⼩？1476015762594.jpg解：1. 写出系数矩阵2. 更新系数矩阵，使系数矩阵的每⼀⾏每⼀列都减去该⾏该列的最⼩值，保证每⼀⾏每⼀列都有0元素出现,参见定理2.3. 选择只有⼀个0元素的⾏或列将该0元素标注为独⽴0元素，并将该0元素所在的列或⾏中0元素划掉，直⾄找不到满⾜条件的⾏或列，需要注意的是在循环时，划掉的0元素不再视为0元素。

分配问题匈牙利算法的Matlab实现function [x,fVal]=Hungary(C)% 输出参数：% x--Decision Varables, n*n矩阵% fval--Objective function Value% 输入参数:% C--效益矩阵c=C; %将效益矩阵暂存入c,以下的操作将针对c进行[iMatrixRow,iMatrixCol]=size(c);%求约化矩阵：将效益矩阵的每行每列各减去其最小值c=c-repmat(min(c,[],2),1,iMatrixCol);c=c-repmat(min(c,[],1),iMatrixRow,1);%进行试分配，求出初始分配方案while 1%对所有零元素均已画⊙(inf)或画×(-inf)c=CircleOrCross(c);%划线，决定覆盖所有零元素的最少直线数iIndepentZeroNum=find(c==inf);if length(iIndepentZeroNum)==iMatrixRowbreak;else[Row,Col]=line(c);end%查找没有被直线段覆盖的元素中的最小元素，并存入fMininumVlaue中fMininumVlaue=inf;for i=1:iMatrixRowfor j=1:iMatrixColif Row(i)~=1 && Col(j)~=1 && c(i,j)<fmininumvlaue fMininumVlaue=c(i,j);endendend%修改约化矩阵中的相关数据for i=1:iMatrixRowfor j=1:iMatrixColif c(i,j)==inf||c(i,j)==-infc(i,j)=0;endif Row(i)~=1 && Col(j)~=1c(i,j)=c(i,j)-fMininumVlaue;endif Row(i)==1 && Col(j)==1c(i,j)=c(i,j)+fMininumVlaue;endendendend%返回分配方案及目标函数值fVal=0;for i=1:iMatrixRowfor j=1:iMatrixColif c(i,j)==infx(i,j)=1;fVal=fVal+C(i,j); elsex(i,j)=0;endendend</fmininumvlaue。

数学建模匈牙利算法数学建模匈牙利算法是一种用于解决分配问题的经典算法，它可以在多项式时间内找到最优解。

匈牙利算法最初是为了解决分配问题而设计的，但现在已经扩展到了其他领域，例如机器学习、优化理论和图论等。

分配问题是一种组合优化问题，它通常涉及将一组资源分配给一组人或任务，以最小化总成本或最大化总效益。

分配问题的关键是要找到一种分配方式，使得每个任务或人得到的资源数量是合理的，并且总成本或总效益是最大的。

匈牙利算法的核心思想是通过在任务或人之间添加虚拟任务或人来简化分配问题。

这些虚拟任务或人可以看作是“桥”，它们可以将不同的任务或人连接起来，从而使得分配问题的解更加简单。

1.初始化：将每个任务或人表示为一个节点，并将所有节点放在一个图中。

2.寻找增广路径：通过使用DFS或BFS等搜索算法，在图中寻找一个增广路径。

增广路径是指一条路径，它连接所有节点，并且可以通过添加虚拟任务或人来扩展。

3.扩展增广路径：在找到增广路径后，可以将其扩展成一个覆盖集，即一个包含所有节点的集合，且每个节点恰好被访问一次。

4.重复步骤2和3：继续寻找增广路径并扩展覆盖集，直到找不到增广路径为止。

5.输出结果：输出最终的覆盖集作为分配问题的解。

匈牙利算法的时间复杂度取决于搜索算法的时间复杂度。

如果使用DFS作为搜索算法，则时间复杂度为O(n^3)，其中n是节点数。

如果使用BFS作为搜索算法，则时间复杂度为O(n^2)。

在实际应用中，匈牙利算法可以与其他优化技术结合使用，例如遗传算法、模拟退火和蚁群优化等。

这些技术可以加速搜索过程，并提高算法的效率和可靠性。

此外，匈牙利算法还可以用于解决其他类型的问题，例如工作调度、资源分配和车辆路径问题等。

这些问题都可以通过添加虚拟任务或人来简化，并使用匈牙利算法找到最优解。

总之，数学建模匈牙利算法是一种非常有效的分配问题求解算法，它可以在多项式时间内找到最优解。

通过与其他优化技术的结合使用，它可以广泛应用于各种实际应用场景中，为解决复杂的优化问题提供有效的解决方案。