What Is Optimal Matching?

Match, usually refers to fit or match, also refers to marriage. The word "matching" has different meanings in different fields. It is both a mathematical language and a computer term. Its meaning is complex and changeable. Optimal matching refers to finding the best matching result based on the use of matching algorithms or some rules. It is generally used in the fields of pattern recognition and image processing. In addition, an extended option for the Find feature in Windows Journal that can include multiple matches.

The derivation process assumes that L is a complete bipartite weighted graph G = (X, Y, E, F) feasible point label, if M * is

Perfect match, then M * is the match with the largest weight of G. This is called optimal (or best) matching.

1. Let M be a subset of edges of graph G. If any two edges in M have no common nodes, then M is said to be a match of G; the nodes associated with M's edges are called saturation points, otherwise Become an unsaturated point.

2. Let M be a match of G = (V, E). If any match M 'of G has | M |> = | M' |, then M is said to be a maximum match of G.

3. Given a matching M of G, the roads in G that belong to M and those that do not belong to M alternately appear as interactive roads.

4. Let P be an interactive road in G that matches M. If the two endpoints of P are unsaturated points about M, then it is called an augmentable road.

5. M is the maximum match of G if and only if there is no augmentable road for M in G.

6. Let r be the maximum number of matches in the bipartite graph G and s be the minimum number of covers of its adjacency matrix, then r == s ^[1]

Practical significance

Assignment problem: n1 tasks need to be completed, and n2 individuals can take on these tasks. Because each person's expertise is different, the cost and efficiency of completing different tasks is also different. How should tasks be allocated to minimize total costs or maximize benefits?

Algorithms and steps

Use the Hungarian algorithm to solve the best matching problem, and solve the problem based on the minimum cost.

Time complexity O (m × n).

step1: After the benefit matrix is transformed, 0 elements appear in each row and column

(1) The element of each row of the benefit matrix minus the smallest element of the row;

(2) Subtract the smallest element from each column of the obtained benefit matrix.

step2: Make the assignment and find the optimal solution

(1) Starting from a row (column) with only 0 elements, circle this 0 element, which means that for the person represented by this row, there is only one task that can be assigned. Then the other 0 elements in the column (row) of the circled 0 element are crossed out, which means that the task represented by the column has been assigned, and there is no need to consider other people.

(2) Circle the 0 elements of a column (row) with only one 0 element, and at the same time delete the other 0 elements of the row (column) where the 0 element is located.

(3) Repeat steps (1) and (2) until all zero elements are circled or crossed out.

(4) If there are still 0 elements that are not circled and not crossed, and there are at least two 0 elements in the same row (column) (indicating that one of the two tasks can be assigned to this), the other 0 in the same column of the peer The 0 elements with the least total number of elements are circled (indicating that they are more selective and less polite), and the other 0 elements in the same column of the peer are crossed out. This can be repeated until all zero elements are circled or crossed out.

(5) If the number of circled elements m is equal to the order n of the matrix (here the order of the matrix refers to the smaller of the number of rows and columns of the cost / benefit matrix), then the assignment problem has been optimally solved; m <n, go to step 3.

step3: Make a minimal straight line covering all 0 elements to determine independent 0 elements in the cost / benefit matrix

(1) Tick the line without circle 0 element;

(2) Tick the column where the 0 element is crossed out in the checked row;

(3) Tick the row with the circled 0 element in the ticked column;

(4) Repeat (2) and (3) until no new tickable rows or columns can be found;

(5) Select unchecked rows and checked columns to cover all 0 elements.

(6) The sum of the number of selected rows and columns (that is, the number of straight lines) is l. If l <n, it means that the current cost / benefit matrix must be transformed to find n independent 0 elements. To do this, go to step 4. If l == n and m <n, return

(4) of step2.

step4: Add independent 0 elements

Find the smallest element in the part that is not covered by a straight line. The minimum element is subtracted from each element of the checked row, and the minimum element is added to each element of the checked column to ensure that the original 0 element is unchanged. Delete all ticks, circles, and marks, and return to step 2.