Class AssignmentState

java.lang.Object
topics.branchandbound.utils.Node
topics.branchandbound.agents.AssignmentState
All Implemented Interfaces:
Comparable<Node>
class AssignmentState extends Node

Represents a distinct state within the Branch and Bound execution tree for the Task Assignment problem. Each node tracks partial assignments and calculates a lower-bound heuristic to guide the search process and prune sub-optimal branches.

*

Complexity

  • Time Complexity: O(N!) in the theoretical worst-case, mapping to every permutation. The heuristic bounding radically flattens this curve in practice.
  • Space Complexity: O(N) per node. Overall heap consumption depends on the underlying priority queue dimension during traversal.

  • Constructor Details

    • AssignmentState

      public AssignmentState(int problemSize, int[][] costMatrix)
      Constructs the Root Node of the state space tree, representing the initial unassigned state of the system.
      Parameters:
      problemSize - The total number of agents and tasks.
      costMatrix - The matrix mapping cost values for all agent-task pairs.

    • AssignmentState

      public AssignmentState(AssignmentState parent, int taskToAssign)
      Constructs a child state derived from a parent node by assigning a specific task to the next available agent.
      Parameters:
      parent - The origin state node.
      taskToAssign - The target task index to assign to the current agent.

  • Method Details

    • initialValuePruneLimit

      public int initialValuePruneLimit()
      Establishes a preliminary upper bound to initiate the pruning phase. It uses the minimum cost between the primary and secondary diagonals of the matrix.
      Overrides:
      initialValuePruneLimit in class Node
      Returns:
      The initial upper bound estimate.

    • calculateHeuristicValue

      public void calculateHeuristicValue()
      Calculates the lower bound heuristic estimate for this partial assignment. The logic relies on accumulating the fixed costs of agents already assigned, plus the absolute minimum available costs for the remaining unassigned tasks.
      Specified by:
      calculateHeuristicValue in class Node

    • expand

      public ArrayList<Node> expand()
      Generates all mathematically valid mathematical combinations extending from the current state.
      Specified by:
      expand in class Node
      Returns:
      A list containing the resulting child nodes.

    • isSolution

      public boolean isSolution()
      Determines whether the current node represents a fully resolved combination.
      Specified by:
      isSolution in class Node
      Returns:
      true if all agents have been assigned a task; false otherwise.

    • toString

      public String toString()
      Overrides:
      toString in class Object