Kuhn-Munkres算法

最大化指派问题匈牙利算法匈牙利算法，也称为Kuhn-Munkres算法，是用于解决最大化指派问题（Maximum Bipartite Matching Problem）的经典算法。

最大化指派问题是在一个二分图中，找到一个匹配（即边的集合），使得匹配的边权重之和最大。

下面我将从多个角度全面地介绍匈牙利算法。

1. 算法原理：匈牙利算法基于增广路径的思想，通过不断寻找增广路径来逐步扩展匹配集合，直到无法找到增广路径为止。

算法的基本步骤如下：初始化，将所有顶点的标记值设为0，将匹配集合初始化为空。

寻找增广路径，从未匹配的顶点开始，依次尝试匹配与其相邻的未匹配顶点。

如果找到增广路径，则更新匹配集合；如果无法找到增广路径，则进行下一步。

修改标记值，如果无法找到增广路径，则通过修改标记值的方式，使得下次寻找增广路径时能够扩大匹配集合。

重复步骤2和步骤3，直到无法找到增广路径为止。

2. 算法优势：匈牙利算法具有以下优势：时间复杂度较低，匈牙利算法的时间复杂度为O(V^3)，其中V是顶点的数量。

相比于其他解决最大化指派问题的算法，如线性规划算法，匈牙利算法具有更低的时间复杂度。

可以处理大规模问题，由于时间复杂度较低，匈牙利算法可以处理大规模的最大化指派问题，而不会因为问题规模的增加而导致计算时间大幅增加。

3. 算法应用：匈牙利算法在实际中有广泛的应用，例如：任务分配，在人力资源管理中，可以使用匈牙利算法将任务分配给员工，使得任务与员工之间的匹配最优。

项目分配，在项目管理中，可以使用匈牙利算法将项目分配给团队成员，以最大程度地提高团队成员与项目之间的匹配度。

资源调度，在物流调度中，可以使用匈牙利算法将货物分配给合适的运输车辆，使得货物与运输车辆之间的匹配最优。

4. 算法扩展：匈牙利算法也可以扩展到解决带权的最大化指派问题，即在二分图的边上赋予权重。

在这种情况下，匈牙利算法会寻找一个最优的匹配，使得匹配边的权重之和最大。

Kuhn-Munkres算法KmKuhn-Munkres算法⼀种⽤于进⾏⼆分图完全匹配的算法前pre技能匈⽛利算法及增⼴路标顶对于图G(U∪V,E)。

对于x∈U，定义Lx i。

对于i∈V。

定义Ly i。

这个玩意叫做标顶，是⼀种⼈为构造的数值。

⽤于进⾏⼆分图完全匹配可⾏标顶对于所有的边，假设权值是W,⽅向是x→y，则是算法执⾏中，恒定满⾜Lx x+Ly y≥W相等⼦图相等⼦图包括U∪V,但只包括满⾜W=Lx x+Ly y的边若相等⼦图有完全匹配，则原图有完全匹配实现概括通过更改标顶，找出相等⼦图。

实现具体扩⼤相等⼦图假设当前相等⼦图⽆法进⾏完全匹配，则⾄少有⼀个点u,从其出发⽆法找到增⼴路则我们需要修改标顶，使更多的边参与进来。

假设我们现在已经知道了⼀个M,这个M是使其他边增加到相等⼦图的最⼩标顶修改量然后我们令所有的Lx i减去M,所有的Ly i加上M正确性？假设我们现在在相等⼦图中在U中已经被匹配的点x,则我们规定x∈A,否则x∈A′相似的，对于x∈V,若x已经被匹配上，则x∈B,否则x∈B′对于⼀条边(x→y,权值（代价）是W)若x∈A,y∈B，仍满⾜Lx x+Ly y=W若x∈A′,y∈B′,则为Lx x+Ly y≥W，即是原本就不在交替路中的的依旧不在若x∈A′,y∈B,则Lx x+Ly y增加，不会被添加进⼊若x∈A,y∈B′,则Lx x+Ly y有所减少，可能会被添加其他关于若x∈A′,y∈B,则Lx x+Ly y增加，不会被添加进⼊若x∈A,y∈B′,则Lx x+Ly y有所减少，可能会被添加对于上边这句，是为了保证在将⼀个点x,x∈U进⾏匹配时，只会相应的引⼊y,y∈V，⽽不会引⼊U中的点。

