Package org.ddolib.examples.lcs

package org.ddolib.examples.lcs
This package implements the acs, astar and ddo models for the Longest Common Subsequence (LCS) Problem. In the Longest Common Subsequence Problem (LCS), we are given a set of 𝑚 input strings 𝑆= {𝑆0,...,𝑆𝑚−1 }composed of characters from a given alpha- bet Σ. The goal is to find the longest subsequence appearing in all strings, that can be obtained by removing some characters from each input string.
  • Classes
    Class
    Description
    LCSAcsMain
    Longest Common Subsequence (LCS) with Acs.
    LCSAstarMain
    Longest Common Subsequence (LCS) with AsTar.
    LCSDdoMain
    Longest Common Subsequence (LCS) with Ddo.
    LCSDp
    Naive DP solver the 2-strings longest common subsequence problem, used to build a heuristic for the m-strings problem.
    LCSFastLowerBound
    Implementation of a fast lower bound heuristic for the Longest Common Subsequence (LCS) problem.
    LCSGenerator
    Contains method to generate instances of the LCS
    LCSLnsMain
    Entry point for solving the Longest Common Subsequence (LCS) problem using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).
    LCSProblem
    Definition of the Longest Common Subsequence (LCS) problem.
    LCSRanking
    Ranking strategy for LCSState in the Longest Common Subsequence (LCS) problem.
    LCSRelax
    Relaxation strategy for LCSState in the Longest Common Subsequence (LCS) problem.
    LCSState
    Represents the state of a node in the Longest Common Subsequence (LCS) problem.