匈牙利解法的步骤

指派问题的匈牙利法求解步骤：

1) 变换指派问题的系数矩阵(c ij)为(b ij)，使在(b ij)的各行各列中都出现0元素，即

从(cij)的每行元素都减去该行的最小元素；

再从所得新系数矩阵的每列元素中减去该列的最小元素。

2) 进行试指派，以寻求最优解。

在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0

元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。

找独立0元素，常用的步骤为：

从只有一个0元素的行开始，给该行中的0元素加圈，记作◎。然后划去◎所

在列的其它0元素，记作?；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。

从只有一个0元素的列开始（画?的不计在内），给该列中的0元素加圈，记作◎；

然后划去◎所在行的0元素，记作?，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。

若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所

在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让”

选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。

若◎元素的数目m 等于矩阵的阶数n（即：m＝n），那么这指派问题的最优解已

得到。若m < n, 则转入下一步。

3) 用最少的直线通过所有0元素。其方法：

对没有◎的行打“√”；

对已打“√”的行中所有含?元素的列打“√”；

再对打有“√”的列中含◎元素的行打“√”；

重复①、②直到得不出新的打√号的行、列为止；

对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最

少直线数l 。

注：l 应等于m，若不相等，说明试指派过程有误，回到第2步，另行试指派；若

l＝m < n，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到n 个独立的0元素，为此转第4步。

4) 变换矩阵(b ij)以增加0元素

在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这

个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。

人力资源级匈牙利法解题思路

匈牙利法 假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一定的生产技术组织条件下，完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工作时间，如表2－6所示。 请求出：员工与任务之间应当如何进行配置，才能保证完成工作任务的时间最短？ 表2－6 各员工完成任务时间汇总表单位：小时 注意：由于存在以下两种情况，匈牙利法的计算过程不唯一，最终矩阵的形式也不唯一，但最终配置结果一定相同， 1．约减时，可先进行行约减，再进行列约减；也可先进行列约减，再进行行约减。2．“盖0”线的画法不唯一。 现列举两种解法如下： 解法一： 1．以各个员工完成各项任务的时间构造矩阵一。 表2－7矩阵一 10 5 9 18 11 13 19 6 12 14 3 2 4 4 5 18 9 12 17 15 11 6 14 19 10 2．对矩阵一进行行约减，即每一行数据减去本行数据中的最小数，得矩阵二。 表2－8 矩阵二 5 0 4 13 6 7 13 0 6 8 1 0 2 2 3 9 0 3 8 6 5 0 8 13 4 3．检查矩阵二，若矩阵二各行各列均有“0”，则跳过此步，否则进行列约减，即每一列数据减去本列数据中的最小数，得矩阵三。 表2－9 矩阵三 4 0 4 11 3 6 13 0 4 5 0 0 2 0 0 8 0 3 6 3 4 0 8 11 1

4．画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住，得图2－5。 图2－5 矩阵四 操作技巧：从含“0”最多的行或列开始画“盖0”线。 5．数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步，若“盖0”线得数目小于矩阵得维数则进行数据转换，本例属于后一种情况，应进行转换，操作步骤如下： （1）找出未被“盖0”线覆盖的数中的最小值λ，例中λ＝1。 （2）将未被“盖0”线覆盖住的数减去λ。 （3）将“盖0”线交叉点的数加上λ。 本例结果见表2－10 矩阵五。 表2－10 矩阵五 3 0 4 10 2 5 13 0 3 4 0 1 3 0 0 7 0 3 5 2 3 0 8 10 0 6．重复4步和5步（计算过程见矩阵五a和矩阵五b），直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表2－11。 矩阵五a

二分图的最大匹配完美匹配和匈牙利算法

二分图的最大匹配完美匹配和匈牙利算法 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是二部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。这篇文章讲无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于求解匹配的匈牙利算法（Hungarian Algorithm）；不讲带权二分图的最佳匹配。二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集U 和V ，使得每一条边都分别连接U、V 中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，图3、图4 中红色的边就是图 2 的匹配。我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。例如图 3 中1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。最大匹配：一个图所有匹配中，所含匹

配边数最多的匹配，称为这个图的最大匹配。图 4 是一个最大匹配，它包含4 条匹配边。完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。基本概念讲完了。求解最大匹配问题的一个算法是匈牙利算法，下面讲的概念都为这个算法服务。交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图5 中的一条增广路如图6 所示（图中的匹配点均用红色标出）：增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数

指派问题的匈牙利解法

