Package org.ddolib.examples.lcs

Class LCSRanking

java.lang.Object
org.ddolib.examples.lcs.LCSRanking
All Implemented Interfaces:
Comparator<LCSState>, StateRanking<LCSState>
public class LCSRanking extends Object implements StateRanking<LCSState>
Ranking strategy for LCSState in the Longest Common Subsequence (LCS) problem.

This class implements StateRanking to compare two LCS states. The comparison is based on the sum of the positions in each string: states with smaller total positions are considered "better" because they represent progress earlier in the strings.

It is typically used in search algorithms (ACS, A*, DDO) to prioritize states that are closer to the beginning of the strings, which may lead to faster exploration of potential optimal LCS solutions.

  • Constructor Details

    • LCSRanking

      public LCSRanking()

  • Method Details

    • compare

      public int compare(LCSState state1, LCSState state2)
      Compares two LCS states.

      The state with the smaller sum of positions across all strings is considered better and will be ranked higher.

      Specified by:
      compare in interface Comparator<LCSState>
      Parameters:
      state1 - The first LCS state to compare.
      state2 - The second LCS state to compare.
      Returns:
      A negative integer if state1 is better, zero if equal, positive if state2 is better.

    • equals

      public boolean equals(Object obj)
      Indicates whether this ranking object is equal to another.

      Currently always returns false since ranking objects do not maintain state.

      Specified by:
      equals in interface Comparator<LCSState>
      Overrides:
      equals in class Object
      Parameters:
      obj - The other object to compare to.
      Returns:
      false