public class AssignmentProblem extends Object
AssignmentProblem
class represents a data type for computing
an optimal solution to an n-by-n assignment problem.
The assignment problem is to find a minimum weight matching in an
edge-weighted complete bipartite graph.
The data type supplies methods for determining the optimal solution and the corresponding dual solution.
This implementation uses the successive shortest paths algorithm. The order of growth of the running time in the worst case is O(n^3 log n) to solve an n-by-n instance.
This computes correct results if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 252.
For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
AssignmentProblem(double[][] weight)
Determines an optimal solution to the assignment problem.
|
Modifier and Type | Method and Description |
---|---|
double |
dualCol(int j)
Returns the dual optimal value for the specified column.
|
double |
dualRow(int i)
Returns the dual optimal value for the specified row.
|
static void |
main(String[] args)
Unit tests the
AssignmentProblem data type. |
int |
sol(int i)
Returns the column associated with the specified row in the optimal solution.
|
double |
weight()
Returns the total weight of the optimal solution
|
public AssignmentProblem(double[][] weight)
weight
- the n-by-n matrix of weightsIllegalArgumentException
- unless all weights are nonnegativeIllegalArgumentException
- if weight
is null
public double dualRow(int i)
i
- the row indexi
IllegalArgumentException
- unless 0 <= i < n
public double dualCol(int j)
j
- the column indexj
IllegalArgumentException
- unless 0 <= j < n
public int sol(int i)
i
- the row indexi
in the optimal solutionIllegalArgumentException
- unless 0 <= i < n
public double weight()
public static void main(String[] args)
AssignmentProblem
data type.
Takes a command-line argument n; creates a random n-by-n matrix;
solves the n-by-n assignment problem; and prints the optimal
solution.args
- the command-line arguments