指派问题的匈牙利解法 1、 把各行元素分别减去本行元素的最小值；然后在此基础上再把每列元素减去本列中的最小值。 ???????? ??????????? ? ?0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 06 10 12 9 610 6 14 7 67 8 12 9 610 14 17 9 712 15 7 8 4 此时每行及每列中肯定都有0元素了。 2、 确定独立零元素，并作标记。 （1）、首先逐行判断是否有含有独立0元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立0元素的列，若有，则按列继续处理。若既没有含有独立0元素的行，也没有含有独立0元素的列，则仍然按行继续处理。 （2）在按行处理时，若某行有独立0元素，把该0元素标记为a ，把该0所在的列中的其余0元素标记为b ；否则，暂时越过本行，处理后面的行。把所有含有独立0元素的行处理完毕后，再回来处理含有2个以及2个以上的0元素的行：任选一个0做a 标记，再把该0所在行中的其余0元素及所在列中的其余0元素都标记为b 。

（3）在按列处理时，若某列有独立0元素，把该0元素标记为a ，把该0所在的行中的其余0元素标记为b ；否则，暂时越过本列，处理后面的列。把所有含有独立0元素的列处理完毕后，再回来处理含有2个以及2个以上的0元素的列：任选一个0做a 标记，再把该0所在列中的其余0元素及所在行中的其余0元素都标记为b 。 （4）、重复上述过程，即得到独立零元素（标记a 的“0”） ???????? ??a b b a b b a 0 4 3 2 04 0 5 0 01 2 3 2 03 7 7 1 08 11 0 3 0a b 3、 若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤： （1）、对没有标记a 的行作标记c （2）、在已作标记c 的行中，对标记b 所在列作标记c （3）、在已作标记c 的列中，对标记a 所在的行作标记c （4）、对没有标记c 的行划线，对有标记c 的列划线 ??????? ? ??04320405001232037710 811030 / / / / / \/ \/

用改进的匈牙利算法求解运输问题

用改进的匈牙利算法求解运输问题 李雪娇，于洪珍 中国矿业大学信电学院，江苏徐州 (221008) Email ：liaohuchushan@https://www.doczj.com/doc/5b11727489.html, 摘 要：本文提出用改进的匈牙利算法求解运输问题。此算法不但可以直接求取最优解，而且在运量受限制的运输问题中有很好的应用。 关键词：改进，匈牙利算法，运输问题，最优解 0. 引言 在现实生活中，我们常常会遇到许多运输问题。运输问题的求解多采用表上作业法。在此方法中，我们需要先利用最小元素法或西北角法求出一组基本可行解，再对此解检验其最优性。若此解非最优解，则又要进行解的改进。这一过程比较麻烦，尤其对一些结构不太大的模型，编程时往往过于繁琐。 同时，经典运输问题在实际应用中有很大的局限性, 对一些运输量受限制或运输能力受限制的运输问题，我们无法用表上作业法直接求取。在此，我们采用改进的匈牙利算法处理这类运输问题。为了便于描述，设物资供应量12[...]m A a a a =，物资需求量12[...]n B b b b =，从到i A j B 的单物的物资运价，最小运输量 (假设m )。 i j C i j L n >1. 匈牙利算法[1][4] 匈牙利算法的基本思想是修改效益矩阵的行和列，使得每行和每列中至少有一个零元素。经过一定的变换，得到不同行、不同列只有一个零元素。从而得到一个与这些零元素相匹配的完全分配方案。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是：在效益矩阵的任何行或列中，加上或减去一个常数后不会改变最优解的分配。求解步骤如下： 第一步：使指派问题的系数矩阵经变换后，在各行各列中都出现零元素，即从系数矩阵的每行（或列）元素中减去该行（或列）的最小元素。 第二步：寻求找n 个独立的零元素，以得到最优解：（1）从只有一个0元素的行（或列）开始，对这个0元素加圈，记为θ。然后划去此元素所在列（或行）的其他0元素，记作?。反复进行，直到所有的0元素被划完。（2）若仍有没有划圈的0元素，则从剩有0元素最少的行开始，比较这行0元素所在各列中0元素的数目，选择0元素少的那列的0元素加圈θ，然后划掉同行同列的其他0元素，反复进行直到所有的0元素被划掉或圈出。 （3）若元素的数目m 等于矩阵的阶数，那么指派问题的最优解已得到。若m ，则转入下一步。 n n <第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数：若l ，必须再变换当前的系数矩阵，才能找到个独立的0元素，为此转第四步；若l ，而，应回到第二步（2），另行试探。 n

二分图匹配(匈牙利算法和KM算法)

前言： 高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看KM的Pascal代码，大概知道过程了，后来老师说不是重点，所以忘的差不多了。都知道二分图匹配是个难点，我这周花了些时间研究了一下这两个算法，总结一下 1.基本概念 M代表匹配集合 未盖点：不与任何一条属于M的边相连的点 交错轨：属于M的边与不属于M的边交替出现的轨（链） 可增广轨：两端点是未盖点的交错轨 判断M是最大匹配的标准：M中不存在可增广轨 2.最大匹配，匈牙利算法 时间复杂度：O(|V||E|) 原理： 寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。修改M 为M&P。即这条轨进行与M进行对称差分运算。 所谓对称差分运算，就是比如X和Y都是集合，X&Y=(X并Y)-(x交Y) 有一个定理是：M&P的边数是|M|+1，因此对称差分运算扩大了M 实现： 关于这个实现，有DFS和BFS两种方法。先列出DFS的代码，带注释。这段代码来自中山大学的教材

