Hungarian method

The Hungarian method is an algorithm for solving the assignment problem. It solves it by finding the minimum cost perfect matching (best match) in a bipartite graph. It assigns tasks to workers where each worker can do a task with a given cost. We want the most cost-efficient assignment.

It is particularly suited for artificial intelligence tasks as a heuristic function, particularly in Sokoban, where like the assignment problem, we want a unique box/storage mapping.

Procedure

We first need a cost matrix. For $n$ jobs and $m$ individuals, it’ll have a space of $\mathcal{O}(nm)$. We first do matrix transformations:

• Find the minimum element in each row. Then subtract each element in the row by the min element.
• Find the min element in each column. Then subtract each element in the column by the min element.

final result

• for the “simple assignment problem”
  • $n$ individuals qualified for $n$ jobs
  • individual $n_i$ may be qualified for a subset of the jobs
• solves assignment problem by finding minimum cost perfect matching in a bipartite graph
  • assigning tasks to workers where each worker can do a task with a given cost
  • we want most cost-efficient assignment

Quick links

• The Hungarian method for the assignment problem, by H.W. Kuhn — the original 1955 paper that introduced the algorithm
• Hungarian Method at Byju’s — a more accessible overview of the algorithm

See also

• Ford-Fulkerson algorithm, an extension of the method for maximum flow problems