org.ddolibscala.tools.ddo.heuristics.cluster
This package contains heuristics used to define a strategy to reduce the number of nodes in a layer of a decision diagram by clustering nodes for restriction and relaxation.
Attributes
Members list
Type members
Classlikes
This strategy select the nodes based on the objective value of the best path leading to them. It requires a problem-specific StateRanking comparator to break the ties between nodes of same cost.
This strategy select the nodes based on the objective value of the best path leading to them. It requires a problem-specific StateRanking comparator to break the ties between nodes of same cost.
Attributes
- See also
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
CostBased.type
Generalized Hyperplane Partitioning (GHP) reduction strategy for decision diagram layers.
Generalized Hyperplane Partitioning (GHP) reduction strategy for decision diagram layers.
This class implements ReductionStrategy and clusters nodes in a layer using a distance-based partitioning method inspired by hyperplane separation. It requires a problem-specific StateDistance function to compute distances between states.
The GHP strategy works by:
- Selecting two distant pivot nodes from the layer ;
- Assigning each remaining node to the cluster of the closer pivot ;
- Recursively splitting clusters until the desired number of clusters (
maxWidth) is reached
A random number generator is used for tie-breaking and initial shuffling of the layer.
Attributes
- See also
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
GHP.type
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.
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:
alphafraction of the clusters are preserved using cost-based ranking ;1 - alphafraction of the clusters are formed using the GHP distance-based method.
Attributes
- See also
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
Hybrid.type
A simple random-based reduction strategy for decision diagram layers.
A simple random-based reduction strategy for decision diagram layers.
This class implements ReductionStrategyand generates clusters by randomly selecting nodes from a layer. Each selected node forms its own cluster.
The strategy is controlled by a Random object, which can be seeded to ensure reproducible behavior.
Attributes
- See also
- Supertypes
-
class Objecttrait Matchableclass Any
- Self type
-
RandomBased.type
Interface defining a strategy to reduce the number of nodes in a layer of a decision diagram by clustering nodes for restriction and relaxation.
Interface defining a strategy to reduce the number of nodes in a layer of a decision diagram by clustering nodes for restriction and relaxation.
Implementations of this interface determine how to group nodes into clusters when the layer exceeds a desired maximum width. All nodes assigned to clusters are removed from the original layer.
Type parameters
- T
-
the type of states in the decision diagram
Attributes
- Supertypes
-
trait ReductionStrategy[T]class Objecttrait Matchableclass Any
Trait defining a distance function between states, used to form clusters when deciding which nodes on a layer of a decision diagram should be merged.
Trait 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 parameters
- T
-
the type of states
Attributes
- Supertypes
-
trait StateDistance[T]class Objecttrait Matchableclass Any