Package edu.princeton.cs.algs4
Class AssignmentProblem
- Object
-
- edu.princeton.cs.algs4.AssignmentProblem
-
public class AssignmentProblem extends Object
TheAssignmentProblem
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.
- Author:
- Robert Sedgewick, Kevin Wayne
-
-
Constructor Summary
Constructors Constructor Description AssignmentProblem(double[][] weight)
Determines an optimal solution to the assignment problem.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 theAssignmentProblem
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
-
-
-
Constructor Detail
-
AssignmentProblem
public AssignmentProblem(double[][] weight)
Determines an optimal solution to the assignment problem.- Parameters:
weight
- the n-by-n matrix of weights- Throws:
IllegalArgumentException
- unless all weights are nonnegativeIllegalArgumentException
- ifweight
isnull
-
-
Method Detail
-
dualRow
public double dualRow(int i)
Returns the dual optimal value for the specified row.- Parameters:
i
- the row index- Returns:
- the dual optimal value for row
i
- Throws:
IllegalArgumentException
- unless0 <= i < n
-
dualCol
public double dualCol(int j)
Returns the dual optimal value for the specified column.- Parameters:
j
- the column index- Returns:
- the dual optimal value for column
j
- Throws:
IllegalArgumentException
- unless0 <= j < n
-
sol
public int sol(int i)
Returns the column associated with the specified row in the optimal solution.- Parameters:
i
- the row index- Returns:
- the column matched to row
i
in the optimal solution - Throws:
IllegalArgumentException
- unless0 <= i < n
-
weight
public double weight()
Returns the total weight of the optimal solution- Returns:
- the total weight of the optimal solution
-
main
public static void main(String[] args)
Unit tests theAssignmentProblem
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.- Parameters:
args
- the command-line arguments
-
-