M如何计算？M的⼤⼩取决于没有被加到相等⼦图中的最⼤边的⼤⼩，即是Lx x+Ly y−W⽽这个我们在寻找增⼴路的时候就可以顺带更新。

其他M的贪⼼选取保证了最⼤权。

个⼈理解是损失最⼩的代价，使其可以加⼊到相等⼦图代码using std::max;using std::min;const int maxn=500;const int inf=0x7fffffff;int M[maxn][maxn];int m[maxn][maxn];int lx[maxn],ly[maxn],mins[maxn],pat[maxn];int S[maxn],T[maxn],tot;int vis[maxn];int n;bool find(int x){S[x]=1;for(int i=1;i<=n;i++){if(T[i]) continue;int s=lx[x]+ly[i]-m[x][i];if(!s){T[i]=1;if(!pat[i]||find(pat[i])){pat[i]=x;return true;}}elsemins[i]=min(mins[i],s);}return false;}int KM(){for(int i=1;i<=n;i++) lx[i]=-inf;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)lx[i]=max(lx[i],m[i][j]),ly[i]=0;memset(pat,0,sizeof(pat));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)mins[j]=inf;while(1){memset(T,0,sizeof(T));memset(S,0,sizeof(S)); if(find(i)) break;int Min=inf;for(int j=1;j<=n;j++) Min=min(Min,mins[j]);for(int j=1;j<=n;j++){if(S[j]) lx[j]-=Min;if(T[j]) ly[j]+=Min;}}}int ans=0;for(int i=1;i<=n;i++)ans+=m[pat[i]][i];return ans;}Processing math: 100%。

km匹配算法流程The KM matching algorithm, also known as the Kuhn-Munkres algorithm, is a classic method for solving the assignment problem in operations research. It aims to find the optimal assignment of a set of tasks to a set of agents, minimizing the total cost of the assignments. The algorithm is based on the concept of a cost matrix, where each element represents the cost of assigning a particular task to a particular agent.KM匹配算法，也称为Kuhn-Munkres算法，是运筹学中解决分配问题的经典方法。

其目标是为一系列任务找到一系列代理的最优分配，以最小化分配的总成本。

该算法基于成本矩阵的概念，其中每个元素表示将特定任务分配给特定代理的成本。

The KM algorithm proceeds in several steps. Firstly, it initializes the cost matrix and introduces slack variables to represent the difference between the cost of a particular assignment and the minimum cost row or column. Then, it searches for zero-cost assignments, which represent optimal matches between tasks and agents. If no zero-cost assignments are found, the algorithm proceeds to the next step.KM算法包括几个步骤。

指派问题的最优解法指派问题是一个最优化问题，在给定若干个任务和执行者（或机器）的情况下，要求将每个任务指派给一个执行者，并使得总体的执行成本或者效益最优。

指派问题可以用匈牙利算法（Hungarian algorithm）或者KM算法（Kuhn-Munkres algorithm）来求解，这两个算法是目前被广泛采用的指派问题求解方法。

匈牙利算法是一个具有全局优势的贪心算法，它通过不断优化当前的局部选择，最终得到全局最优解。

其基本思想是通过给任务和执行者之间的边标注权重，然后选取最小权重的边进行指派，如果发现某个任务或者执行者已经被指派，就将其它相关的边进行更新，并继续寻找最小权重的边进行指派，直到所有的任务都得到指派。

KM算法是匈牙利算法的一种更加高效的变体。

它首先将指派问题转化为一个最大权匹配问题，然后通过不断调整边的权重，使得每次迭代都可以找到一个指派边的增广路径，并更新相应的匹配结果。

