《Kuhn-Munkres.doc》由会员分享，可在线阅读，更多相关《Kuhn-Munkres.doc（7页珍藏版）》请在金锄头文库上搜索。
1、Kuhn-Munkres算法 KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为Ai，顶点Yi的顶标为Bi，顶点Xi与Yj之间的边权为wi,j。在算法执行过程中的任一时刻，对于任一条边(i,j)，Ai+Bj=wi,j始终成立。KM算法的正确性基于以下定理：若由二分图中所有满足Ai+Bj=wi,j的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小
2、于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。初始时为了使Ai+Bj=wi,j恒成立，令Ai为所有与顶点Xi关联的边的最大权，Bj=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：两端都在交错树中的边(i,j)，Ai+Bj的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子
3、图。两端都不在交错树中的边(i,j)，Ai和Bj都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。X端不在交错树中，Y端在交错树中的边(i,j)，它的Ai+Bj的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。X端在交错树中，Y端不在交错树中的边(i,j)，它的Ai+Bj的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。现在的问题就是求d值了。为了使Ai+Bj=wi,j始终成立，且至少有一条边进入相等子图，d应该等于minAi+Bj-wi,j|Xi在交错树中，Yi不在交错树中。以上就是KM算法的基本思路。但
4、是朴素的实现方法，时间复杂度为O(n4)需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slackj变成原值与Ai+Bj-wi,j的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。二分图最大权完美匹配KM算法好吧，这弄点正经的。这次就
5、写写大家肯定很久以前就搞出来的KM。我写这个是因为前几天整理模板的时候居然发现我的KM还是O(n4)的，虽然实际运行效果大部分和O(n3)差不多，但是理论的上界仍然让我不爽，就像network simplex algorithm一样。先说一下KM的适用范围。据我分析KM实际上可以对任意带权（无论正负权）二分图求最大/最小权完美匹配，唯一的一个，也是最重要的一个要求就是这个匹配必须是完美匹配，否则KM的正确性将无法得到保证。这个当了解了KM的正确性证明之后自然就会知道。非完美的匹配的似乎必须祭出mincost maxflow了。然后就是KM的时间界。这里略去KM的步骤不谈。众所周知，KM弄不好就
6、会写出O(n4)的算法，而实际上是存在O(n3)的实现的。那么O(n4)究竟是慢在什么地方呢？这个就需要搞清楚O(n4)的4究竟是怎么来的。每个点都需要作一次增广，所以有一个n的循环。每个循环内部，每次可能无法得到一条增广路，需要新加入一个y顶点，然后重新寻找增广路。一次最少加进1个点，所以最多加入n次。每次重新找一遍增广路n2，更新距离标号需要扫描每一条边n2，所以迭加起来O(n)*O(n)*O(n2)，结果自然就是O(n4)。第一层和第二层循环似乎没有很好的方法可以把它搞掉，所以我们只能从第三层，也就是每次的O(n2)入手。这一层包括两个部分，一个是增广路的n2，一个是更新标号的n2，需要
7、将二者同时搞掉才能降低总共的复杂度。注意更新标号之后有一个最重要的性质，那就是 原来存在的合法边仍然合法，更新只是将不合法的边变得合法。所以当我们找到一次交错树，没有增广路之后，下次再寻找的时候完全没有必要重新开始，因为原先有的边更新之后还有，所以完全可以接着上一次得到的交错树继续寻找。那么应该从什么地方继续号、开始搜索呢？很明显是那些新加进的点，也就是新进入的那些y点。这样虽然不知道每次更新标号会又扫描多少次，但是每条边最多也就被扫描一次，然后被添加进交错树一次。所以这一块，n层循环总的复杂度是O(n2)。按照这样描述的话，用dfs似乎没有可以接着上一次找的方法，所以只能用bfs来写增广路的
8、搜索了。然后就是重标号。这一段实际上是由重新扫了一次边，然后对x在树中而y不在的边进行侦测，然后重新标号。想把这个搞掉似乎是有些困难，但是我们先做的是增广路搜索然后才是标号，增广路搜索的时候不也是要扫边么？要是能在bfs的时候记录一下什么信息，到时候直接取用不就好了？所以，做法就是在bfs的时候，对于每个扫到的这种边，更新一下对应的y顶点的标号，这个标号的意义就是y点连接的所有这种边当中可松弛的最小值，定义为slacky。然后每次更新的时候扫一下所有的y，对于所有没在交错树中的y，找到最小slacky，然后更新就可以了。注意由于我们要接着上一次进行bfs，所以上一次算出来的标号也要留下来。别忘
9、了重标号之后每个y点的slacky也要同样更新，这样每次寻找标号并更新的复杂度就是O(n)了，n层重标号最多也就是O(n2)，然后bfs的O(n2)，增广的O(n)，所以对于每个点，想对匹配进行增广，复杂度就是O(n2)，n个点每个点来一次自然就是O(n3)了。CODE:#include #include #include using namespace std; const int size = 160;const int INF = 100000000; / 相对无穷大 bool mapsizesize; / 二分图的相等子图, mapij = true 代表Xi与Yj有边bool xck
10、dsize, yckdsize; / 标记在一次DFS中，Xi与Yi是否在交错树上int matchsize; / 保存匹配信息，其中i为Y中的顶点标号，matchi为X中顶点标号 bool DFS(int, const int); void KM_Perfect_Match(const int n, const int edgesize) int i, j; int lxsize, lysize; / KM算法中Xi与Yi的标号 for(i = 0; i n; i+) lxi = -INF; lyi = 0; for(j = 0; j n; j+) lxi = max(lxi, edgeij
11、); bool perfect = false; while(!perfect) / 初始化邻接矩阵 for(i = 0; i n; i+) for(j = 0; j n; j+) if(lxi+lyj = edgeij) mapij = true; else mapij = false; / 匹配过程 int live = 0; memset(match, -1, sizeof(match); for(i = 0; i n; i+) memset(xckd, false, sizeof(xckd); memset(yckd, false, sizeof(yckd); if(DFS(i, n)
12、 live+; else xckdi = true; break; if(live = n) perfect = true; else / 修改标号过程 int ex = INF; for(i = 0; i n; i+) for(j = 0; xckdi & j n; j+) if(!yckdj) ex = min(ex, lxi+lyj-edgeij); for(i = 0; i n; i+) if(xckdi) lxi -= ex; if(yckdi) lyi += ex; / 此函数用来寻找是否有以Xp为起点的增广路径，返回值为是否含有增广路 bool DFS(int p, const
13、int n) int i; for(i = 0; i n; i+) if(!yckdi & mappi) yckdi = true; int t = matchi; matchi = p; if(t = -1 | DFS(t, n) return true; matchi = t; if(t != -1) xckdt = true; return false; int main() int n, edgesizesize; / edgeij为连接Xi与Yj的边的权值 int i; /* * 在此处要做的工作 : * 读取二分图每两点间边的权并保存在edge中, * 若X与Y数目不等，应添加配合的顶点 * 保存
