程序包 edu.princeton.cs.algs4

类 AssignmentProblem

  • public class AssignmentProblem
extends java.lang.Object
    The 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.

    For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • 构造器概要

      构造器 
      构造器 说明
      AssignmentProblem​(double[][] weight)
      Determines an optimal solution to the assignment problem.

    • 方法概要

      修饰符和类型 方法 说明
      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​(java.lang.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

      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 构造器详细资料

      • AssignmentProblem

        public AssignmentProblem​(double[][] weight)
        Determines an optimal solution to the assignment problem.
        参数:
        weight - the n-by-n matrix of weights
        抛出:
        java.lang.IllegalArgumentException - unless all weights are nonnegative
        java.lang.IllegalArgumentException - if weight is null

    • 方法详细资料

      • dualRow

        public double dualRow​(int i)
        Returns the dual optimal value for the specified row.
        参数:
        i - the row index
        返回:
        the dual optimal value for row i
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < n

      • dualCol

        public double dualCol​(int j)
        Returns the dual optimal value for the specified column.
        参数:
        j - the column index
        返回:
        the dual optimal value for column j
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= j < n

      • sol

        public int sol​(int i)
        Returns the column associated with the specified row in the optimal solution.
        参数:
        i - the row index
        返回:
        the column matched to row i in the optimal solution
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < n

      • weight

        public double weight()
        Returns the total weight of the optimal solution
        返回:
        the total weight of the optimal solution

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the 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