Package elki.utilities.datastructures
Class KuhnMunkres
- java.lang.Object
-
- elki.utilities.datastructures.KuhnMunkres
-
- Direct Known Subclasses:
KuhnMunkresWong
@Reference(authors="H. W. Kuhn",title="The Hungarian method for the assignment problem",booktitle="Naval Research Logistics Quarterly 2",url="https://doi.org/10.1002/nav.3800020109",bibkey="doi:10.1002/nav.3800020109") @Reference(authors="J. Munkres",title="Algorithms for the Assignment and Transportation Problems",booktitle="Journal of the Society for Industrial and Applied Mathematics 5(1)",url="https://doi.org/10.1137/0105003",bibkey="doi:10.1137/0105003") public class KuhnMunkres extends java.lang.Object
Kuhn-Munkres optimal matching (aka the Hungarian algorithm). This is a popular algorithm to find the best 1:1 matching to minimize the cost. The original version has a worst case of O(n4) albeit sometimes given as O(n³). Empirically, this version is O(n³), too, but literature seems to disagree. For an improved O(n³) version, seeKuhnMunkresWong
.As a rule of thumb, a 1000x1000 problem may take around 30-60 seconds depending on your CPU, a 10kx10k problem may hence take 8-16 hours already.
References:
H. W. Kuhn
The Hungarian method for the assignment problem
Naval Research Logistics Quarterly 2J. Munkres
Algorithms for the Assignment and Transportation Problems
Journal of the Society for Industrial and Applied Mathematics 5(1)TODO: also implement the Jonker-Volgenant variant!
- Since:
- 0.8.0
- Author:
- Erich Schubert
-
-
Field Summary
Fields Modifier and Type Field Description (package private) int[]
cmark
Column marks.(package private) double[][]
cost
Cost matrix(package private) int[]
csel
Selected ("starred") row per column, -1 if not selected.private static Logging
LOG
Class logger(package private) int
minc
Position of uncovered minimum column(package private) int
minr
Position of uncovered minimum row(package private) int[]
rmark
Row marks, used only temporary.(package private) int[]
rsel
Selected ("starred") column per row, -1 if not selected.(package private) int
selected
Number of selected zeros.
-
Constructor Summary
Constructors Constructor Description KuhnMunkres()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected double
costOf(int i, int j)
Get the adjusted cost of a single element, for debug output.protected void
debugLogMatrix(java.util.logging.Level l, long maxit, java.lang.String msg)
Debug logging of the matrix.private double
findUncoveredMinimum()
Find the minimum in the uncovered rows.protected void
initialCover()
Select the last zero in each row to make an initial selection, which may already yield a solution.protected void
initialize(double[][] ocost)
Initialize, and make a deep copy.private boolean
pivot()
Pivot columns mark to row marks.private void
removeCost(double h)
Remove cost h (if > 0) found to be unavoidable.int[]
run(double[][] cost)
Perform the Kuhn-Munkres algorithm.private void
updateStars()
Update the position of stars.
-
-
-
Field Detail
-
LOG
private static final Logging LOG
Class logger
-
cost
double[][] cost
Cost matrix
-
selected
int selected
Number of selected zeros.
-
rsel
int[] rsel
Selected ("starred") column per row, -1 if not selected.
-
csel
int[] csel
Selected ("starred") row per column, -1 if not selected.
-
rmark
int[] rmark
Row marks, used only temporary.
-
cmark
int[] cmark
Column marks.
-
minr
int minr
Position of uncovered minimum row
-
minc
int minc
Position of uncovered minimum column
-
-
Method Detail
-
run
public int[] run(double[][] cost)
Perform the Kuhn-Munkres algorithm.- Parameters:
cost
- Cost matrix- Returns:
- Selected columns, per row
-
initialize
protected void initialize(double[][] ocost)
Initialize, and make a deep copy.- Parameters:
ocost
- Original cost matrix
-
initialCover
protected void initialCover()
Select the last zero in each row to make an initial selection, which may already yield a solution.
-
findUncoveredMinimum
private double findUncoveredMinimum()
Find the minimum in the uncovered rows.- Returns:
- Minimum in uncovered rows
-
removeCost
private void removeCost(double h)
Remove cost h (if > 0) found to be unavoidable.- Parameters:
h
- Cost to remove
-
pivot
private boolean pivot()
Pivot columns mark to row marks.- Returns:
true
if we pivoted.
-
updateStars
private void updateStars()
Update the position of stars.
-
debugLogMatrix
protected void debugLogMatrix(java.util.logging.Level l, long maxit, java.lang.String msg)
Debug logging of the matrix.- Parameters:
l
- Log levelmaxit
- Iteration countdownmsg
- Message prefix
-
costOf
protected double costOf(int i, int j)
Get the adjusted cost of a single element, for debug output.- Parameters:
i
- rowj
- column- Returns:
- cost
-
-