Package org.ddolib.examples.lcs

Class LCSRelax

java.lang.Object

org.ddolib.examples.lcs.LCSRelax

All Implemented Interfaces:

Relaxation<LCSState>

public class LCSRelax
extends Object
implements Relaxation<LCSState>

Relaxation strategy for LCSState in the Longest Common Subsequence (LCS) problem.

This class implements Relaxation and is used to merge multiple LCS states into a single relaxed state, which is useful for search algorithms such as DDO (Decision Diagram Optimization).

The merged state preserves, for each string, the earliest position among all merged states. This allows the algorithm to over-approximate the search space while maintaining feasibility.

Constructor Summary

Constructors

Constructor	Description
LCSRelax(LCSProblem problem)	Constructs a relaxation object for a given LCS problem.

Method Summary

Modifier and Type	Method	Description
LCSState	mergeStates(Iterator<LCSState> states)	Merges multiple LCS states into a single relaxed state.
double	relaxEdge(LCSState from, LCSState to, LCSState merged, Decision d, double cost)	Relaxes the cost of a transition between two LCS states.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

LCSRelax

public LCSRelax(LCSProblem problem)

Constructs a relaxation object for a given LCS problem.

Parameters:

problem - The LCS problem instance.

Method Details

mergeStates

public LCSState mergeStates(Iterator<LCSState> states)

Merges multiple LCS states into a single relaxed state.

For each string, the merged state takes the minimum position among all states, effectively keeping the "earliest progress" along each string.

Specified by:

mergeStates in interface Relaxation<LCSState>

Parameters:

states - Iterator over the states to be merged.

Returns:

A new LCSState representing the merged state.

relaxEdge

public double relaxEdge(LCSState from,
 LCSState to,
 LCSState merged,
 Decision d,
 double cost)

Relaxes the cost of a transition between two LCS states.

This implementation returns the original cost unchanged.

Specified by:

relaxEdge in interface Relaxation<LCSState>

Parameters:

from - The state from which the transition originates.

to - The state to which the transition goes.

merged - The merged state that includes both 'from' and 'to'.

d - The decision taken.

cost - The original cost of the transition.

Returns:

The relaxed cost, which in this case is the same as cost.