org.cpsolver.ifs.heuristics

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

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

- Type Parameters:
    `V` - Variable
    `T` - Value
  All Implemented Interfaces:
    NeighbourSelection<V,T>
  Direct Known Subclasses:
    RandomizedBacktrackNeighbourSelection, ShuffleStudentsSelection.ShuffleBacktrackNeighbourSelection

      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:

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

  Version:
    StudentSct 1.3 (Student Sectioning)
    Copyright (C) 2007 - 2014 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/.
  Author:
    Tomáš Müller

- - ### Nested Class Summary

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

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext` | `iContext`

    - ### Fields inherited from class org.cpsolver.ifs.heuristics.StandardNeighbourSelection

      `iSolver, 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(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context, List<V> variables2resolve, int idx, int depth)` Backtracking
    `protected boolean` | `canContinue(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context, List<V> variables2resolve, int idx, int depth)` Check whether backtrack can continue
    `protected boolean` | `canContinueEvaluation(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)`
    `protected boolean` | `checkBound(List<V> variables2resolve, int idx, int depth, T value, Set<T> conflicts)` Check bound
    `BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext` | `getContext()`
    `int` | `getDepth()` Return maximal depth
    `int` | `getMaxIters()` Return maximal number of iterations
    `int` | `getTimeout()` Return time limit
    `void` | `init(Solver<V,T> solver)` Solver initialization
    `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.
    `protected void` | `selectNeighbour(Solution<V,T> solution, V variable, BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)`
    `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(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context, V variable)` List of values of the given variable that will be considered

    - ### Methods inherited from class org.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

    - #### iContext

          protected BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext iContext

  - ### Constructor Detail

    - #### BacktrackNeighbourSelection

          public BacktrackNeighbourSelection(DataProperties properties)
                                      throws Exception

      Constructor
      Parameters:
        `properties` - configuration
      Throws:
        `Exception` - thrown when initialization fails

  - ### 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>>`
      Parameters:
        `solver` - current solver

    - #### 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`).
      Parameters:
        `solution` - current solution
        `variable` - selected variable
      Returns:
        a neighbour, null if not found

    - #### selectNeighbour

          protected void selectNeighbour(Solution<V,T> solution,
                                         V variable,
                                         BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)

    - #### getContext

          public BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext getContext()

    - #### values

          protected Iterator<T> values(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context,
                                       V variable)

      List of values of the given variable that will be considered
      Parameters:
        `context` - assignment context
        `variable` - given variable
      Returns:
        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
      Parameters:
        `variables2resolve` - unassigned variables that are in conflict with the current solution
        `idx` - position in variables2resolve
        `depth` - current depth
        `value` - value to check
        `conflicts` - conflicting values
      Returns:
        bound (best possible improvement)

    - #### canContinue

          protected boolean canContinue(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context,
                                        List<V> variables2resolve,
                                        int idx,
                                        int depth)

      Check whether backtrack can continue
      Parameters:
        `context` - assignment context
        `variables2resolve` - unassigned variables that are in conflict with the current solution
        `idx` - position in variables2resolve
        `depth` - current depth
      Returns:
        true if the search can continue

    - #### canContinueEvaluation

          protected boolean canContinueEvaluation(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context)

    - #### backtrack

          protected void backtrack(BacktrackNeighbourSelection.BacktrackNeighbourSelectionContext context,
                                   List<V> variables2resolve,
                                   int idx,
                                   int depth)

      Backtracking
      Parameters:
        `context` - assignment context
        `variables2resolve` - unassigned variables that are in conflict with the current solution
        `idx` - position in variables2resolve
        `depth` - current depth

    - #### getDepth

          public int getDepth()

      Return maximal depth
      Returns:
        maximal search depth

    - #### setDepth

          public void setDepth(int depth)

      Set maximal depth
      Parameters:
        `depth` - maximal search depth

    - #### getTimeout

          public int getTimeout()

      Return time limit
      Returns:
        time limit

    - #### setTimeout

          public void setTimeout(int timeout)

      Set time limit
      Parameters:
        `timeout` - time limit

    - #### getMaxIters

          public int getMaxIters()

      Return maximal number of iterations
      Returns:
        maximal number of iterations

    - #### setMaxIters

          public void setMaxIters(int maxIters)

      Set maximal number of iterations
      Parameters:
        `maxIters` - maximal number of iterations