net.sf.cpsolver.ifs.heuristics

## Class BacktrackNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>

- java.lang.Object
- - net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection<V,T>
  - - net.sf.cpsolver.ifs.heuristics.BacktrackNeighbourSelection<V,T>

- All Implemented Interfaces:
    NeighbourSelection<V,T>
  Direct Known Subclasses:
    RandomizedBacktrackNeighbourSelection

      public class BacktrackNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>
      extends StandardNeighbourSelection<V,T>

  Backtracking-based neighbour selection. A best neighbour that is found by a backtracking-based algorithm within a limited depth from a selected variable is returned.
  Parameters:

  Parameter | Type | Comment
  --- | --- | ---
  Neighbour.BackTrackTimeout | `Integer` | Timeout for each neighbour selection (in milliseconds).
  Neighbour.BackTrackDepth | `Integer` | Limit of search depth.

  Version:
    StudentSct 1.2 (Student Sectioning)
    Copyright (C) 2007 - 2010 Tomáš Müller
    muller@unitime.org
    http://muller.unitime.org
    This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
    This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
    You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `class` | `BacktrackNeighbourSelection.BackTrackNeighbour` Backtracking neighbour

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected BacktrackNeighbourSelection.BackTrackNeighbour` | `iBackTrackNeighbour`
    `protected Solution<V,T>` | `iSolution`
    `protected double` | `iValue`

    - ### Fields inherited from class net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection

      `sLogger`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `BacktrackNeighbourSelection(DataProperties properties)` Constructor

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected void` | `backtrack(List<V> variables2resolve, int idx, int depth)` Backtracking
    `protected boolean` | `canContinue(List<V> variables2resolve, int idx, int depth)` Check whether backtrack can continue
    `protected boolean` | `canContinueEvaluation()`
    `protected boolean` | `checkBound(List<V> variables2resolve, int idx, int depth, T value, Set<T> conflicts)` Check bound
    `int` | `getDepth()` Return maximal depth
    `int` | `getMaxIters()` Return maximal number of iterations
    `long` | `getTime()` Time needed to find a neighbour (last call of selectNeighbour method)
    `int` | `getTimeout()` Return time limit
    `void` | `init(Solver<V,T> solver)` Solver initialization
    `boolean` | `isMaxItersReached()` True, if the maximum number of iterations was reached by the last call of selectNeighbour method
    `boolean` | `isTimeoutReached()` True, if timeout was reached during the last call of selectNeighbour method
    `Neighbour<V,T>` | `selectNeighbour(Solution<V,T> solution)` Select neighbour.
    `Neighbour<V,T>` | `selectNeighbour(Solution<V,T> solution, V variable)` Select neighbour -- starts from the provided variable.
    `void` | `setDepth(int depth)` Set maximal depth
    `void` | `setMaxIters(int maxIters)` Set maximal number of iterations
    `void` | `setTimeout(int timeout)` Set time limit
    `protected Iterator<T>` | `values(V variable)` List of values of the given variable that will be considered

    - ### Methods inherited from class net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection

      `getValueSelection, getVariableSelection, selectValue, selectVariable, setValueSelection, setVariableSelection`

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### iSolution

          protected Solution<V extends Variable<V,T>,T extends Value<V,T>> iSolution

    - #### iBackTrackNeighbour

          protected BacktrackNeighbourSelection.BackTrackNeighbour iBackTrackNeighbour

    - #### iValue

          protected double iValue

  - ### Constructor Detail

    - #### BacktrackNeighbourSelection

          public BacktrackNeighbourSelection(DataProperties properties)
                                      throws Exception

      Constructor
      Parameters:
        `properties` - configuration
      Throws:
        `Exception`

  - ### Method Detail

    - #### init

          public void init(Solver<V,T> solver)

      Solver initialization
      Specified by:
        `init` in interface `NeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>`
      Overrides:
        `init` in class `StandardNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>`

    - #### selectNeighbour

          public Neighbour<V,T> selectNeighbour(Solution<V,T> solution)

      Select neighbour. The standard variable selection (see `StandardNeighbourSelection.getVariableSelection()`) is used to select a variable. A backtracking of a limited depth is than employed from this variable. The best assignment found is returned (see `BacktrackNeighbourSelection.BackTrackNeighbour`).
      Specified by:
        `selectNeighbour` in interface `NeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>`
      Overrides:
        `selectNeighbour` in class `StandardNeighbourSelection<V extends Variable<V,T>,T extends Value<V,T>>`
      Parameters:
        `solution` - given solution
      Returns:
        a neighbour assignment

    - #### selectNeighbour

          public Neighbour<V,T> selectNeighbour(Solution<V,T> solution,
                                                V variable)

      Select neighbour -- starts from the provided variable. A backtracking of a limited depth is employed from the given variable. The best assignment found is returned (see `BacktrackNeighbourSelection.BackTrackNeighbour`).

    - #### getTime

          public long getTime()

      Time needed to find a neighbour (last call of selectNeighbour method)

    - #### isTimeoutReached

          public boolean isTimeoutReached()

      True, if timeout was reached during the last call of selectNeighbour method

    - #### isMaxItersReached

          public boolean isMaxItersReached()

      True, if the maximum number of iterations was reached by the last call of selectNeighbour method

    - #### values

          protected Iterator<T> values(V variable)

      List of values of the given variable that will be considered

    - #### checkBound

          protected boolean checkBound(List<V> variables2resolve,
                                       int idx,
                                       int depth,
                                       T value,
                                       Set<T> conflicts)

      Check bound

    - #### canContinue

          protected boolean canContinue(List<V> variables2resolve,
                                        int idx,
                                        int depth)

      Check whether backtrack can continue

    - #### canContinueEvaluation

          protected boolean canContinueEvaluation()

    - #### backtrack

          protected void backtrack(List<V> variables2resolve,
                                   int idx,
                                   int depth)

      Backtracking

    - #### getDepth

          public int getDepth()

      Return maximal depth

    - #### setDepth

          public void setDepth(int depth)

      Set maximal depth

    - #### getTimeout

          public int getTimeout()

      Return time limit

    - #### setTimeout

          public void setTimeout(int timeout)

      Set time limit

    - #### getMaxIters

          public int getMaxIters()

      Return maximal number of iterations

    - #### setMaxIters

          public void setMaxIters(int maxIters)

      Set maximal number of iterations