Package org.ddolib.ddo.core.heuristics.cluster

Interface StateDistance<T>

Type Parameters:
T - the type of states
All Known Implementing Classes:
KSDistance, MaxCoverDistance, MKSDistance, TSDistance
public interface StateDistance<T>
Interface defining a distance function between states, used to form clusters when deciding which nodes on a layer of a decision diagram should be merged.

The distance function must satisfy the following properties:

  • Non-negative: distance(a, b) ≥ 0
  • Symmetric: distance(a, b) = distance(b, a)
  • Triangle inequality: distance(a, c) ≤ distance(a, b) + distance(b, c)

Type parameter T denotes the type of the states being compared.

  • Method Summary

    Modifier and Type
    Method
    Description
    default double
    distance(NodeSubProblem<T> a, NodeSubProblem<T> b)
    Computes the distance between two nodes of a subproblem.
    double
    distance(T a, T b)
    Computes the discrete distance between two states.
    default double
    distanceWithRoot(T state)
    Computes the distance between a state and the root of the search/tree.

  • Method Details

    • distance

      double distance(T a, T b)
      Computes the discrete distance between two states.
      Parameters:
      a - the first state
      b - the second state
      Returns:
      the distance between a and b

    • distance

      default double distance(NodeSubProblem<T> a, NodeSubProblem<T> b)
      Computes the distance between two nodes of a subproblem.

      By default, returns 0. Can be overridden for more precise node-level distances.

      Parameters:
      a - the first node
      b - the second node
      Returns:
      the distance between the nodes

    • distanceWithRoot

      default double distanceWithRoot(T state)
      Computes the distance between a state and the root of the search/tree.

      By default, returns 0. Can be overridden for root-distance computations.

      Parameters:
      state - the state to measure
      Returns:
      the distance to the root