backtracker: Backtracker: a flexible and generic binary search program

In editrules: Parsing, Applying, and Manipulating Data Cleaning Rules

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()

editrules documentation built on June 22, 2024, 12:21 p.m.