KM算法的核心思想是通过对匹配结果进行调整，减小局部优势并增加全局优势。

无论是匈牙利算法还是KM算法，在最坏情况下的时间复杂度都是O(n^3)，其中n表示任务和执行者的数量。

这两个算法的主要区别在于实现的复杂度和算法的效率，KM算法相对于匈牙利算法来说具有更好的性能。

除了匈牙利算法和KM算法之外，还有一些其他的指派问题求解方法，例如启发式搜索、遗传算法等。

这些方法一般适用于指派问题的规模比较大、复杂度比较高的情况下，但是相对于匈牙利算法和KM算法，它们的效率和准确性可能会有所降低。

总之，指派问题的最优解法可以通过匈牙利算法或者KM算法来求解，具体选择哪一种方法可以根据问题的规模和复杂度来决定。

最大权匹配KM算法
KM算法（Kuhn–Munkres算法，也称为匈牙利算法）是由Kuhn于
1955年和Munkres于1957年分别提出的，用于解决二分图最大匹配问题。

该算法的核心思想是基于匈牙利算法的增广路径，通过构建一个增广路径
来不断更新匹配，直到无法找到增广路径为止。

算法流程如下：
2.从G的每个未匹配顶点开始，通过增广路径将其标记为可增广点；
3.当存在增广路径时，将匹配的边进行反向操作，直到不存在增广路径；
4. 利用增广路径的反向操作可以修改lx和ly的值，使其满足特定
约束条件；
5.通过相等子图的扩展来实现增广路径的；
6.重复步骤3-5，直到不存在更多的增广路径；
7.返回找到的最大匹配。

具体实现时，对于增广路径的可以利用DFS或BFS等方法进行，当找
到一个增广路径时，通过反向操作修改匹配情况，并更新lx和ly的值。

同时，算法还可以使用增广路径来调整优化标号，以减少匹配时间。

KM算法是一种高效的解决最大权匹配问题的方法，其时间复杂度为
O(V^3)，其中V为图的顶点数。

算法的核心思想是利用二分图中的相等子
图来查找增广路径，并通过修改顶点的标号来实现最大匹配。

总之，最大权匹配KM算法是一个解决带权无向二分图最大匹配问题
的高效算法，通过不断寻找增广路径并调整顶点的标号来实现最大权匹配。

它的思想简单而有效，可以广泛应用于各种实际问题中。

匈牙利匹配算法的原理匈牙利匹配算法（也被称为二分图匹配算法或者Kuhn-Munkres算法）是用于解决二分图最大匹配问题的经典算法。

该算法由匈牙利数学家Dénes Kőnig于1931年提出，并由James Munkres在1957年进行改进。

该算法的时间复杂度为O(V^3)，其中V是图的顶点数。

匹配问题定义：给定一个二分图G=(X,Y,E)，X和Y分别代表两个不相交的顶点集合，E表示连接X和Y的边集合。

图中的匹配是指一个边的集合M，其中任意两条边没有公共的顶点。

匹配的相关概念：1.可增广路径：在一个匹配中找到一条没有被占用的边，通过这条边可以将匹配中的边个数增加一个，即将不在匹配中的边添加进去。

2. 增广路径：一个可增广路径是一个交替序列P=v0e1v1e2v2...ekvk，其中v0属于X且不在匹配中，v1v2...vk属于Y且在匹配中，e1e2...ek在原图中的边。

3.增广轨：一个交替序列形如V0E1V1E2...EkVk，其中V0属于X且不在匹配中，V1V2...Vk属于Y且在匹配中，E1E2...Ek在原图中的边。

增广轨是一条路径的特例，它是一条从X到Y的交替序列。

1.初始时，所有的边都不在匹配中。

2.在X中选择一个点v0，如果v0已经在匹配中，则找到与v0相连的在Y中的顶点v1、如果v1不在匹配中，则(v0,v1)是可增广路径的第一条边。

3. 如果v1在匹配中，则找到与v1相连的在X中的顶点v2，判断v2是否在匹配中。

依此类推，直到找到一个不在匹配中的点vn。

