匈牙利算法

发表于 更新于 阅读次数： Artalk：

Hungarian Algorithm

The Hungarian matching algorithm , also called the Kuhn-Munkres algorithm, is a $O\big(|V|^3\big)$algorithm that can be used to find maximum-weight matchings in bipartite graphs , which is sometimes called the assignment problem . A bipartite graph can easily be represented by an adj matrix, where the weights of edges are the entries. Thinking about the graph in terms of an adjacency matrix is useful for the Hungarian algorithm.

The Hungarian Algorithm for Graphs

Given: the labeling $l$, an equality graph $G_l=(V, E_l)$, an initial matching $M$ in $G_l$, and an unmatched vertex $u \in V$ and $u \notin M$

Augmenting the matching

  1. A path is augmenting for $M$ in $G_l$ if it alternates between edges in the matching and edges not in the matching, and the first and last vertices are free vertices, or unmatched, in $M$. We will keep track of a candidate augmenting path starting at the vertex $u$.

  2. If the algorithm finds an unmatched vertex $v$, add on to the existing augmenting path $p$ by adding the $u$ to $v$ segment.

  3. Flip the matching by replacing the edges in $M$ with the edges in the augmenting path that are not in $M$ (in other words, the edges in $\left.E_l-M\right)$.

Improving the labeling

  1. $S \subseteq X$ and $T \subseteq Y$, where $S$ and $T$ represent the candidate augmenting alternating path between the matching and the edges not in the matching.
  2. Let $N_l(S)$ be the neighbors to each node that is in $S$ along edges in $E_l$ such that $N_l(S)=\{v \mid \forall u \in S:(u, v) \in E_l\}$.
  3. If $N_{l}(S)=T$, then we cannot increase the size of the alternating path (and therefore can’t further augment), so we need to improve the labeling.
  4. Let $\delta_{l}$ be the minimum of $l(u)+l(v)-w(u, v)$ over all of the $u \in S$ and $v \notin T$.
  5. Improve the labeling $l$ to $l^{\prime}$ :

  • If $r \in S$, then $l^{\prime}®=l®-\delta_{l}$,

  • If $r \in T$, then $l^{\prime}®=l®+\delta_{l}$.

  • If $r \notin S$ and $r \notin T$, then $l^{\prime}®=l®$.

    $l^{\prime}$ is a valid labeling and $E_{l} \subset E_{l^{\prime}}$.

Putting it all together: The Hungarian Algorithm

  1. Start with some matching $M$, a valid labeling $l$, where $l$ is defined as the labelling $\forall x \in X, y \in Y \mid l(y)=0, l(x)=\max _{y \in Y}(w(x, y))$.
  2. Do these steps until a perfect matching is found (when $M$ is perfect):
  • (a) Look for an augmenting path in $M$.
  • (b) If an augmenting path does not exist, improve the labeling and then go back to step (a).

Python Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
TOLERANCE = 1e-6  # everything below is considered zero
MAX = 999999
def improveLabels(val):
    """ change the labels, and maintain minSlack.
    """
    for u in S:
        lu[u] -= val
    for v in V:
        if v in T:
            lv[v] += val
        else:
            minSlack[v][0] -= val

def improveMatching(v):
    """ apply the alternating path from v to the root in the tree.
    """
    u = T[v]
    if u in Mu:
        improveMatching(Mu[u])
    Mu[u] = v
    Mv[v] = u

def slack(u,v): return lu[u]+lv[v]-w[u][v]

def augment():
    """ augment the matching, possibly improving the lablels on the way.
    """
    while True:
        # select edge (u,v) with u in S, v not in T and min slack
        ((val, u), v) = min([(minSlack[v], v) for v in V if v not in T])
#         assert u in S
#         assert val > - TOLERANCE
        if val > TOLERANCE:
            improveLabels(val)
        # now we are sure that (u,v) is saturated
        assert abs(slack(u,v)) < TOLERANCE  # test zero slack with tolerance
        T[v] = u                            # add (u,v) to the tree
        if v in Mv:
            u1 = Mv[v]                      # matched edge,
            assert not u1 in S
            S[u1] = True                    # ... add endpoint to tree
            for v in V:                     # maintain minSlack
                if not v in T and minSlack[v][0] > slack(u1,v):
                    minSlack[v] = [slack(u1,v), u1]
        else:
            improveMatching(v)              # v is a free vertex
            return

def maxWeightMatching(weights):
    """ given w, the weight matrix of a complete bipartite graph,
        returns the mappings Mu : U->V ,Mv : V->U encoding the matching
        as well as the value of it.
    """
    global U,V,S,T,Mu,Mv,lu,lv, minSlack, w
    w  = weights
    n  = len(w)
    V = range(n)
    U   = range(n)
    # initialize the feasible vertex label.
    lu = [ max([w[u][v] for v in V]) for u in U]  
    lv = [ 0                         for v in V]
    Mu = {}                                      
    Mv = {}
    
    # choose a unmatched vertex u0
    while len(Mu)<n:
        free = [u for u in U if u not in Mu]      
        u0 = free[0]
        S = {u0: True}                           
        T = {}
        minSlack = [[slack(u0,v), u0] for v in V]
        augment()

    val = sum(lu)+sum(lv)
    return  val