Problem
Can anyone explain how to solve this problem ?
This problem is known as the assignment problem. It’s a classical problem so I’m sure you will find many tutorials to solve it if you search online. I’m not familiar with it myself, but a quick search reveals the Hungarian Algorithm is commonly applied.
1 Like
This is one of the classic problems of type Assignment problem or Hungarian Problems!
Say we have N workers and N jobs that should be done. For each pair (worker, job) cost of job is known.
We have to complete all tasks while minimizing total cost.
The algorithm works as follows:
If a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.
- For each row of the matrix, find the smallest element and subtract it from every element in its row.
- Do the same (as step 1) for all columns.
- Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
- Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and
we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must
proceed to step 5. - Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and
then add it to each covered column. Return to step 3.
Check this topcoder link to get to know about the algorithm behind solving this:
Hungarian Algorithm
1 Like