| WXYZ 的个人资料WXYZ的异人馆照片日志列表 |  工具  帮助 |
|
11月4日 km算法 很久之前说好要把二分图最佳权匹配的算好写好贴上来，可惜由于能力的缺乏，只写出O(n^4)的，令我好不满意，我就叫师兄发个O(n^3)的来参考参考。结合网上的一些文章，大概就一知半解吧，让我复述我就写不出来了，只好把其它人的贴上来。下面几段来自wc的小屋。
然后就是KM的时间界。这里略去KM的步骤不谈。众所周知，KM弄不好就会写出O(n^4)的算法，而实际上是存在O(n^3)的实现的。那么O(n^4)究竟是慢在什么地方呢？这个就需要搞清楚O(n^4)的4究竟是怎么来的。
每个点都需要作一次增广，所以有一个n的循环。每个循环内部，每次可能无法得到一条增广路，需要新加入一个y顶点，然后重新寻找增广路。一次最少加进1个点，所以最多加入n次。每次重新找一遍增广路n^2，更新距离标号需要扫描每一条边n^2，所以迭加起来O(n)*O(n)*O(n^2)，结果自然就是O(n^4)。 第一层和第二层循环似乎没有很好的方法可以把它搞掉，所以我们只能从第三层，也就是每次的O(n^2)入手。这一层包括两个部分，一个是增广路的n^2，一个是更新标号的n^2，需要将二者同时搞掉才能降低总共的复杂度。注意更新标号之后有一个最重要的性质，那就是 原来存在的合法边仍然合法，更新只是将不合法的边变得合法。所以当我们找到一次交错树，没有增广路之后，下次再寻找的时候完全没有必要重新开始，因为原先有的边更新之后还有，所以完全可以接着上一次得到的交错树继续寻找。那么应该从什么地方继续号、开始搜索呢？很明显是那些新加进的点，也就是新进入的那些y点。这样虽然不知道每次更新标号会又扫描多少次，但是每条边最多也就被扫描一次，然后被添加进交错树一次。所以这一块，n层循环总的复杂度是O(n^2)。按照这样描述的话，用dfs似乎没有可以接着上一次找的方法，所以只能用bfs来写增广路的搜索了。 然后就是重标号。这一段实际上是由重新扫了一次边，然后对x在树中而y不在的边进行侦测，然后重新标号。想把这个搞掉似乎是有些困难，但是我们先做的是增广路搜索然后才是标号，增广路搜索的时候不也是要扫边么？要是能在bfs的时候记录一下什么信息，到时候直接取用不就好了？所以，做法就是在bfs的时候，对于每个扫到的这种边，更新一下对应的y顶点的标号，这个标号的意义就是y点连接的所有这种边当中可松弛的最小值，定义为slack[y]。然后每次更新的时候扫一下所有的y，对于所有没在交错树中的y，找到最小slack[y]，然后更新就可以了。注意由于我们要接着上一次进行bfs，所以上一次算出来的标号也要留下来。别忘了重标号之后每个y点的slack[y]也要同样更新，这样每次寻找标号并更新的复杂度就是O(n)了，n层重标号最多也就是O(n^2)，然后bfs的O(n^2)，增广的O(n)，所以对于每个点，想对匹配进行增广，复杂度就是O(n^2)，n个点每个点来一次自然就是O(n^3)了。 然后再配合下面的程序吧，防止突发事件资源流失，贴上来好了，以备不时之需。
/*二分图最佳权匹配O(n^3)算法*/
const int max=1000; const int inf=10000; //设定上限 int a[max][max]; //图 int x[max],y[max]; //分别保存x与y的连结信息 int lx[max],ly[max]; //保存x与y的界值 void km(int n) { int i,j,k,p,q,temp; int b[max]; //bfs表 int link[max]; //保存本轮是否搜过并记录结点 memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); for (i=0;i<n;i++) for (j=0;j<n;j++) if (a[i][j]>lx[i]) lx[i]=a[i][j]; //初始化界值 memset(x,-1,sizeof(x)); memset(y,-1,sizeof(y)); for (i=0;i<n;) //n次迭代 { memset(link,-1,sizeof(link)); p=0; q=1; b[0]=i; while (p<q&&x[i]<0) { k=b[p]; for (j=0;j<n&&x[i]<0;j++) if (lx[k]+ly[j]<=a[k][j]&&link[j]<0) { b[q]=y[j]; q++; link[j]=k; if (y[j]<0) { while (j>=0) { k=link[j]; y[j]=k; temp=x[k]; x[k]=j; j=temp; } } } p++; } //寻找增广路 if (x[i]>=0) i++; else { //修改界值 temp=inf; for (p=0;p<q;p++) { k=b[p]; for (j=0;j<n;j++) if (link[j]==-1&&temp>lx[k]+ly[j]-a[k][j]) temp=lx[k]+ly[j]-a[k][j]; } for (p=0;p<q;p++) lx[b[p]]-=temp; for (j=0;j<n;j++) if (link[j]>=0) ly[j]+=temp; } } return; } 修改界值部分好难明…… 评论 (5)
引用通告此日志的引用通告 URL 是： http://wxyz202.spaces.live.com/blog/cns!D4DC981555112325!533.trak 引用此项的网络日志
|
|
|
