Package org.ddolib.examples.mks

Class MKSDistance

java.lang.Object
org.ddolib.examples.mks.MKSDistance
All Implemented Interfaces:
StateDistance<MKSState>
public class MKSDistance extends Object implements StateDistance<MKSState>
Computes a normalized distance between Multi-dimensional Knapsack (MKS) states.

This class implements StateDistance for MKSState objects. The distance is based on the Euclidean distance between the remaining capacities of two states, normalized by the maximal distance of the knapsack capacities.

This distance can be used in clustering or merging strategies in decision diagram optimization algorithms to guide state aggregation.

  • Constructor Details

    • MKSDistance

      public MKSDistance(MKSProblem instance)
      Constructs a distance evaluator for the given MKS problem.
      Parameters:
      instance - the multi-dimensional knapsack problem instance

  • Method Details

    • distance

      public double distance(MKSState a, MKSState b)
      Computes the normalized Euclidean distance between two MKS states.
      Specified by:
      distance in interface StateDistance<MKSState>
      Parameters:
      a - the first state
      b - the second state
      Returns:
      the normalized distance between a and b

    • distanceWithRoot

      public double distanceWithRoot(MKSState a)
      Computes the normalized Euclidean distance from the given state to the initial state.
      Specified by:
      distanceWithRoot in interface StateDistance<MKSState>
      Parameters:
      a - the state
      Returns:
      the normalized distance from a to the initial state