匈牙利算法

转自：http://hi.baidu.com/kukumayas/blog/item/a43c39384af633d3b311c753.html

设想一个公司里有A, B, C三种工具, 有员工1, 2, 3, 4号. 这四位员工分别能操作的机型为情况为:

1: A, B

2: A, C

3: A

若想充分发挥所有人和所有机器的能力, 让生产力最大化, 我们不难安排1->B, 2->C, 3->A.

当一个公司非常大, 机器种类非常多, 员工非常多, 那么此时就需要一种有效的算法来解决人员分配的问题. 而匈牙利算法就可以做到这一点.

上述问题中, 员工和机器可以看作一个二部图(或二分图, 见http://en.wikipedia.org/wiki/Bipartite_graph), 设G=(V,E)是一个无向图, 如果顶点V可分割为两个互不相交的子集(A,B), 并且图中的每条边（i,j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A, j in B)，则称图G为一个二分图. 上例中, 员工二分图的一个集合, 机器是另一个集合.

匈牙利算法进行时需要找一个叫做"交错路径"(或者交错树)的东西, 下边第一个图黑色实现标出了一个匹配, 而第二个图则给出了这个匹配的交错路径. 交错路径是针对匹配而言的.

匈牙利算法的一个案例:

1、起始没有匹配

2、选中第一个x点找第一跟连线

3、选中第二个点找第二跟连线

4、发现x3的第一条边x3y1已经被人占了，找出x3出发的的交错路径x3-y1-x1-y4，把交错路中已在匹配上的边x1y1从匹配中去掉，剩余的边x3y1 x1y4加到匹配中去

5、同理加入x4,x5。

匈牙利算法可以深度有限或者广度优先，本文的示例采用深度优先，即x3找y1,y1已经有匹配，则找交错路。若是广度优先，应为：x3找y1,y1有匹配，x3找y2。

模版：

 1 bool 寻找从k出发的对应项出的可增广路
 2 {
 3     while (从邻接表中列举k能关联到顶点j)
 4     {
 5         if (j不在增广路上)
 6         {
 7             把j加入增广路;
 8             if (j是未盖点 或者 从j的对应项出发有可增广路)
 9             {
10                 修改j的对应项为k;
11                 则从k的对应项出有可增广路,返回true;
12             }
13         }
14     }
15     则从k的对应项出没有可增广路,返回false;
16 }
17 void 匈牙利hungary()
18 {
19     for i->1 to n
20     {
21         if (则从i的对应项出有可增广路)
22             匹配数++;
23     }
24     输出 匹配数;
25 }