Package org.ddolib.examples.maximumcoverage

Class MaxCoverDistance

java.lang.Object
org.ddolib.examples.maximumcoverage.MaxCoverDistance
All Implemented Interfaces:
StateDistance<MaxCoverState>
public class MaxCoverDistance extends Object implements StateDistance<MaxCoverState>
Distance function for MaxCoverState used to measure similarity between states in the context of the Maximum Coverage problem.

This class implements StateDistance and provides several distance computations:

  • a distance between two states based on the covered item sets
  • a distance between two search nodes combining state similarity and cost difference
  • a distance between a state and the root, used for diversification purposes

Distances are normalized with respect to the number of items in the problem instance and may rely on weighted or unweighted set-based metrics.

  • Constructor Details

    • MaxCoverDistance

      public MaxCoverDistance(MaxCoverProblem instance)
      Constructs a distance measure associated with a given MaxCover problem instance.
      Parameters:
      instance - the MaxCover problem instance providing problem-specific parameters

  • Method Details

    • distanceWithRoot

      public double distanceWithRoot(MaxCoverState state)
      Computes the distance between a state and the root of the search tree.

      This distance is proportional to the fraction of items covered by the state.

      Specified by:
      distanceWithRoot in interface StateDistance<MaxCoverState>
      Parameters:
      state - the state for which the distance to the root is computed
      Returns:
      a normalized distance to the root

    • distance

      public double distance(NodeSubProblem<MaxCoverState> a, NodeSubProblem<MaxCoverState> b)
      Computes the distance between two search nodes.

      The distance is a convex combination of:

      • a weighted Jaccard distance between the covered item sets
      • a normalized difference between the node objective values
      Specified by:
      distance in interface StateDistance<MaxCoverState>
      Parameters:
      a - first node
      b - second node
      Returns:
      the combined distance between the two nodes

    • distance

      public double distance(MaxCoverState a, MaxCoverState b)
      Computes the distance between two MaxCover states.

      The distance is based on the size of the symmetric difference between the sets of covered items, normalized by the total number of items.

      Specified by:
      distance in interface StateDistance<MaxCoverState>
      Parameters:
      a - first state
      b - second state
      Returns:
      a normalized symmetric difference distance