New Topic/Question
The matrix is set up in the following form:
X/Y | 1 | 2 | 3 | 4 | 5 A | 4 5 5 4 6 B | 6 7 7 5 8 C | 6 5 2 5 4 D | 4 3 4 7 6 E | 9 7 7 6 10
The steps of the Hungarian algorithm are as follows:
-If the matrix isn't square, make it square by adding rows of 0's
-Reduce the matrix (note that this is NOT a Linear Algebra reduction)
-Pick a greedy matching on the 0's
-Find the optimal matching with the bipartite matching algorithm
-If the matching isn't optimal, find the minimal Cover (found X vertices + unfound Y vertices).
-Based on the cover, find the minimal uncovered entry (call it m). Subtract m from every uncovered entry and add m to every double-covered entry.
-Pick a new greedy matching on the 0's and repeat
Some Pseudo-Code:
function hungarianAlgorithm(SquareCostMatrix matrix)
foreach row in matrix
min = findMin(row)
foreach element in row
element <-- element - min
end foreach
end foreach
foreach column in matrix
min = findMin(col)
if min > 0
foreach element in column
element <-- element - min
end foreach
end if
end foreach
while matrix.getNumberMatches() < matrix.getX().size()
pickMatching(matrix)
augmentMatching(matrix)
minCover <-- matrix.getMinCover()
foreach element in minCover
if matrix.x.contains(element)
cover row at element
end if
else
cover column at element
end else
end foreach
min <-- findMinUncovered(matrix)
foreach row in matrix
foreach element in row
if isCovered(element) == FALSE
element <-- element - min
end if
else if isDoubleCovered(element)
element <-- element + min
end if
end foreach
end foreach
end while
end function
function findMinUncovered(Matrix matrix)
min <-- infinity
foreach row in matrix
foreach element in row
if isCovered(element) == FALSE AND element < min
min <-- element
end foreach
end foreach
return min
end foreach
function pickMatching(Matrix matrix)
foreach row in matrix
foreach element in row, indexed i
if element == 0 AND hasMatching(column[i]) == FALSE
match(element)
end if
end foreach
end foreach
end function
Now, let's work through an example with the following cost matrix:
X/Y | 1 | 2 | 3 | 4 | 5 A | 4 5 5 4 6 B | 6 7 7 5 8 C | 6 5 2 5 4 D | 4 3 4 7 6 E | 9 7 7 6 10
Each row has the following minimums:
A- 4
B- 4
C- 2
D- 3
E- 6
After subtracting the row minimums from each row, the matrix reduces to:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0 1 1 0 2 B | 1 2 2 0 3 C | 4 3 0 3 2 D | 1 0 1 4 3 E | 3 1 1 0 4
The only non-zero column minimum is at column 5, where the min = 2. Reducing the matrix again, we get:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0 1 1 0 0 B | 1 2 2 0 1 C | 4 3 0 3 0 D | 1 0 1 4 1 E | 3 1 1 0 2
Picking a greedy matching (using a * to denote a matched edge) on the 0's, we get:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0* 1 1 0 0 B | 1 2 2 0* 1 C | 4 3 0* 3 0 D | 1 0* 1 4 1 E | 3 1 1 0 2
The bipartite matching algorithm produces the forest: E --- 4 -*- B, meaning the matching is maximal. So it is necessary to reduce the matrix yet again. The min cover for this matching is: {4, A, C, D}. The double-covered elements are A4, C4, and D4. The remaining elements in the A, C, and D rows are single covered, as are the remaining elements in column 4.
The minimum amongst the uncovered elements is 1, so subtract it from the uncovered elements and add it to the double-covered elements. The updated matrix is as follows, with the greedy matching the same as the last one:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0* 1 1 1 0 B | 0 1 1 0* 0 C | 4 3 0* 4 0 D | 1 0* 1 5 1 E | 2 0 0 0 1
Augmenting the matching leaves the final matrix:
X/Y | 1 | 2 | 3 | 4 | 5 A | 0* 1 1 1 0 B | 0 1 1 0* 0 C | 4 3 0 4 0* D | 1 0* 1 5 1 E | 2 0 0* 0 1
Looking at the original cost matrix, that leaves the final cost at:
3 + 2 + 6 + 4 + 3 = 18
MultiQuote
| 