How to implement Kuhn-Munkres Algorithm ( Hungarian Method ) ?
publicclass Hungarian{
Hungarian (int[][] matrix ){
//input a n by n matrix
}
privatevoid initial(){
//some initial process
}
publicint getMin(){
//main idea
initial();
rowSubtract();
columnSubtract();
while( minCover() < this.size ){
modify();
}
return findSolution();
}
publicint getMax(){
//main idea
initial();
for (int i = 0; i < line; i++ )
for (int j = 0; j < line; j++ )
this.c[i][j] *= -1;
rowSubtract();
columnSubtract();
while( minCover() < this.size )
modify();
return findSolution()();
}
privatevoid rowSubtract(){
int[] minRow =newint[line];
for (int i = 0; i < line; i++ )
minRow[i] = Integer.MAX_VALUE;
for (int i = 0; i < line; i++ )
for (int j = 0; j < line; j++ )
if ( minRow[i] > c[i][j] )
minRow[i] = c[i][j];
for (int i = 0; i < line; i++ )
for (int j = 0; j < line; j++ )
c[i][j] -= minRow[i];
}
privatevoid columnSubtract(){
int[] minColumn =newint[line];
for (int i = 0; i < line; i++ )
minColumn[i] = Integer.MAX_VALUE;
for (int i = 0; i < line; i++ )
for (int j = 0; j < line; j++ )
if ( minColumn[i] > c[j][i] )
minColumn[i] = c[j][i];
for (int i = 0; i < line; i++ )
for (int j = 0; j < line; j++ )
c[j][i] -= minColumn[i];
}
privateint minCover(){
//return the number of minimum cover lines
}
privatevoid modify(){
//some modify process
}
privateint findSolution(){
//according the c[][] matrix find a complete bipartite matching
}
}
I don't know how to find a minimum cover lines and a solution!
Could some nice guy give me a hint?
*^^*
