Description
The Hungarian algorithm solves instances of the assignment problem.
The assignment problem belongs to the general class of matching problems.
The idea benind it is very easy to grasp. It is about matching things
that belong in two separate sets in a way that maximizes (or minimizes)
the sum of some quantities. These quantities are typically benefits or
costs associated with each matching and expressed numerically. Each object
in one set can be matched with only one object from the other set. The
desirable outcome is the one that maximizes the sum of benefits or, conversely,
minimizes the sum of the costs.
If you are confused, let me try to clarify with an example. Consider
two spatial scenes, each having two buildings. We have a [2]x[2] table
describing how different the buildings of one scene are to those of the
other (table of differences). The scores could be from 0 to 1, with 0
meaning that there is no difference (i.e., the objects are identical)
and 1 meaning that the objects exhibit maximum dissimilarity. Alternatively,
we could have the table of similarities describing how similar each building
of one scene is to that of the other, where the meanings of 1 and 0 are
now reversed: 1 means identical and 0 totally different. In this example
we assume that the similarity is calculated as the inverse of difference
(Sim=1-Diff).
| |
A |
B |
|
|
A |
B |
|
| A' |
0.3 |
0.9 |
|
A' |
0.7 |
0.1 |
|
| B' |
0.5 |
0.2 |
|
B' |
0.5 |
0.8 |
|
| |
Differences |
|
|
Similarities |
|
The question is how to perform the mapping so as to minimize the sum
of differences or, to maximize the sum of similarities. The two statements
are equivalent and both correspond to the assignment problem's formulation.
Apparently, there are two possible scenarios:
(a) take the pairs (A, A'), (B, B') (the red combination)
and
(b) take the pairs (A, B'), (B, A') (the yellow combination).
In our example it is apparent that the winning assignment
is the red one.
The formal name of what we have done is minimum-cost (or maximum- weight)
maximum cardinality matching on a bipartite graph. Our example was trivial,
but for larger array dimensions things quickly get out of control (try
doing the same with a [4]x[4] matrix). The reason is that with brute-force
approaches one has to consider n! (n factorial) combinations where n is
the dimension of the matrix. The factorial complexity is prohibiting even
for computers, since a fast computer would need about 10,000 years for
a [20]x[20] matrix. That's a long time to wait.
The Hungarian algorithm reduces the complexity to O(N³). However,
it is a very cumbersome algorithm to implement. I
provide two versions of it, one that can be used
as a method call from within your program (clean version) and another
one that demonstrates the inner workings of the algorithm by outputting
at the console information about what is happening during each step of
operation (educational version). The educational version also contains
a wealth of comments inside the code. It is a great tool for those willing
to understand the internal operation of the algorithm but it does not
explain WHY the algorithm does the things it does...this is a matter of
theory (network flows, augmenting paths etc); it only explains WHAT it
does.
For a more thorough explanation of the problem you may check this
page that contains a nice example and the pseudocode on which I was
based to write this program. LEDA and this
page provide an explanation in terms of graph theory, and information
about other efficient matching algorithms.
Technical Info
- Release Date: May 12, 2005.
- Type of Application: Console.
- Version: 0.11
- Language: JAVA.
- Coded in: Eclipse 3.1 Milestone 6 Release.
- Minimum Requirements: JDK 1.5.0_01 or better.
- Tested on: Windows XP SP2.
Algorithm Licence Agreement
You may freely redistribute this source code, as long as the comments
in the headers of the source files—with the exception of sections
in brackets— remain unaltered.
This code is provided on an "AS-IS" basis, without any warranties,
and you use it entirely at your own risk.
Download
To download this: HungarianAlgorithm-src-0.11.zip
Archived Versions
HungarianAlgorithm-src-0.10.zip
[Software Projects Index] [All
Projects Page]
|