核心部分在dfs(x)，来寻找可增广轨。如果找到的话，在Hungarian()中，最大匹配数加一。这是用了刚才提到的定理。大家可以想想初始状态是什么，又是如何变化的 view plaincopy to clipboardprint?

第二种方法BFS，来自我的学长cnhawk 核心步骤还是寻找可增广链，过程是： 1.从左的一个未匹配点开始，把所有她相连的点加入队列 2.如果在右边找到一个未匹配点，则找到可增广链 3.如果在右边找到的是一个匹配的点，则看它是从左边哪个点匹配而来的，将那个点出发的所有右边点加入队列 这么说还是不容易明白，看代码吧

运筹学指派问题的匈牙利法实验报告

运筹学 课 程 设 计 报 告 专业： 班级： 学号： ： 2012年6月20日

目录 一、题目。 二、算法思想。 三、算法步骤。 四、算法源程序。 五、算例和结果。 六、结论与总结。

一、题目：匈牙利法求解指派问题。 二、算法思想。 匈牙利解法的指派问题最优解的以下性质： 设指派问题的系数矩阵为C=()c ij n n?，若将C的一行（或列）各元素分别减去一个常数k（如该行或列的最小元素），则得到一个新的矩阵C’=()'c ij n n?。那么，以C’位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。 由于系数矩阵的这种变化不影响约束方程组，只是使目标函数值减少了常 数k，所以，最优解并不改变。必须指出，虽然不比要求指派问题系数矩阵中无 负元素，但在匈牙利法求解指派问题时，为了从以变换后的系数矩阵中判别能否 得到最优指派方案，要求此时的系数矩阵中无负元素。因为只有这样，才能从总 费用为零这一特征判定此时的指派方案为最优指派方案。 三、算法步骤。 （1）变换系数矩阵，使各行和各列皆出现零元素。 各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有 零元素，同时，也避免了出现负元素。 （2）做能覆盖所有零元素的最少数目的直线集合。

因此，若直线数等于n，则以可得出最优解。否则，转第（3）步。 对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指派方案。在第（1）步的基础上，若能找到n个不同行、不同列的零元素，则对应的指派方案总费用为零，从而是最优的。当同一行（或列）上有几个零元素时，如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的是零元素能恰当地分布在不同行和不同列上，而并在与它们的多少。但第（1）步并不能保证这一要求。若覆盖所有零元素的最少数目的直线集合中的直线数目是n，则表明能做到这一点。 此时，可以从零元素的最少的行或列开始圈“0”，每圈一个“0”，同时把位于同行合同列的其他零元素划去（标记为），如此逐步进行，最终可得n个位于不同行、不同列的零元素，他们就对应了最优解；若覆盖所有零元素的最少数目的直线集合中的元素个数少于n，则表明无法实现这一点。需要对零元素的分布做适当调整，这就是第（3）步。 （3）变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第（2）步。 在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中个元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可。 四、算法源程序。

二分图的最大匹配经典之匈牙利算法

Doctor的图论计划之——二分图最大匹配 第一讲二分图的最大匹配经典之匈牙利算法 二分图，顾名思义就是分成了两个部分的图……很白痴的解释（自己吐槽了先），但吐槽的同时我们也要发现一些二分图的基本性质！ 性质1 二分图之所以分成了两个部分，那是因为单独的一个部分中的任意两点不连通！ 性质2 二分图匹配——匈牙利算法中我们只需记录集合1到集合2的单向边就可以了（注意看上边的图，箭头是单向的）思考这是为什么！ 但是！二分图确实是无向图！！！只不过匈牙利算法只是从一个集合另一个集合走一遍罢了！！！！ 性质3 树是一种特殊的二分图！ 紫色的结点构成集合1，绿色的结点构成集合2，换句话说，儿子和爸爸打仗时爷爷和

