带权二分图的最优匹配 Kuhn-Munkres算法 收藏.docx

带权二分图的最优匹配 Kuhn-Munkres算法 收藏 分工问题如下：某公司有工作人员x1,x2,.,xn,他们去做工作y1,y2,.,yn,每人适合做其中的一项或几项工作，每个人做不同的工作的效益不一样，我们需要制定一个分工方案，使公司的总效益最大，这就是所谓最佳分配问题， 它们数学模型如下：数学模型： G是加权完全二分图，V(G)的二分图划分为X，Y；X=x1,.,xn,Y=y1,y2,.yn,w(xiyi)=0是工作人员xi做yi工作时的效益，求权最大的完备匹配，这种完备匹配称为最佳匹配。这个问题好象比较的棘手，用穷举法的话举也举死了，效率很低。本节给出一种有效算法，为此，先引入一个定义和一个定理。定义1 映射l:V(G)-R，满足：任意xX,任意yY,成立l(x)+l(y)=w(xy),则称l(v)是二分图G的可行顶标；令El=xy|xyE(G),l(x)+l(y)=w(xy),称以El为边集的G之生成子图为相等子图，记为Gl可行顶标是存在的，例如l(x)=max w(xy),xX;l(y)=0, yY.定理1 Gl的完备匹配即为G的最佳匹配。证：设M*是Gl的一个完备匹配，因Gl是G的生成子图，故M*也是G的完备匹配。M*中的边之端点集合含G的每个顶点恰一次，所以W(M*)=w(e)=l(v) (eM*,vV(G).另一方面，若M是G中任意一个完备匹配，则W(M)=w(e)=W(M)，即M*是最佳匹配，证毕。定理1告知，欲求二分图的最佳匹配，只需用匈牙利算法求取其相等子图的完备匹配；问题是，当Gl中无完备匹配时怎么办？Kuhn和Munkras给出修改顶标的一个算法，使新的相等子图的最大匹配逐渐扩大，最后出现相等子图的完备匹配。Kuhn-Munkras算法： (0) 选定初始的可行顶标l,确定Gl,在Gl中选取一个匹配M。(1) X中顶皆被M许配，止，M即为最佳匹配；否则，取Gl中未被M许配的顶u,令S=u,T为空。(2) 若N(S)真包含T，转(3)；若N(S)=T，取al=min(l(x)+l(y)-w(xy)(xS,yT),l(v)-al,vS;l(v)= l(v)+al,vT;l(v),其它。l=l,Gl=Gl。(3) 选N(S)-T中一顶y,若y已被M许配，且yzM,则S=Sz,T=Ty,转(2)；否则，取Gl中一个M的可增广轨P(u,y),令M=ME(P)，转(1)。上面的算法看得有点莫名，改那个可行顶标怎么改改就好了？还是得看盾例子例1 已知K5,5的权矩阵为y1 y2 y3 y4 y5x1 3 5 5 4 1x2 2 2 0 2 2x3 2 4 4 1 0x4 0 1 1 0 0x5 1 2 1 3 3求最佳匹配，其中K5,5的顶划分为X=xi,Y=yi,i=1,2,3,4,5.解：(1)取可行顶标l(v)为 l(yi)=0,i=1,2,3,4,5；l(x1)=max(3,5,5,4,1=5,l(x2)=max2,2,0,2,2=2,l(x3)=max(2,4,4,1,0=4,l(x4)=max0,1,1,0,0=1,l(x5)=max1,2,1,3,3=3.(2) Gl及其上之匹配见图7.12。这个图中(G-x2)=3,由Tutte定理知无完备匹配。需要修改顶标。(3) u=x4,得S=x4,x3,x1,T=y3,y2,N(S)=T,于是al=min(l(x)+l(y)-w(xy)=1. (xS,yT)x1,x2,x3,x4,x5的顶标分别修改成4,2,3,0,3；y1,y2,y3,y4,y5的顶标分别修改成0,1,1,0,0。(4) 用修改后的顶标l得Gl及其上面的一个完备匹配如图7.13。图中粗实线给出了一个最佳匹配，其最大权是2+4+1+4+3=14。我们看出：al0；修改后的顶标仍是可行顶标；Gl中仍含Gl中的匹配M；Gl中至少会出现不属于M的一条边，所以会造成M的逐渐增广。得到可行顶标后求最大匹配： 书上这部分没讲，实际上是这样的，对于上面这个例子来说，通过Kuhn-Munkres得到了顶标l(x)=4,2,3,0,3,l(y)= 0,1,1,0,0,那么，对于所有的l(xi)+l(yj) = w(i,j)，在二分图G设置存在边w(i,j)。再用匈牙利算法求出最大匹配，再把匹配中的每一边的权值加起来就是最后的结果了。view plaincopy to clipboardprint?#include #include #include / 使用其中的 min 函数 using namespace std; const int MAX = 1024; int n; / X 的大小 int weight MAX MAX; / X 到 Y 的映射（权重） int lx MAX, ly MAX; / 标号 bool sx MAX, sy MAX; / 是否被搜索过 int match MAX; / Y(i) 与 X(match i) 匹配 / 初始化权重 void init (int size); / 从 X(u) 寻找增广道路，找到则返回 true bool path (int u); / 参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配 int bestmatch (bool maxsum = true); void init (int size) / 根据实际情况，添加代码以初始化 n = size; for (int i = 0; i n; i +) for (int j = 0; j n; j +) scanf (%d, &weight i j); bool path (int u) sx u = true; for (int v = 0; v n; v +) if (!sy v & lxu + ly v = weight u v) sy v = true; if (match v = -1 | path (match v) match v = u; return true; return false; int bestmatch (bool maxsum) int i, j; if (!maxsum) for (i = 0; i n; i +) for (j = 0; j n; j +) weight i j = -weight i j; / 初始化标号 for (i = 0; i n; i +) lx i = -0x1FFFFFFF; ly i = 0; for (j = 0; j n; j +) if (lx i weight i j) lx i = weight i j; memset (match, -1, sizeof (match); for (int u = 0; u n; u +) while (1) memset (sx, 0, sizeof (sx); memset (sy, 0, sizeof (sy); if (path (u) break; / 修改标号 int dx = 0x7FFFFFFF; for (i = 0; i n; i +) if (sx i) for (j = 0; j n; j +) if(!sy j) dx = min (lxi + ly j - weight i j, dx); for (i = 0; i n; i +) if (sx i) lx i -= dx; if (sy i) ly i += dx; int sum = 0; for (i = 0; i n; i +) sum += weight match i i; if (!maxsum) sum = -sum; for (i = 0; i n; i +) for (j = 0; j n; j +) weight i j = -weight i j; / 如果需要保持 weight 原来的值，这里需要将其还原 return sum; int main() int n; scanf (%d, &n); init (n); int cost = bestmatch (true); printf (%d , cost); for (int i = 0; i X %d , i, match i); ret