4.此时，如果n是奇数，则(n-1)条边在匹配中，这意味着我们找到了一条增广路径。

如果n是偶数，则(n-1)条边在匹配中，需要进行进一步的处理。

5.如果n是偶数，则将匹配中的边和非匹配中的边进行颠倒，得到一个新的匹配。

6.对于颠倒后的匹配，我们再次从第2步开始，继续寻找增广路径。

7.重复步骤2到步骤6，直到找不到可增广路径为止，此时我们得到了最大匹配。

第一章引言在过去的四十几年里，图论已经被证明是解决几何、数论、运筹学和优化等领域中各种组合问题非常有用的工具。

而匹配是图论中的一个重要内容，也是图论的一个活跃的研究领域．匹配与独立集。

横贯等概念有着密切的关系．三四十年代Ｈａｌｌ，Ｔｕｔｔｅ［１】【２】得出了二分图上完美匹配存在性的充要条件；五十年代末Ｂｅｒｇｅ［３１等得出了最大匹配的判定条件；Ｋｕｈｎ，Ｍｕｎｋｒｅｓ［４］［５１给出了二分图上的最大权匹配的一个有效算法；六十年代Ｅｄｍｏｎｄ［Ｓ］｛７］找到了一般图上最大匹配以及最大加权匹配的第一个多项式算法；Ｇａｂｏｗ［ｓ］将Ｅｄｍｏｎｄｓ算法的复杂度从ｏ（［ｖ１４）提高到了ｏ（Ｉｖｌ３），还提出一种嵌入合并和查找技术的算法其复杂度为ｏ（ＩＶｌｌＥＩ）１９】；Ｍｉｅａｌｉ，Ｖａｚｉｒａｎｉ［１０】提出了一个最优渐进运行时间为ｏ（￣／丽例）的算法，不过这个算法难于理解和实现，以至从发表到证明其正确性花了近十年的时间．最大匹配、最大权匹配的启发式算法也有不少研究，ＤｏｒａｔｈａＥ．Ｄｒａｋｅ［ｎ］等人针对加权匹配问题提出了一种效率为；复杂度为ｏ（㈣）的算法；ＪｏｎａｔｈａｎＡｒｏｎｓｏｎ，ＭａｒｔｉｎＤｙｅｒ，Ａｌａｎ刚ｅ＝ｅ【１目等人发展了随机贪婪算法并对其中的一些性质做了深入的探讨．本文针对三分图上的最大匹配也提出了一个启发式算法，算法能够为随后的基于拉格朗日松弛的分支定界提供一个好的初始下界．管理决策中，匹配在所谓人员分配问题和最优分配阿题中有重要应用，．还有很多问题可以化归到匹配问题．通常意义上的匹配都假定图中节点在匹配中只出现１次。

如果放宽在节点上的容量约束，允许每个节点可以在匹配中重复出现多次，就变成了６一Ｍｏｔｃｈｉｎｇ问题．ＰｕｌｌｅｙＢｌａｎｋ（１９８０，１９８１）［１３】ｆ１４Ｊ对ｂ—Ｍａｃｔｈｉｎ９作了研究；ＭａｔｔｈｉａｓＭｕｌｌｅｒ．Ｈａｎｎｅｍａｎｎ，ＡｌｅｘａｎｄｅｒＳｃｈｗａｒｔｚ御咧【１５】从实现的角度进行了研究．以上的这些研究往往局限在二分图上，在管理决策中也的确出现了不少的问题可以归结到三分图上的匹配问题，笔者最近所作的项目中就出现了此类问题。

改进的km 算法流程-回复改进的KM算法流程引言KM算法，即Kuhn-Munkres算法，也被称为匈牙利算法，是一种用于解决二分图最大权匹配问题的经典算法。

它在应用中被广泛使用，例如在任务分配、资源分配、航线规划等领域。

然而，KM算法在处理大规模问题时存在效率低下的问题。

为了提高算法的性能，学者们不断进行改进和优化。