孙子站在同一战线！（也可以认为是儿子和爸妈吵架时总是爷爷奶奶护着，小时候有这样的记忆没有？反正我没有！） PS：树就是无回路懂不？ 性质3 对于任意二分图，其包含的环一定全部是偶环！（充要可证） 可以证明，含有奇数条边的环一定有两个在相同集合内的点有边相连！ 也就是说——二分图的bfs子树一定不含奇环！ 接下来说一下二分图求最大匹配的算法——匈牙利算法 【例1】传说中的多米诺骨牌覆盖问题 在一个n*m的棋盘上，摆放一些1*2大小的多米诺骨牌，但棋盘某些地方是坏 掉的，即不能将骨牌置于这些坏掉的格子上，求最多能摆上的骨牌数量 【例2】传说中的猎人打鸟问题 猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被 打掉，也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光 所有的鸟？ 【例3】传说中的搞对象问题 一保守教师想带学生郊游, 却怕他们途中谈恋爱,他认为满足下面条件之一的两 人谈恋爱几率很小: (1)身高差>40 (2) 性别相同(3) 爱好不同类型的音乐(4) 爱好同类型的运动 告诉你每个同学的信息，问老师最多能带多少学生？ 这样的问题如何解决？搜索？怎么搜？会不会超时？答案很简单，三道题中的元素都可以用很简单的方式分成两个互不相干的部分，因此可以用二分图匹配来解决这个问题：形象的说，我们规定搞基和百合都是不允许的，已知一群男人和女人，他们可以看做图中的顶点，男人构成了集合A,女人构成了集合B，边表示这名男人和这名女人互相有好感（可以配成一对）不考虑个人因素，现在希望为这些饥渴的男男女女找到最多的配对数（脚踏两只船也是不允许的！）为了解决这样的问题我们才引入了二分图的匹配算法——匈牙利算法！ 匈牙利算法是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出，因而得名。 如果暴搜的话那么无疑时间复杂度将成为O（2^E）！无法快速实现，于是我们就提出了更为高效的算法，这种算法是从网络流演变而来，但这里我们抛开所有网络流的知识，但从这一算法的角度来进行阐释！ 解释一些常用的名词 交错轨：所谓交错轨，还有一种更为文雅的说法叫增广轨，这种说法让人不禁联想到蛋疼的网络流算法，所以我更喜欢用一种与网络流无关的说法来称呼它，下面我们来举几个交错轨的例子：

匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes K?nig和Jen? Egerváry的工作之上创建起来的。 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 二分图： 二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。图一就是一个二分图。 匈牙利算法： 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是一种用增广路径求二分图最大匹配的算法。 Hall定理： 二部图G中的两部分顶点组成的集合分别为X, Y; X={X1, X2, X3,X4, .........,Xm}, Y={y1, y2, y3, y4 , .........,yn}, G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m) 匹配： 给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。图一中红线为就是一组匹配。 未盖点： 设Vi是图G的一个顶点，如果Vi 不与任意一条属于匹配M的边相关联，就称Vi 是一个未盖点。如图一中的a 3、b1。

运输问题的匈牙利解法和表上作业法

运输问题的解法 运输问题是一类特殊的线性规划问题，最早是从物质调运工作中提出的，后来又有许 多其它问题也归结到这一类问题中。正是由于它的特殊结构，我们不是采用线性规划的单纯方法求解，而是根据单纯形方法的基本原理结合运输问题的具体特性须用表上作业的方法求解。 §1 运输问题的数学模型及其特性 1.1 运输问题的数学模型 设有 个地点（称为产地或发地） 的某种物资调至 个地点（称为销 地或收地） ，各个发点需要调出的物资量分别为 个单位，各个收点需要调进的物资量分别为 个单位。已知每个发点 到每个收点 的物 资每单位运价为 ，现问如何调运，才能使总的运费最小。我们把它列在一张表上（称为 运价表）。设 表示从产地 运往 销地的运价（ =1，2，…， ； =1，2，…， ）。 表3-1 如果（总发量） （总收量），我们有如下线性规划问题： m m A A A ,,,21 n n B B B ,,,2 1 m a a a ,,,21 n b b b ,,,21 i A j B ij c ij x i A j B i m j n ∑∑===m i n j ij ij x c z 11 min

