The Hungarian Algorithm

匈牙利算法又称KM算法，这是一个组合优化算法，

解决分配问题，维基地址：http://en.wikipedia.org/wiki/KM_algorithm

 

Assumption: There are n “jobs” and n “machines”.

Step 0: If necessary, convert the problem from a maximum assignment into a minimum
assignment. We do this by letting C = maximum value in the assignment matrix.
Replace each cij with C − cij . (see example 2).

Step1: From each row subtract off the row min.

Step 2: From each column subtract off the row column min.

Step 3: Use as few lines as possible to cover all the zeros in the matrix. There is no easy
rule to do this – basically trial and error.
Suppose you use k lines.
• If k < n, let m be the minimum uncovered number. Subtract m from every
uncovered number. Add m to every number covered with two lines. Go back
to the start of step 3.
• If k = n, goto step 4.

Step 4: Starting with the top row, work your way downwards as you make assignments.
An assignment can be (uniquely) made when there is exactly one zero in a row. Once
an assignment it made, delete that row and column from the matrix.
If you cannot make all n assignments and all the remaining rows contain more than
one zero, switch to columns. Starting with the left column, work your way rightwards
as you make assignments.
Iterate between row assignments and column assignments until you’ve made as many
unique assignments as possible. If still haven’t made n assignments and you cannot
make a unique assignment either with rows or columns, make one arbitrarily by
selecting a cell with a zero in it. Then try to make unique row and/or column
assignments. (See the examples below).