backtracker {editrules}

Backtracker: a flexible and generic binary search program

Description

backtracker creates a binary search program that can be started by calling the $searchNext function It walks a binary tree depth first. For all left nodes choiceLeft is evaluated, for all right nodes choiceRight is evaluated. A solution is found if isSolution evaluates to TRUE. In that case $searchNext will return all variables in the search environment in a list If isSolution evaluates to NULL it will continue to search deaper. If isSolution evaluates to FALSE it stops at the current node and goes up the next search node

Usage

backtracker(
  isSolution,
  choiceLeft,
  choiceRight,
  list = NULL,
  maxdepth = Inf,
  maxduration = Inf,
  ...
)

Arguments

isSolution

expression that should evaluate to TRUE when a solution is found.

choiceLeft

expression that will be evaluated for a left node

choiceRight

expression that will be evaluated for a right node

list

list with variables that will be added to the search environment

maxdepth

integer maximum depth of the search tree

maxduration

integer Default maximum search time for $searchNext() and $searchAll()

...

named variables that will be added to the search environment

Details

Methods

$searchNext(..., VERBOSE=FALSE)

Search next solution, can be called repeatedly until there is no solution left. Named variables will be added to the search environment, this feature can be used to direct the search in subsequent calls to searchNext. VERBOSE=TRUE will print all intermediate search steps and results. It can be used to debug the expressions in the backtracker

$searchAll(..., VERBOSE=FALSE)

Return all solutions as a list

$reset()

Resets the backtracker to its initial state.

Value

backtracker object, see Methods for a description of the methods

Examples

bt <- backtracker( isSolution= { 
                                 if (y == 0) return(TRUE)
                                 if (x == 0) return(FALSE)
                               }
                 , choiceLeft = { x <- x - 1; y <- y}
                 , choiceRight = { y <- y - 1; x <- x}
                 # starting values for x and y
                 , x=2
                 , y=1
                 )

bt$searchNext(VERBOSE=TRUE)
bt$searchNext(VERBOSE=TRUE)

# next search will return NULL because there is no more solution
bt$searchNext()

bt$reset()