《算法设计与分析》课件 第9章 匹配与指派

算法设计与分析匹配与指派主要内容基本概念基于图的匈牙利算法基于矩阵的匈牙利算法基本概念：匹配基本概念：匹配例子基本概念：匹配例子基本概念：指派基本概念：指派例子矩阵模型图模型主要内容基本概念基于图的匈牙利算法基于矩阵的匈牙利算法基于图的匈牙利算法：匹配基于图的匈牙利算法：例子基于图的匈牙利算法：例子进行逐个匹配，选择匹配对(b1,w1)，(b2,w2)选取b3的匹配白点基于图的匈牙利算法：例子基于图的匈牙利算法：匹配增广路径具有以下特点基于图的匈牙利算法：例子匹配黑点b4在匹配黑点b5

时，找不到未匹配的白点，试图再次用增广路径来进行重新匹配，图中已经无法找到一条增广路径，所以最优匹配是4个匹配，分别是(b1,w2)，(b2,w3)，(b3,w1)，(b4,w4)，基于图的匈牙利算法：匹配算法首先遍历二分图左边部分的节点，在遍历顶点i时，调用增广路径函数，试图找到一条增广路径基于图的匈牙利算法语句4-6对B部分所有顶点的visited属性设置为0(表示未访问)，这样，每次寻找增广路径时，如果顶点的visited属性为1，表示此顶点已经在增广路径上，不能再访问注意：增广路径函数augmentedPath参数一定是A部分的顶点找增广路径的本质实际上就是深度优先搜索因为深度优先搜索的复杂度为O(n2)（二分图），所以该算法的复杂度为O(n3)基于图的匈牙利算法：指派基于图的匈牙利算法：二分图添加权重为0的边，完全二分图

基于图的匈牙利算法为了解决指派问题，需要给每个节点标注，用l(a)表给某一顶点a标注，我们定义一个合法的标注应该满足以下不等式基于图的匈牙利算法：二分图合法标注平等图基于图的匈牙利算法：KM定理基于图的匈牙利算法：KM定理基于图的匈牙利算法有权二分图上的匈牙利算法流程

基于图的匈牙利算法可以让A中的所有顶点的标注都为0(l(a)=0,∀a∈A)，B中顶点的标注以所连边的最大权重即可标注完后，对B中的每个顶点，选择与之相连的最大边(如果有多条，全部选取)，从而和所有的顶点形成了一个平等图。基于图的匈牙利算法按照贪心算法选取即可，即对所有的边按照从大到小进行排序，之后依次选取可匹配边即可，选出的边形成了一个初始匹配如果这个初始匹配是个完美匹配，根据KM定理，最大匹配找到，算法结束，否则，就需要继续寻找完美匹配基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法基于图的匈牙利算法按照KM定理，这个匹配是最大权重匹配基于图的匈牙利算法基于图的匈牙利算法主要内容基本概念基于图的匈牙利算法基于矩阵的匈牙利算法指派的数学模型指派的数学模型克尼格定理克尼格定理匈牙利算法流程找出每行的最小值，每行都减去相应的最小值；对矩阵的每一行，找到一个0，如果这个0所有在的行和列没有0*，则给这个0打星号0*；对矩阵的每一列，如果包含0*，则划线；如果刚好有n条划线，则找到最优解，否则，执行步骤4；寻找未被划线覆盖的0，如果有，则直接执行步骤5;如果没有，则找到所有没有被划线覆盖的元素中最小元素，将最小元素加到所有划了线的行中，并将所有未划线的列减去此元素;将一个未被划线覆盖的0转换为0′相同行不存在一个0∗:找0∗

所在行的0′(必然有)，再找0′所在列的0∗，重复此步骤直到0′所在列再也没有0∗，对所有找到的0∗

去掉∗，并将所有0′转变为0∗，回到步骤3；相同行存在一个0∗:对这一行划线，并取消0∗

所在列的划线，重复此步骤，直到找不出未被划分覆盖的0，回到步骤4匈牙利算法流程匈牙利算法流程步骤1步骤2步骤3步骤4（a）（b）（c）（d）（e）步骤5（f）匈牙利算法流程步骤5.2步骤5步骤5.1步骤3（g）（i）（j）（k）（l）步骤4（h）最优匹配简化匈牙利算法流程匈牙利算法的流程简化为简化匈牙利算法流程简化匈牙利算法流程将所有还没有被划线覆盖的元素(这些元素肯定大于0)减去最小值。此例中减去1简化匈牙利算法流程寻找最少的划线找到独立的0对没有独立0的行打钩寻找最少的划线对已打√的行中所含0元素的列打√号再对所有打√的