Package org.ddolib.examples.gruler

Class GRProblem

java.lang.Object
org.ddolib.examples.gruler.GRProblem
All Implemented Interfaces:
Problem<GRState>
public class GRProblem extends Object implements Problem<GRState>
Represents an instance of the Golomb Ruler (GR) problem.

The Golomb Ruler problem consists in placing n marks on a ruler such that all pairwise distances between marks are distinct, and the length of the ruler (i.e., the position of the last mark) is minimized.

This class defines the problem structure and state transitions to be used in optimization or search algorithms (e.g., A*, DDO, or constraint programming). Each state represents a partially constructed ruler with a set of marks and the distances between them.

Example:


 GRProblem problem = new GRProblem(4);
 GRState initial = problem.initialState();
 Iterator<Integer> domain = problem.domain(initial, 0);
See Also:

  • Constructor Summary

    Constructors
    Constructor
    Description
    GRProblem(int n)
    Constructs a Golomb Ruler problem with n marks and no known optimal value.
    GRProblem(int n, double optimal)
    Constructs a Golomb Ruler problem with n marks and a known optimal length.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(GRState state, int var)
    Returns the possible domain values for the next decision (i.e., possible positions for the next mark).
    double
    evaluate(int[] solution)
    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.
    GRState
    initialState()
    Returns the initial state of the problem, containing only the first mark at position 0.
    double
    initialValue()
    Returns the initial cost (always 0).
    int
    nbVars()
    Returns the number of variables in the problem.
    Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    String
    toString()
    Returns a human-readable representation of the problem instance.
    GRState
    transition(GRState state, Decision decision)
    Computes the next state resulting from applying a decision (adding a new mark).
    double
    transitionCost(GRState state, Decision decision)
    Computes the cost associated with a transition between states.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • GRProblem

      public GRProblem(int n)
      Constructs a Golomb Ruler problem with n marks and no known optimal value.
      Parameters:
      n - the number of marks to place on the ruler.

    • GRProblem

      public GRProblem(int n, double optimal)
      Constructs a Golomb Ruler problem with n marks and a known optimal length.
      Parameters:
      n - the number of marks to place on the ruler.
      optimal - the known optimal length of the ruler.

  • Method Details

    • toString

      public String toString()
      Returns a human-readable representation of the problem instance.
      Overrides:
      toString in class Object
      Returns:
      a string describing the Golomb Ruler instance.

    • nbVars

      public int nbVars()
      Returns the number of variables in the problem. For a ruler with n marks, there are n - 1 decision variables.
      Specified by:
      nbVars in interface Problem<GRState>
      Returns:
      the number of decision variables.

    • initialState

      public GRState initialState()
      Returns the initial state of the problem, containing only the first mark at position 0.
      Specified by:
      initialState in interface Problem<GRState>
      Returns:
      the initial GRState.

    • initialValue

      public double initialValue()
      Returns the initial cost (always 0).
      Specified by:
      initialValue in interface Problem<GRState>
      Returns:
      the initial cost value.

    • domain

      public Iterator<Integer> domain(GRState state, int var)
      Returns the possible domain values for the next decision (i.e., possible positions for the next mark).

      The method ensures that no pairwise distance between existing marks and the new mark duplicates an already existing distance.

      Specified by:
      domain in interface Problem<GRState>
      Parameters:
      state - the current state of the ruler.
      var - the index of the variable being expanded.
      Returns:
      an iterator over the feasible next mark positions.

    • transition

      public GRState transition(GRState state, Decision decision)
      Computes the next state resulting from applying a decision (adding a new mark).

      The new state updates the set of marks and the set of pairwise distances.

      Specified by:
      transition in interface Problem<GRState>
      Parameters:
      state - the current state.
      decision - the decision representing the position of the new mark.
      Returns:
      a new GRState representing the updated configuration.

    • transitionCost

      public double transitionCost(GRState state, Decision decision)
      Computes the cost associated with a transition between states.

      The cost corresponds to the distance between the newly placed mark and the previous one.

      Specified by:
      transitionCost in interface Problem<GRState>
      Parameters:
      state - the current state.
      decision - the decision leading to the next mark placement.
      Returns:
      the incremental cost, equal to decision.val() - state.getLastMark().

    • optimalValue

      public Optional<Double> optimalValue()
      Returns the known optimal value of the problem, if available.
      Specified by:
      optimalValue in interface Problem<GRState>
      Returns:
      an Optional containing the optimal value (negated), or empty if the optimal value is 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<GRState>
      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.