（3.1） （3.1）式称为产销平衡运输问题的数学模型。当（总发量） （总收量） 时。即当产大于销（ ）时，其数学模型为 （3.2） 当销大于产（ ）时，其数学模型为 （3.3） 因为产销不平衡的运输问题可以转化为产销平衡的运输问题。所以我们先讨论产销平衡的运输问题的求解。 运输问题有个未知量,个约束方程。例如当≈40,=70时（3.1）式就有2800个未知量，110个方程,若用前面的单纯形法求解，计算工作量是相当大的。我们必须寻找特殊解法。 1.2 运输问题的特性 由于运输问题也是线性规划问题，根据线性规划的一般原理，如果它的最优解存在，一 ????? ??????==≥====∑∑==),,2,1;,2,1(0),,2,1(),,2,1(1 1n j m i x n j b x m I a x ij j m i ij i n j ij ∑∑==≠n j j m i i b a 1 1 ∑∑==>n j j m i i b a 1 1 ∑∑===m i n j ij ij x c z 11 min ????? ??????==≥===≤∑∑==),,2,1;,2,1(0),,2,1(),,2,1(1 1n j m i x n j b x m I a x ij j m i ij i n j ij ∑∑==

可以直接用的匈牙利算法

将xyl程序存入M文件，在matlab中先写入邻接矩阵marix，而后再写function [z,ans]=xyl(marix) 回车得出结果 程序文件 xyl.m function [z,ans]=xyl(marix) %输入效率矩阵 marix 为方阵; %若效率矩阵中有 M,则用一充分大的数代替; %输出z为最优解，ans为最优分配矩阵； %////////////////////////////////////////////////// a=marix; b=a; %确定矩阵维数 s=length(a); %确定矩阵行最小值，进行行减 ml=min(a'); for i=1:s a(i,:)=a(i,:)-ml(i); end %确定矩阵列最小值，进行列减 mr=min(a); for j=1:s a(:,j)=a(:,j)-mr(j); end % start working num=0; while(num~=s) %终止条件是“（0）”的个数与矩阵的维数相同 %index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0 index=ones(s); index=a&index; index=~index; %flag用以标记划线位，flag=0 表示未被划线， %flag=1 表示有划线过，flag=2 表示为两直线交点 %ans用以记录 a 中“（0）”的位置 %循环后重新初始化flag,ans flag = zeros(s); ans = zeros(s); %一次循环划线全过程，终止条件是所有的零元素均被直线覆盖， %即在flag>0位,index=0 while(sum(sum(index))) %按行找出“（0）”所在位置，并对“（0）”所在列划线， %即设置flag,同时修改index,将结果填入ans for i=1:s t=0;

指派问题的解法

指派问题的解法总结 问题引入：在工作的时候，常常需要对一些人进行工作安排，由于某些条件的限制， 每个人只能进行一种工作，怎么安排才能使得总工作时间最小。我们把这一类问题称 为指派问题。在这里，我只对人和工作刚好一对一的指派问题的解法进行总结，而对 于不是一对一的，则可以通过文献1中的一些方法进行变换。 目前问题解法的总结。 1：最广泛应用的解法：匈牙利算法。 算法简介：库恩（fW．W．Kuhn)于1955年提出了指派问题的解法．他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等 于覆盖所有0元素的最少直线数。这个解法称为匈牙利解法。 匈牙利算法虽是运用最广泛的算法，但其操作过程却过于复杂。在划0的时候也不方 便记忆，对于初学者来说掌握不便。于是国内很多学者对指派问题给出了几个较简单，方便易记的算法。 2：指派问题新解法——目标值子矩阵法。 算法描述：任取变量矩阵X某一行中的最小元素，为该行元素目标值的最优解(但 不一定是系统目标函数的最优解)，应该是系统目标函数满意解中的一个元素，记作 a11 划去a11 所在的行和列，取剩下的子矩阵中某一行的最小元素，记作a22。依次 类推，直到最后一个元素a nn．这些元素相加得系统目标函数的一个满意解，此为一 次运算．第二次运算取变量矩阵X中含a 以外的任一行，做与上面相同运算，又可以 得到系统的第二个满意解．相同地，对于n行做n次运算，共得到系统的n个满意解，系统的最优解即应该是这 n个满意解当中的最小值．若第i的最小元素在前面以被取 用过，则在进行第i的运算时，不选取该元素，取该行中未被选用过的元素中最小的一个进行运算。 算法分析：相对于匈牙利算法，此算法简单，方便操作。但不能给出所有最优解，得出的最优解唯一，若要给出全部最优解，则算法的次数将大大增加。 当矩阵维数较大的时候，可以对矩阵进行划分，以更快计算。 算法举例：对于变量矩阵x；

匈牙利解法C程序代码

西安科技大学 程序设计实训报告 班级： ^^^^^^^^^^^ 学号： ^^^^^^^^^^ 姓名： ^^^^^^ 2012年6月20日

题目指派问题的匈牙利法 一、算法思想 本程序根据课本上匈牙利算法思想做了如下操作：首先定义结构体ASS用于存储该矩阵中每个元素，并且定义结构体TrueOrForse用于判断矩阵中每个元素是否被标记。并且定义了相应函数（例如：输出函数）来完成相关操作。 （注释：具体操作见第二步，算法流程与步骤。具体结构体与相关函数祥见源程序首部定义） 二、算法流程与步骤 初始化： 本程序首先根据用户输入转换为其相应的方阵（即行数等于列数）。若人的数量乘以每个人最多工作的任务数量小于或等于任务数量，同时补n行0；否则补n列0。（n 为任务数量减去人的数量乘以每个人最多工作的任务数量的绝对值）。输出该方阵，方便用户检查输入是否正确。 标记： 然后根据用户输入判断是按行减去每行最小值，还是减去每列最小值（注释：若人的数量乘以每个人最多工作的任务数量小于或等于任务数量，则减去每行最小值，否则则减去每列最小值）。然后从中选择其中含0最多的行或列依次进行标记，若所标记的直线数量小于矩阵行数（或列数），则撤销所有标记，选择其中含0最少的行（或列）减去其中除0以外的最小值，并同时将该行出现负数所在列（或行）每个元素加上该负数的相反数。重复以上操作，直到所标记的直线数等于矩阵行数（或列数）。 转换为0-1指派矩阵： 从行与列中选择含零最少的行（或列），将该行（或列）中的零元素先转换为矩阵中不可能出现的一个很大的数，将零出现的行与列进行标记，然后从列（或行）中选择零最少的，并将其中未被标记零元素转化为很大的数，依此类推；直到标记完所有数，最后将很大的数转换为1，其余均转化为0。即得0-1指派矩阵。

