Let g = (x, *, y) is a two-point diagram, where x = {x1, x2, ... xm}, y = {Y1, Y2, ... Yn}. Let M match one of the gs.
1) All the vertex marks (@) that is not associated with the edge of M, and is called all the vertices being unsweed. Go to 2).
2) If there is no new tag to X-based vertices, it will stop. Otherwise turn to 3).
3) When there is a vertex that is marked but not scanned, a vertex, such as Xi, with (Xi) tag Y, for example, all the vertices that are marked, such as Xi, with (Xi) tag Y, have not yet The marks are connected to Xi. Now, the vertex xi is scanned. Turn to 4) if there is no vertex that is marked but not scanned.
4) If there is no new mark to be marked in the vertex of Y, it is stopped. Otherwise, go to 5).
5) When there is a tag but not scanned vertex, a vertex that is marked but not scanned, such as Yi, with (yi) tagx, and these vertices are not tagged. Connect Yi. Now, the vertex yi is scanned. Turning to 2) if there is no vertex that is marked but not scanned.
It can also be described as:
Hungarian algorithm
The key is that there are many re-calculated nodes in the recursive process of the Hungarian algorithm, and this repetition cannot be avoided, he can't
Find a "order" to the dynamic planning to change the recursive to the recursive.
Several terms in the algorithm:
1. Two diagrams:
If the vertices of Figure g = (v, e) can be divided into two sets x, y, and satisfy x∪y = v, x∩y = φ, then G is called two
Overview;
The edge set of Figure G is represented by E (g), and the point set is represented by V (g).
2. match:
Set M is a subset of E (g), if the two edges in m are not adjacent to G, the M is a match of G. Middle
- The two endpoints on the strip are called pairing in m.
3. Saturation and unsaturation:
If a side of the match is associated with the vertex V, it is called the M saturated vertex V, and the V is M-saturation, otherwise V is M- not
Saturated.
4. Interactive:
If m is a match between two-point diagram g = (V, E). There is a road from one of the vertices in Figure G to another.
This road is composed of the edges belonging to M and the edges that are not mi, saying that this road is interactive.
5. Can increase road:
If the two ends of the interactive channel are about M unsaturated vertices, this interactive road is called augmentation. Obviously, one
The two ends of the side are unsaturated, and this edge is also a bootable road.
6. Maximum match:
If m is a match, there is no other match M ', so that M' |> | M |, the M max match is called M. Where | M |
Match the number of M.
7. Symmers:
A, B is two sets, definition
A⊕B = (A∪B) / (A ∩B)
Then A⊕B is called the symmetrical difference of A and B.
Theorem: Maximum Maximum Condition of M is G is G. There is no increase in the road.
Hall Theorem: For the two figures g, there is a match M so that all vertices of X for the M saturate is:
Any number of subsets A, and A adjacent to A, and the points are set (a), and constant: | T (a) |> = | A |
The Hungarian algorithm is idea based on sufficient proven in the Hall theorem, which is: 1. RMB initial match M;
2. If x is saturated, the third step is performed;
3. Find a unsaturated vertex X0 in X,
V1 ← {x0}, V2 ← φ
4. If T (V1) = V2 is stopped because it cannot match, it will optionally be a little y ∈T (V1) / V2;
5. If Y is saturated, turn to 6, otherwise it will be made from X0 → Y, the increased road P, M ← M⊕e (P), and 2;
6. Since Y is saturated, there is a side (Y, Z) in m, which is V1 ← V1 ∪ {z}, V2 ← V2 ∪ {y}, turn 4;