本文将介绍改进后的KM算法的流程，并逐步解释每个步骤的具体操作。

一、问题描述在介绍改进的KM算法之前，首先需要明确问题的描述。

给定一个二分图，其中左侧顶点集合为X，右侧顶点集合为Y，边权重矩阵为C。

目标是找到一个匹配M，使得M中所有边的权重之和最大。

二、改进算法的基本思路改进的KM算法主要通过两个步骤来提高效率：启发式初始化和优化的增广路径寻找。

1. 启发式初始化：将初始标号设置为最小权重值2. 优化的增广路径寻找：通过DFS（深度优先搜索）和BFS（广度优先搜索）寻找增广路径下面将详细介绍这两个步骤。

三、启发式初始化启发式初始化的目的是在算法初始阶段就为每个顶点设置一个初始标号，以便减少后续迭代中的计算量。

具体步骤如下：1. 初始化顶点集合X和Y的标号为0。

2. 对于每个左侧顶点x∈X，找到该顶点对应的最大权重，将该权重作为左侧顶点x的初始标号。

3. 更新右侧顶点y∈Y的标号为与它相连的左侧顶点的初始标号中的最大值。

四、优化的增广路径寻找优化的增广路径寻找是通过DFS和BFS结合的方式来寻找增广路径，其中DFS用于尽可能延伸已有的匹配集，而BFS用于寻找未被匹配的顶点。

1. 初始化路径集合P为空。

2. 对于每个未匹配的左侧顶点x∈X，将x添加到路径集合P中。

3. 对于路径集合P中的每个顶点u，如果u是未匹配的左侧顶点，则将u的相邻未匹配右侧顶点v添加到路径集合P中，并将v的前驱节点设置为u。

4. 如果路径集合P中存在一条从未匹配的左侧顶点x开始，以交替的形式经过已匹配的边和未匹配的边，并最终达到未匹配的右侧顶点y的路径，那么就找到了一条增广路径。

KM算法（Kuhn-Munkres）算法理论基础：可⾏顶点标号⽤l(v)表⽰顶点v的标号，w(uv)表⽰边(u,v)的权，对于赋权⼆分图G=(X,Y),若对每条边e=xy，均有l(x)+l(y)>=w(xy),则称这个标号为G的⼀个可⾏顶点标号。

赋权⼆分图的可⾏顶点标号总是存在，⼀种平凡的可⾏顶点标号是:l(v)=max w(vy),v∈X y∈Y l(v)=0,v∈Y相等⼦图设G是⼀个赋权⼆分图，l是G的可⾏顶点标号，边(u,v)上的权为w(uv)。

令El={xy∈E(G)|l(x)+l(y)=w(xy)},G中以El为边集的⽣成⼦图称为G的l 相等⼦图，记为Gl，注意Gl　的顶点集与G的顶点集相同。

定理设l是赋权⼆分图G的⼀个可⾏顶点标号，若相等⼦图有Gl有完美匹配M*，则M*是G的最⼤权完美匹配。

基本原理该算法是通过给每个顶点⼀个标号（叫做顶标）来把求最⼤权匹配的问题转化为求完备匹配的问题的。

设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。

在算法执⾏过程中的任⼀时刻，对于任⼀条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成⽴。

KM算法的正确性基于以下定理：若由中所有满⾜A[ i ]+B[j]=w[i,j]的边(i,j)构成的⼦图（称做相等⼦图）有完备匹配，那么这个完备匹配就是⼆分图的最⼤权匹配。

⾸先解释下什么是完备匹配，所谓的完备匹配就是在⼆部图中，X点集中的所有点都有对应的匹配且Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。

这个定理是显然的。

因为对于⼆分图的任意⼀个匹配，如果它包含于相等⼦图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等⼦图，那么它的边权和⼩于所有顶点的顶标和。

所以相等⼦图的完备匹配⼀定是的最⼤权匹配。

初始时为了使A[ i ]+B[j]>=w[i,j]恒成⽴，令A[ i ]为所有与顶点Xi关联的边的最⼤权，B[j]=0。