匈牙利算法

匈牙利算法(Edmonds算法)步聚： (1)首先用（*）标记X中所有的非M顶点，然后交替进行步骤（2），（3）。 (2)选取一个刚标记（用（*）或在步骤（3）中用（y i）标记）过的X中顶点，例如顶点x ，如果x i与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过,则用（x i）i 去标记Y中顶点y。重复步骤(2)，直至对刚标记过的X中顶点全部完成一遍上述过程。 (3)选取一个刚标记（在步骤(2)中用(x i)标记）过的Y中结点，例如y i，如果y i与x为 同一匹配边的两端点，且在本步骤中x尚未被标记过，则用(y i)去标记X中结点x。 重复步骤(3)，直至对刚标记过的Y中结点全部完成一遍上述过程。 (2),(3)交替执行，直到下述情况之一出现为止： (I)标记到一个Y中顶点y，它不是M顶点。这时从y出发循标记回溯，直到（*）标 记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配 边，k+1条是非匹配边。 (II)步骤(2)或(3)找不到可标记结点，而又不是情况(I)。 (4)当(2),(3)步骤中断于情况(I)，则将交替链中非匹配边改为匹配边，原匹配边改为非 匹配边(从而得到一个比原匹配多一条边的新匹配)，回到步骤(1)，同时消除一切现有 标记。 (5)对一切可能,(2)和(3)步骤均中断于情况(II),或步骤(1)无可标记结点,算法终止 (算法找不到交替链). 以上算法说穿了，就是从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过交替出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。 下面给出此算法的一个例子：

匈牙利解法的步骤

指派问题的匈牙利法求解步骤： 1) 变换指派问题的系数矩阵(c ij)为(b ij)，使在(b ij)的各行各列中都出现0元素，即 从(cij)的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。 2) 进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0 元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。 找独立0元素，常用的步骤为： 从只有一个0元素的行开始，给该行中的0元素加圈，记作◎。然后划去◎所 在列的其它0元素，记作?；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。 从只有一个0元素的列开始（画?的不计在内），给该列中的0元素加圈，记作◎； 然后划去◎所在行的0元素，记作?，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比较这行各0元素所 在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让” 选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 若◎元素的数目m 等于矩阵的阶数n（即：m＝n），那么这指派问题的最优解已 得到。若m < n, 则转入下一步。 3) 用最少的直线通过所有0元素。其方法： 对没有◎的行打“√”； 对已打“√”的行中所有含?元素的列打“√”； 再对打有“√”的列中含◎元素的行打“√”； 重复①、②直到得不出新的打√号的行、列为止； 对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最 少直线数l 。 注：l 应等于m，若不相等，说明试指派过程有误，回到第2步，另行试指派；若 l＝m < n，表示还不能确定最优指派方案，须再变换当前的系数矩阵，以找到n 个独立的0元素，为此转第4步。 4) 变换矩阵(b ij)以增加0元素 在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这 个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。转回第2步。

算法学习：图论之用匈牙利算法求二分图的最大匹配

