Package org.ddolib.examples.gruler

package org.ddolib.examples.gruler
This package implements the acs, astar and ddo models for the Golomb Rule Problem (GRP). In a Golomb rule problem, a set of marks at integer positions along a ruler are posted such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. By default, the first mark is posted at 0. This class demonstrates how to implement a solver for the Golomb ruler problem. For more information on this problem, see Golomb Ruler - Wikipedia.

This model was introduced by Willem-Jan van Hoeve. In this model: - Each variable/layer represents the position of the next mark to be placed. - The domain of each variable is the set of all possible positions for the next mark. - A mark can only be added if the distance between the new mark and all previous marks is not already present in the set of distances between marks.

The cost of a transition is defined as the distance between the new mark and the previous last mark. Consequently, the cost of a solution is the position of the last mark.

  • Classes
    Class
    Description
    GRAcsMain
    Golomb Rule Problem (GRP) with Acs.
    GRAstarMain
    Golomb Rule Problem (GRP) with AsTar.
    GRDdoMain
    Golomb Rule Problem (GRP) with Ddo.
    GRFastLowerBound
    Lower bound for the Golomb Ruler.
    GRProblem
    Represents an instance of the Golomb Ruler (GR) problem.
    GRRanking
    Defines a ranking strategy for states in the Golomb Ruler (GR) problem.
    GRRelax
    Relaxation operator for the Golomb Ruler (GR) problem.
    GRState
    Represents a state in the Golomb Ruler (GR) problem.