Package org.ddolib.examples.knapsack

Class KSDistance

java.lang.Object
org.ddolib.examples.knapsack.KSDistance
All Implemented Interfaces:
StateDistance<Integer>
public class KSDistance extends Object implements StateDistance<Integer>
Distance measure for states in a Knapsack (KS) problem.

This class implements StateDistance for states represented as integers (typically the current total weight of the knapsack). It provides methods to compute distances between states and between a state and the root.

Distances are normalized by the knapsack capacity to produce values in [0,1].

  • Constructor Details

    • KSDistance

      public KSDistance(KSProblem problem)
      Constructs a distance measure for a given Knapsack problem instance.
      Parameters:
      problem - the Knapsack problem

  • Method Details

    • distance

      public double distance(Integer a, Integer b)
      Computes the normalized distance between two states.

      The distance is the absolute difference of their integer values divided by the knapsack capacity.

      Specified by:
      distance in interface StateDistance<Integer>
      Parameters:
      a - the first state
      b - the second state
      Returns:
      the normalized distance between a and b

    • distanceWithRoot

      public double distanceWithRoot(Integer state)
      Computes the normalized distance between a state and the root (empty knapsack).
      Specified by:
      distanceWithRoot in interface StateDistance<Integer>
      Parameters:
      state - the state to measure
      Returns:
      the normalized distance from the root