用匈牙利算法求二分图的最大匹配 什么是二分图，什么是二分图的最大匹配，这些定义我就不讲了，网上随便都找得到。二分图的最大匹配有两种求法，第一种是最大流（我在此假设读者已有网络流的知识）；第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。匈牙利算法其实很简单，但是网上搜不到什么说得清楚的文章。所以我决定要写一下。 最大流算法的核心问题就是找增广路径（augment path）。匈牙利算法也不例外，它的基本模式就是： 可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性，下面我来分析一下。 （注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。每条边也不需要有方向。） 图1 图2 图1是我给出的二分图中的一个匹配：［1，5］和［2，6］。图2就是在这个匹配的基础上找到的一条增广路径：3->6->2->5->1->4。我们借由它来描述一下二分图中的增广路径的性质： (1)有奇数条边。 (2)起点在二分图的左半边，终点在右半边。 (3)路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。） (4)整条路径上没有重复的点。 (5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。） (6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。） (7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。（如图2所示，新的匹配就是所有蓝色的边，而所有红色的边则从原匹配中删除。则新的匹配数为3。） 不难想通，在最初始时，还没有任何匹配时，图1中的两条灰色的边本身也是增广路径。因此在这张二分图中寻找最大配匹的过程可能如下： (1)找到增广路径1->5，把它取反，则匹配数增加到1。 (2)找到增广路径2->6，把它取反，则匹配数增加到2。 (3)找到增广路径3->6->2->5->1->4，把它取反，则匹配数增加到3。 (4)再也找不到增广路径，结束。 当然，这只是一种可能的流程。也可能有别的找增广路径的顺序，或者找到不同的增广路径，最终的匹配方案也可能不一样。但是最大匹配数一定都是相同的。 对于增广路径还可以用一个递归的方法来描述。这个描述不一定最准确，但是它揭示了寻找增广路径的一般方法：“从点A出发的增广路径”一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匹配中没有与任何点配对，则它就是这条增广路径的终点；反之，如果点B已与点C配对，那么这条增广路径就是从A到B，再从B 到C，再加上“从点C出发的增广路径”。并且，这条从C出发的增广路径中不能与前半部分的增广路径有重复的点。 比如图2中，我们要寻找一条从3出发的增广路径，要做以下3步： (1)首先从3出发，它能连到的点只有6，而6在图1中已经与2配对，所以目前的增广路径就是3->6->2再加上从2出发的增广路径。 (2)从2出发，它能连到的不与前半部分路径重复的点只有5，而且5确实在原匹配中没有与2配对。所以从2连到5。

图的匹配——匈牙利算法与KM算法

图的匹配 一、什么是图的匹配 1.图的定义 无向图：无向图G 是指非空有限集合V G ，和V G 中某些元素的无序对的集合E G ，构成的二元组(V G ，E G )。V G 称为G 的顶点集，其中的元素称为G 的顶点。E G 称为G 的边集，其中的元素称为G 的边。在不混淆的情况下，有时记V ＝V G ，E ＝E G 。如果V ＝{v 1,…,v n }，那么E 中的元素e 与V 中某两个元素构成的无序对(v i ，v j )相对应，记e ＝v i v j ，或e ＝v j v i 。在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。 二分图：设G 是一个图。如果存在V G 的一个划分X ，Y ，使得G 的任何一条边的一个端点在X 中，另一个端点在Y 中，则称G 为二分图，记作G ＝(X ，Y ，E)。如果G 中X 的每个顶点都与Y 的每个顶点相邻，则称G 为完全二分图。 2.匹配的相关概念 设G ＝(V ，E)是一个图，E M ?，如果M 不含环且任意两边都不相邻，则称M 为G 的一个匹配。G 中边数最多的匹配称为G 的最大匹配。 对于图G ＝(V ，E)，在每条边e 上赋一个实数权w(e)。设M 是G 的一个匹配。定义∑∈=m e e w M w )()(，并称之为匹配M 的权。G 中权最大的匹配称为G 的最大权匹配。如果 对一切，e ∈E ，w(e)=1,则G 的最大权匹配就是G 的最大匹配。 设M 是图G=(V ,E)的一个匹配，v i ∈V 。若v i 与M 中的边相关联，则称v i 是M 饱和点，否则称v i 为M 非饱和点。 如果G 中每个顶点都是M 饱和点，则称M 为G 的完美匹配。 设M 是G 的一个匹配，P 是G 的一条链。如果P 的边交替地一条是M 中的边，一条不是M 中的边，则称P 为M 交错链。类似地，我们可以定义G 的交错圈。易知，G 的交错圈一定是偶圈。 一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。 两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2＝（S 1∩S 2）\（S 1∪S 2） 容易看出，设M 是G 的匹配，P 是G 中的M 增广链、则M ⊕P 也是G 的匹配，而且1+=⊕M P M 。 图表 1 “异或”操作 可以证明，G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。

匈牙利法解决人数及任务数不等的指派问题

匈牙利法解决人数与任务数不等的指派问题 于凯 重庆科技学院经济管理学院物流专业重庆沙坪坝区 摘要：本文将讨论运筹学中的指派问题，而且属于非标准指派问题，即人数与任务数不相等的指派问题，应当视为一个多目标决策问题，首先要求指派给个人任务数目两两之间相差不能超过1，其次要求所需总时间最少，并且给出了该类问题的求解方法。 关键词：运筹学指派问题匈牙利算法系数矩阵解矩阵 引言：在日常的生产生活中常遇到这样的问题：有n项任务，有n个人员可以去承担这n 项任务，但由于每位人员的特点与专长不同，各对象完成各项任务所用的时间费用或效益不同；有因任务性质要求和管理上需要等原因，每项任务只能由一个人员承担来完成，这就涉及到应该指派哪个人员去完成哪项任务，才能使完成n项任务花费总时间最短，总费用最少，产生的总效益最佳。我们把这类最优匹配问题称为指派问题或分配问题。 1.指派问题的解法——匈牙利法 早在1955年库恩（，该方法是以匈牙利数学家康尼格（koning）提出的一个关于矩阵中0元素的定理为基础，因此得名匈牙利法（The Hungonrian Method of Assignment） 1.1匈牙利解法的基本原理和解题思路 直观的讲，求指派问题的最优方案就是要在n阶系数矩阵中找出n个分布于不用行不同列的元素使得他们的和最小。 而指派问题的最优解又有这样的性质：若从系数矩阵C（ij）的一行（列）各元素都减去该行（列）的最小元素，得到新矩阵CB（ij），那么以CB（ij）为系数矩阵求得的最优解和原系数矩阵C（ij）求得的最优解相同。 由于经过初等变换得到的新矩阵CB（ij）中每行（列）的最小元素均为“○”，因此求原指派问题C（ij）的最优方案就等于在新矩阵CB（ij）中找出n个分布于不同行不同列的“○”元素（简称为“独立○元素”），这些独立○元素就是CB（ij）的最优解，同时与其对应的原系数矩阵的最优解。 1.2匈牙利法的具体步骤 第一步：使指派问题的系数矩阵经过变换在各行各列中都出现○元素。 （1）先将系数矩阵的每行中的每个元素减去本行中的最小元素。 （2）再从系数矩阵的每列中的每个元素减去本列的最小元素。 第二步：进行试指派，以寻求最优解。 （1）从含有○元素个数最少的行（列）开始，给某个○元素加圈，记作◎，然后划去与◎所在同行（列）杂其他○元素，记作?。（注：从含元素 少的开始标记◎的原则） （2）重复进行（1）的操作，直到所有○元素都记作◎或?，称作“礼让原则”。 （3）按以上方法操作后，若◎元素数目m’等于矩阵阶数n，那么指派问题最优解已得到。若m﹤n，则转入下一步。 第三步：做最少的直线覆盖所有的○元素，以确定该系数矩阵中能找到最多的独立○元素。 （1）对没有◎的行打√号； （2）对已打√号的行中含有?元素所在的列打√号； （3）对已打√号的列中含有◎元素所在的行打√号； （4）重复（2）、（3）直到得不到新√号的行和列为止； （5）对没有√号的行画一横线，有√号的列画一竖线。如此便可以覆盖所有

匈牙利算法

匈牙利算法是一种组合优化算法，可以在多项式时间内解决任务分配问题，并在以后推广原始的对偶方法。美国数学家哈罗德·库恩（Harold Kuhn）在1955年提出了该算法。该算法之所以称为匈牙利算法，是因为它很大程度上是基于前匈牙利数学家Denes K nig和Jen Egervary的工作。 假设它是无向图。如果顶点集V可以分为两个不相交的子集，则在该子集中选择具有最大边数的子集称为图的最大匹配问题。 如果存在匹配项和匹配项数，则该匹配项称为完美匹配项，也称为完全匹配项。称为完美匹配时的特殊。 在介绍匈牙利算法之前，只有几个概念，M是G的匹配项。 如果，则边缘已经在匹配的M上。 M交错的路径：P是G的路径。如果P中的边是属于M的边和不属于M而是属于G的边交替，则称P为M交错的路。如：路径，。 M饱和点：例如，如果V与M中的边关联，则V为m饱和点；否则，V为非M饱和点。例如，它们都属于M饱和点，而其他所有点都属于非M饱和点。 M扩展路径：P是M交错的路径。如果P的起点和终点均为非M饱和点，则P称为m增强路径。例如（不要与流网络中的增强路径混淆）。 寻找最多匹配项的一种明显算法是找到所有匹配项，然后保留最多匹配项。但是该算法的时间复杂度是边数的指数函数。因

此，我们需要找到一种更有效的算法。下面介绍使用增强路径查找最大匹配的方法（称为匈牙利算法，由匈牙利数学家爱德蒙兹（Edmonds）于1965年提出）。 增强轨道（也称为增强轨道或交错轨道）的定义： 如果P是连接图G中两个不匹配顶点的路径，并且属于M的边和不属于M的边（即已匹配和待匹配）在P上交替，则称P为扩充路径相对于M 从增强路径的定义可以得出以下三个结论： （1）到P的路径数必须是奇数，并且第一个边缘和最后一个边缘都不属于M。 （2）通过将M和P取反可以获得更大的匹配度。 （3）当且仅当没有M的增加路径时，M是G的最大匹配。 算法简介： （1）令M为空 （2）通过异或运算找到增强路径P并获得更大的匹配项而不是M （3）重复（2），直到找不到扩展路径。 时间复杂度邻接矩阵：最差的是邻接表： 空间复杂度的邻接矩阵：邻接表：