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

Class Hybrid<T>

java.lang.Object
org.ddolib.ddo.core.heuristics.cluster.Hybrid<T>
Type Parameters:
T - the type of states in the decision diagram
All Implemented Interfaces:
ReductionStrategy<T>
public class Hybrid<T> extends Object implements ReductionStrategy<T>
Hybrid reduction strategy that combines cost-based and distance-based clustering for decision diagram layers. This strategy is a hybridation between cost based selection and GHP. It preserves the w * alpha best nodes (alpha between 0 and 1) and merge the other nodes using clustering. It requires a problem-specific StateRanking comparator to break the ties between nodes of same cost, and a problem-specif StateDistance to quantify the dissimilarity between states.

This class implements ReductionStrategy and merges two strategies:

  • CostBased: preserves a fraction of nodes based on their ranking
  • GHP: clusters the remaining nodes based on a distance metric

The combination is controlled by a weighting parameter alpha:

  • alpha fraction of the clusters are preserved using cost-based ranking
  • 1-alpha fraction of the clusters are formed using the GHP distance-based method

  • Constructor Details

    • Hybrid

      public Hybrid(StateRanking<T> ranking, StateDistance<T> distance, double alpha, long seed)
      Constructs a Hybrid reduction strategy with specified ranking, distance, alpha, and seed.
      Parameters:
      ranking - state ranking used for cost-based preservation
      distance - state distance used for GHP clustering
      alpha - fraction of clusters preserved using cost-based strategy
      seed - random seed for distance-based clustering

    • Hybrid

      public Hybrid(StateRanking<T> ranking, StateDistance<T> distance)
      Constructs a Hybrid reduction strategy with default alpha (0.5) and seed.
      Parameters:
      ranking - state ranking used for cost-based preservation
      distance - state distance used for GHP clustering

  • Method Details

    • setSeed

      public void setSeed(long seed)
      Sets the random seed used for the distance-based GHP clustering.
      Parameters:
      seed - the new random seed

    • defineClusters

      public List<NodeSubProblem<T>>[] defineClusters(List<NodeSubProblem<T>> layer, int maxWidth)
      Defines clusters from a layer of nodes using a hybrid strategy.

      A fraction alpha of nodes are clustered using cost-based ranking, while the remaining nodes are clustered using the GHP distance-based method.

      Specified by:
      defineClusters in interface ReductionStrategy<T>
      Parameters:
      layer - the list of nodes at the current layer
      maxWidth - the desired maximum width after clustering
      Returns:
      an array of clusters, each cluster being a list of nodes