Shulou(Shulou.com)06/01 Report--

Today, I will talk to you about the detailed explanation of the KM algorithm and how to use java, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following contents for you. I hope you can get something according to this article.

Basic concept of Hungarian algorithm

Bipartite graph: bipartite graph is also called bipartite graph. To put it simply, if the points in the graph can be divided into two groups, and all the edges cross the boundaries of the group, then this is a bipartite graph. To be exact, the vertices of a graph are divided into two disjoint sets U and V, so that each edge connects the vertices in U and V respectively. If such a partition exists, the graph is a bipartite graph. An equivalent definition of a bipartite graph is a graph that does not contain "rings with odd edges". Generate subgraph: the subgraph contains all the vertices of the original graph

Matching: in popular terms, a match is a set of edges in which any two edges have no common vertices. Definition: for a given bipartite graph G, in the subgraph M of G, any two edges in the edge set {E} of M do not depend on the same vertex, then M is called a match.

Maximum matching: of all the matches in a graph, the matching with the largest number of edges is called maximum matching.

Complete matching: if a matching M of a graph G associates every vertex of G with an edge in matching M, then M is called complete matching (complete matching), and complete matching must be the maximum matching.

Cymbal

As shown in the figure: Fig.1 is a bipartite graph, so it is more intuitive to change it to the form of Fig.2; the red line part of Fig.3 is a match; Fig.4 is a maximum match and a complete match.

A Hungarian algorithm for finding the maximum matching of graphs

The most direct and violent way to find the maximum match is to find all the matches and keep the ones with the most edges. The complexity of this method is an exponential function of the number of edges. The Hungarian algorithm is a more efficient method.

Augmented path: if P is a path connecting two unmatched points in a graph G, and the edges that belong to matching M and edges that do not belong to M appear alternately on P, then P is called an augmented path relative to M.

Cymbal

As shown in the figure above, Fig.5 red is the match and Fig.6 is an augmented path relative to the match.

From the definition of augmentation path, three conclusions can be drawn:

The path length of P must be odd, and neither the first edge nor the last edge belongs to M.

P can get a larger matching M1 after the reverse operation.

M is the maximum match of G if and only if there is no augmentation path relative to M.

Hungarian algorithm: using augmented path to find the maximum match (proposed by Hungarian scientist Edmonds in 1965); its framework is as follows:

Set M to empty

An augmented path P is found, and a larger matching M1 is obtained by taking the inverse operation.

Repeat step 2 until the augmentation path cannot be found.

Implementation of Hungarian algorithm (java)

Cymbal

There are two routing methods for augmented paths, one is deep search (DFS) and the other is wide search (BFS). As shown above, the blue line is the first matching subgraph, now look for the augmented path from x1, if it is DFS: first, X1 finds y0 and finds that y0 has been matched by x0, then goes deep into x0, finds a new matching point for x0, finds that x0 can match y2, makes x0 match with y2, and then matches x1 with y0 to get the second matching subgraph (red). Now, starting from x2, X2 finds a match for Y0, but finds that Y0 has been matched by x1, so it goes deep into x1 to find a new matching node for x1, and it turns out that x1 has no other matching node, so the match fails. X2 then looks for Y1 and finds that Y1 can match, so a new augmentation path is found and x2-y1 is added to the match.

For the DFS implementation code, please see my code java implementation | GitHub

Principle of KM algorithm KM algorithm

For the weighted complete bipartite graph, finding the weight and the maximum match is called finding the best match; the direct exhaustive method: the efficiency is nasty; using the KM algorithm.

Theorem: let M be a complete match of a weighted complete bipartite graph G, and give each vertex a feasible top label (the feasible mark of the I x vertex is denoted by LX [I], and the feasible mark of the j y vertex is denoted by Ly [j]). If for all edges (iMagazine j) in G, there is LX [I] + ly [j] > = w [iForce j] (w [iArt j] denotes the weight of edges). And for all edges (iMagnej) in M, if LX [I] + ly [j] = w [iMagnej] holds, then M is a best match of a graph G. It's easy to prove.

For any G and M, feasible markers exist.

For a bipartite graph G and a set of feasible markers, a generated subgraph (which needs to include all vertices) formed by all edges satisfying the feasible label boundary condition (LX [I] + ly [j] = w [iMagazine j]) is called its equivalent subgraph (equivalent subgraph). On this equivalent subgraph, a complete match is found. If a complete match exists, then the complete matching M is the maximum weight matching of the graph G, and the maximum weight is equal to the sum of all feasible targets. If the complete matching does not exist, the feasible index is modified and the optimal edge is added to the equivalent subgraph with the idea of greed. KM algorithm is a method to modify the feasible top mark step by step, so that the corresponding equivalent subgraph is enlarged step by step (adding edges), and finally there is a complete match.

Flow and example of KM algorithm

Kuhn-Munkras algorithm flow:

Initialize the value of the feasible top mark

Using Hungarian algorithm to find complete matching in equivalent subgraph

If no complete match is found, modify the value of the feasible top mark

Repeat (2) (3) until a complete match of the equivalent subgraph is found.

An example to explain the algorithm process:

The weighted bipartite diagram is as follows:

Cymbal

Cymbal

Find the augmentation path from x0 and find x0-y4 Then, if the augmentation path cannot be found from x1, it is necessary to modify the top label and add an optimal new edge to the equivalent subgraph: the searched path is x1-y4-x0 (using the Hungarian method DFS), and the set of X vertices on the path is S (x0Powerx1), and the set of Y vertices is T (y4). For all points xi in S and yj not in T, calculate d=min {(L (xi) + L (yj)-weight (xiyj))}. Subtract the top mark of the point in S minus the top mark of the point in d ~ (th) and add d to keep the top mark still feasible. (the meaning of this d calculation is greedy, two cases: let x0 match other points, x1 match Y4; x0 still match Y4, x1 find other points to match. D calculates to find a new edge, so that x0 and x1 are matched, compared with the illegal matching of x0 and x1 with Y4, the loss of weight is the least. Specifically, the minimum dicil (X1) + L (Y0)-weight (X1Y0) = 2 is calculated at this time. After relaxing the top label, the equivalent subgraph is obtained as above, adding an edge x1-y0 to re-find the augmented path for x1 and find the x1-y0. In this case, the matching weight sum is 9 / 6 / 15. The original illegal matching weight sum is 9: 8: 17, and the weight of "loss" is at least 2 (that is, adding another non-x1-y0 edge such as x0-y2, the weight of loss is 3, greater than 2, that is, greedy idea, "loss is minimum").

The original time complexity of KM algorithm is O (n4), n nodes find n augmentation paths, in a certain search for augmentation paths, the top mark is changed at most n times, and it takes N2 to modify the relaxation amount of the top mark, which can be improved to O (n3) time complexity: the slack value is calculated by the way when looking for the augmentation path.

After reading the above, do you have any further understanding of the detailed explanation of KM algorithm and how to implement it using java? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.