Package org.ddolib.examples.lcs

Class LCSProblem

java.lang.Object
org.ddolib.examples.lcs.LCSProblem
All Implemented Interfaces:
Problem<LCSState>
public class LCSProblem extends Object implements Problem<LCSState>
Definition of the Longest Common Subsequence (LCS) problem.

The LCS problem consists in finding the longest sequence of characters that appears in the same relative order in a set of strings. This class models the problem in a way suitable for state-space search solvers.

The state of the problem is represented by the current position in each string, and the decisions correspond to selecting a character to include in the LCS next. The class precomputes several auxiliary structures to efficiently determine:

  • Next occurrence of each character after a given position in each string.
  • Remaining occurrences of each character after a given position in each string.
  • Dynamic programming tables for optimal LCS of string pairs.

  • Constructor Details

    • LCSProblem

      public LCSProblem(String instance, int stringNb, int diffCharNb, int[][] stringsAsInt, int[] stringsLength, int[][][] nextCharPos, int[][][] remChar, HashMap<Character,Integer> charToId, Character[] idToChar, Optional<Double> optimal)
      Constructs an LCS problem instance with all precomputed structures.
      Parameters:
      instance - The instance name or path.
      stringNb - Number of strings.
      diffCharNb - Number of distinct characters.
      stringsAsInt - Input strings encoded as integer arrays.
      stringsLength - Length of each string.
      nextCharPos - Next occurrence of each character after each position.
      remChar - Remaining occurrences of each character after each position.
      charToId - Mapping from character to ID.
      idToChar - Mapping from ID to character.
      optimal - Optional optimal solution value.

    • LCSProblem

      public LCSProblem(String filename) throws IOException
      Constructs an LCS problem instance from a file.

      The file should contain the number of strings, number of characters, and optionally the optimal solution in the first line, followed by each string in the format: length string_content.

      Parameters:
      filename - Path to the file defining the LCS instance.
      Throws:
      IOException - If reading the file fails.

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nbVars

      public int nbVars()
      Specified by:
      nbVars in interface Problem<LCSState>
      Returns:
      the total number of decision variables in this problem

    • initialState

      public LCSState initialState()
      Description copied from interface: Problem
      Returns the initial state of the problem.
      Specified by:
      initialState in interface Problem<LCSState>
      Returns:
      the state representing the starting point of the optimization

    • initialValue

      public double initialValue()
      Description copied from interface: Problem
      Returns the initial objective value associated with the initial state.
      Specified by:
      initialValue in interface Problem<LCSState>
      Returns:
      the starting value of the objective function

    • domain

      public Iterator<Integer> domain(LCSState state, int var)
      Computes the domain of possible next decisions (characters) for a given state.

      Only characters that exist in all strings from their current positions are included. If no such character exists, a special value GO_TO_END_OF_STRINGS is returned.

      Specified by:
      domain in interface Problem<LCSState>
      Parameters:
      state - The current LCS state.
      var - Index of the variable to decide (unused, all positions considered).
      Returns:
      An iterator over valid next character IDs.

    • transition

      public LCSState transition(LCSState state, Decision decision)
      Computes the next state resulting from applying a decision at the current state.
      Specified by:
      transition in interface Problem<LCSState>
      Parameters:
      state - The current LCS state.
      decision - The decision applied.
      Returns:
      The next LCS state after the decision.

    • transitionCost

      public double transitionCost(LCSState state, Decision decision)
      Computes the transition cost of a decision from the current state.

      The cost is -1 for selecting a character to maximize the LCS length, and 0 if no character is selected (end of strings).

      Specified by:
      transitionCost in interface Problem<LCSState>
      Parameters:
      state - The current LCS state.
      decision - The decision applied.
      Returns:
      The cost associated with the transition.

    • optimalValue

      public Optional<Double> optimalValue()
      Description copied from interface: Problem
      Returns the known optimal value of the problem, if available.

      Note: This value should correspond to the expected output of the solver. For maximization problems, be careful with negative values.

      Specified by:
      optimalValue in interface Problem<LCSState>
      Returns:
      an Optional containing the known optimal value, or empty if unknown

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Description copied from interface: Problem
      Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.

      Note: For maximization problems, the returned value is minus the computed value.

      Specified by:
      evaluate in interface Problem<LCSState>
      Parameters:
      solution - A solution of the problem.
      Returns:
      The value of the input solution
      Throws:
      InvalidSolutionException - If the solution does not respect problem's constraints.