posts - 43,  comments - 9,  trackbacks - 0
图采用矩阵存储,下标从1开始。

匈牙利匹配算法的理论和证明不复杂,就是不断寻找两个端点都是未浸润点的交替路径,把路径上的边匹配状态全部取反。每次操作,图的匹配数都增加1。为方便描述,将二部图划分为X和Y两个部集。
此算法有几个性质:
1.算法只需以某一个部集(可以是X或Y)中的所有未浸润点为交替路径的起始点,展开寻找。
2.X中的某个点,只有在以它为起始点进行过交替路径搜索后,才有可能变为浸润点。
3.以X中的某个点为起始点,如果无法找到交替路径,那么以后不论何时以它为起始点,都不可能找到交替路径。
4.据1,选择处理X集,由2,3知X集中的所有点最多只需处理一次。

伪代码:
 1 SEARCH(Vi):
 2     SEARCH AUGMENT PATH STARTING FROM Vi
 3     IF FOUND THEN RETURN TRUE
 4     ELSE RETURN FALSE
 5 MATCHING(G(X,Y)):
 6     ANS:=0
 7     FOR EACH VERTEX Vi IN SET X
 8         T:=SEARCH(Vi)
 9         IF T=TRUE
10             ANS:=ANS+1
11         END IF
12     END FOR


寻找交替路径这个过程有BFSDFS两种方式。

DFS:
 1 int w[NX][NY]; //X中的点到Y中的点的连接矩阵,w[i][j]是边<Vxi,Vyj>的权
 2 int m[NY]; //Vyi的匹配对象
 3 int v[NY]; //在一次DFS中,Vyi是否被访问过
 4 bool dfs(int k){ //以Vxk为起点找交替路径
 5     int i;
 6     for(i=1;i<=N;i++){
 7         if(!v[i] && w[k][i]){ //如果Vyi未访问过,而且Vxk,Vyi有边连接
 8             v[i]=1;
 9             if(!m[i] || dfs(m[i])){ //如果Vyi是未浸润点,或者以Vyi原来的匹配点为起始,有扩张路径
10                 m[i]=k;
11                 return true//扩张成功
12             }
13         }
14     }
15     return false;
16 }

这个算法也可以从类似“贪心”的角度理解:一个X中的点Vx0,如果找到某个能到达的Y点Vy0,就暂时把它“据为己有”,然后看Y的“原配X点”还能不能找到别的Y点配对,如果能,那么Vx0和Vy0就配对成功,否则不成功,Vx0继续寻找别的Vy。

BFS:
这是我在某些算法书上看到的BFS版本,需要用变量(或变量数组)tag记录扩展目标。代码中,我改为用que[i]的bit1记录:
 1 int w[NX],ma[NY];
 2 int que[NX+NY],pq,sq; //广搜队列
 3 int pax[NX],pay[NY]; //记录交替路径
 4 bool bfs(int r){
 5     int i,j,k,tag; //tag,记录交替路径的下一步要扩展X中的点(tag==1时),还是Y中的点(tag==0时)
 6     memset(pax,0,sizeof(pax));
 7     memset(pay,0,sizeof(pay));
 8     que[0]=(r<<1);
 9     pq=0; sq=1;
10     while(pq<sq){
11         k=que[pq]>>1; tag=que[pq]&1;
12         if(tag==0){ //process set X, look for unvisited vex in Y
13             for(i=1;i<=N;i++){
14                 if(!pay[i] && w[k][i]){
15                     pay[i]=k;
16                     if(!ma[i]){ //是未浸润点,扩展路径搜索完毕
17                         for(j=i;j;j=pax[pay[j]]){
18                             ma[j]=pay[j];
19                         }
20                         return true;
21                     }
22                     else//这个Y点不是未浸润点,入队
23                         que[sq++]=(i<<1)|1;
24                     }
25                 }
26             }
27         }
28         else//Vyk不是未浸润点,路径必须沿着它所在的匹配边扩展
29             que[sq++]=(ma[k]<<1);
30             pax[ma[k]]=k;
31         }
32         pq++;
33     }
34     return false;
35 }


其实,在遇到浸润的Vyi时,由于下一步只能沿着它的匹配点Vxj走,即排队轮到Vyi时,必定是Vxj被加入队列。因此,只要令队列que仅存放X集的点,每次遇到浸润的Vyi,把它的匹配点Vxj加入队列。这样就省去了分支,减小了代码量。
实现:
 1 int w[NX],ma[NY];
 2 int que[NX+NY],pq,sq;
 3 int pax[NX],pay[NY];
 4 bool bfs(int r){
 5     int i,j,k;
 6     memset(pax,0,sizeof(pax));
 7     memset(pay,0,sizeof(pay));
 8     que[0]=r;
 9     pq=0; sq=1;
10     while(pq<sq){
11         k=que[pq++];
12         for(i=1;i<=N;i++){
13             if(!pay[i] && w[k][i]){
14                 pay[i]=k;
15                 if(!ma[i]){ //free vex, augment path found
16                     for(j=i;j;j=pax[pay[j]]){
17                         ma[j]=pay[j];
18                     }
19                     return true;
20                 }
21                 else//add Y's matched vex to que
22                     pax[ma[i]]=i;
23                     que[sq++]=ma[i];
24                 }
25             }
26         }
27     }
28     return false;
29 }

显然,单纯的匹配问题,BFS和DFS复杂度都是O(mn),但DFS编码难度小很多。
还有一种Hopcroft-Karp算法,复杂度是O(msqrt(n)),只能用BFS实现,暂时还没深入研究。
然而,解决带权匹配问题时,DFS只能做到O(n^4),而BFS可以做到O(n^3)。

posted on 2009-02-15 21:55 wolf5x 阅读(1766) 评论(0)  编辑 收藏 引用 所属分类: algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