Package org.ddolib.examples.lcs

Class LCSFastLowerBound

java.lang.Object
org.ddolib.examples.lcs.LCSFastLowerBound
All Implemented Interfaces:
FastLowerBound<LCSState>
public class LCSFastLowerBound extends Object implements FastLowerBound<LCSState>
Implementation of a fast lower bound heuristic for the Longest Common Subsequence (LCS) problem.

This class provides a quick estimation of the best achievable LCS length from a given LCSState. It is designed to be used within search algorithms to prune the search space efficiently.

The heuristic works by:

  • For each character, computing the minimum number of occurrences remaining in all strings from their current positions, contributing to a lower bound on the LCS length.
  • For each string pair, using precomputed pairwise LCS tables to find the minimum LCS length achievable based on the current positions.
  • Returning the negative of the smaller value between the total character-based bound and the minimum pairwise LCS bound. This aligns with the solver's convention of minimizing costs.

  • Constructor Details

    • LCSFastLowerBound

      public LCSFastLowerBound(LCSProblem problem)
      Constructs a fast lower bound heuristic for a given LCS problem.
      Parameters:
      problem - The LCS problem instance.

  • Method Details

    • fastLowerBound

      public double fastLowerBound(LCSState state, Set<Integer> variables)
      Computes a fast lower bound on the objective function for the given state.
      Specified by:
      fastLowerBound in interface FastLowerBound<LCSState>
      Parameters:
      state - The current LCS state representing positions in each string.
      variables - The set of variables (unused in this heuristic but required by interface).
      Returns:
      The negative of the estimated maximum LCS length achievable from this state.