匈牙利算法示例ppt

匈牙利算法经典问题——工作分配一个公司有n个工作岗位空缺，每个岗位空缺需要有一定资格的人来填补。现在有m个人申请这n个工作。由于每个人工作能力不同，所以不同的人能胜任不同的工作。现在已知每个人所能胜任的若干工作，求这m个人最多可以填补几个工作岗位。每个人只能做一份工作，每个工作岗位也只需要一个人二分图设G=(V,{R})是一个无向图。图的顶点集V可分割为两个互不相交的子集X和Y（子集内部没有边），图任何一条边的两个端点都分属不同的子集。则称图G为二分图。用n个顶点X={1,2,3,4,5}表示n个工作，用m个顶点Y={A,B,C,D,E,F}表示m个工人。12345ABCDEF{1,2,3,4,5}{A,B,C,D,E,F}二分图匹配给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。在工作分配的问题中，我们给出一个可行的分配方案，就是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题如果这个匹配是最优的（可以填补的工作岗位最多），就是最大匹配。12345ABCDEF12345ABCDEF12345ABCDEF12345ABCDEF2345ABDE12345ABDE12345ABCDE匈牙利算法增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。由增广路的定义可以推出下述三个结论：1）P的路径长度必定为奇数，第一条边和最后一条边都不属于M。2）P经过取反操作可以得到一个更大的匹配M’。3）M为G的最大匹配当且仅当不存在相对于M的增广路径。１２AB４３CD5EF１２AB４３CD5EF匈牙利算法１２AB４３CD5EF１２AB４３CD5EF(1)找到某一匹配M(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M(3)重复(2)操作直到找不出增广路径为止设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。jiijijxcZmin1.21inijiixxxxtsi=1,2,…,n121njijjjxxxxj=1,2,…,nnjnixij,,2,1;,,2,11,0分配问题及其数学模型有甲、乙、丙、丁、戊五位工人被指派去完成A、B、C、D、E五项任务，每个人完成任务所需的工时各不相同，见表。求应如何指派人员才能使得所用工时最少？ABCDE甲127979乙89666丙71712149丁15146610戊4107109任务时间人员89匈牙利算法的基本原理是基于以下两个定理.定理1设C=(Cij)n×n是指派问题的效益矩阵，若将C中的任一行（或任一列）减去该行（或该列）中的最小元素，得到新的效率矩阵C’，则C’对应的新的指派问题与原指派问题有相同的最优解.定理2效率矩阵C中独立的0元素的最多个数等于覆盖所有0元素的最少直线数.当独立零元素的个数等于矩阵的阶数时就得到最优解.匈牙利法的解题步骤：第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即(1)从（cij）的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。()ijc127979896667171214915146610410710950202230000105729800406365-7-6-7-6-4-0-050202230000105729800406365-0-0-0第二步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。然后划去◎所在列(行)的其它0元素，记作Ø；这表示这列所代表的任务已指派完，不必再考虑别人了。(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø．(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。5020223000010572980040636556364892751032225◎◎◎◎ØØØØØ50202230000105729800406365◎Ø◎Ø◎ØØ◎Ø第三步；作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。（1）对没有◎的行打√（2）在已经打√的行中所含有的0元素打√号（3）在已经打√号的列中含◎元素的行打√；（4）重复（2）（3）直到得不出打√的行列为止（5）对没有打√的行画一横线，有打√的列画一纵线，这就覆盖所有0元素的最少直线数。令这一直线数为l。若ln,说明必须再换当前的系数矩阵，才能找到n个独立的0元素，为此转到第四步；若l=n，而mn，应回到（2）（4）另行试探。√50202230000105729800406365◎Ø◎◎ØØØØ◎√√√第四步；在没有被直线覆盖的部分中找出最小元素。然后在行打√行每个元素减去这一最小元素，而在打√列的每个元素都加上这一最小元素，以保证原来0元素不变。这样得到新系数矩阵。若得到n个独立的0元素，则已得到最优解，否则回到第三步。3414481153834227◎◎◎◎◎ØØØØØ3414481153834227◎◎◎◎◎ØØØØØ上面矩阵有5个独立0元素，这就得到相应的最优解。×50202230000105729800406365◎Ø◎◎ØØØØ◎√√√-2-2+200001010001000000100000100000100100100000100000010或解矩阵得到2个最优指派方案；（1）甲-B，乙-C，丙--E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C，戊-A。所需时间为minz=7+6+9+6+4=3215•非标准型的指派问题：匈牙利法的条件是：模型求最小值、效率cij≥0。当遇到各种非标准形式的指派问题时，处理方法是先将其转化为标准形式，1、人数和事数不相等的指派问题：人少事情多，虚拟“人”，做各事的费用系数为0；人多事情少，虚拟“事”，各人做的费用系数为0。2、对于求极大化的问题，只要系数矩阵变换为B＝（m-cij）nn，仍可利用匈牙利算法进行求解。3、一个人可以做几件事情的指派问题：可以将该人化作相同的几个“人”来接受指派，费用一样。4、某事一定不能由某人做的指派问题，费用系数为“M”然后用匈牙利法来求解。请各位老师和同学批评指导！