GrammaticalExhaustiveSearch: Exhaustive Search

Description

Exhaustive Search within context-free grammar.

Usage

GrammaticalExhaustiveSearch(grammar, evalFunc,
                max.depth = GrammarGetDepth(grammar),
                startSymb = GrammarStartSymbol(grammar),
                max.len = GrammarMaxSequenceLen(grammar, max.depth, startSymb),
                wrappings = 3,
                terminationCost = NA,
                monitorFunc = NULL)

Arguments

grammar

A grammar object.

evalFunc

The evaluation function, taking an expression as its input and returning the cost (i.e., the score) of the expression.

max.depth

Maximum depth of recursion, in case of a cyclic grammar. By default it is limited to the number of production rules in the grammar.

startSymb

The symbol where the generation of a new expression should start.

max.len

Maximum length of the sequences to search. By default it is determined by max.depth.

wrappings

The number of times the function is allowed to wrap around inputString if non-terminal symbols are still remaining.

terminationCost

Target cost. If an expression with this cost or less is found, the algorithm terminates.

monitorFunc

A function that is called at each iteration. It can be used to monitor the search.

Value

bestExpression

The Best expresssion.

bestSequence

Best expresssion's generating sequence.

bestCost

Best expresssion's cost.

numExpr

Number of evaluated expressions.

In addition, the monitorFunc receives the following additional slots:

currentExpression

The current expresssion.

currentSequence

Current expresssion's generating sequence.

currentCost

Current expresssion's cost.

Details

GrammaticalExhaustiveSearch performs an exhaustive search, iterating through all possible expressions that can be generated by the grammar, to find the expression that minimises evalFunc.

The search terminates when all possible expressions are exhausted, or when an expression with a cost less than terminationCost is discovered.

If a monitorFunc is given, it is called for each expression, and it receives a list similar to the GrammaticalExhaustiveSearch's return value with the information availabe for that expression.

Examples

Run this code

# NOT RUN {
library("gramEvol")

ruleDef <- list(expr = gsrule("<var><op><var>"),
                op   = gsrule("+", "-", "*"),
                var  = gsrule("A", "B"))

# Create a grammar object
grammarDef <- CreateGrammar(ruleDef)         


# use exhaustive search to find the sequence for creating "B - A"
evalFunc <- function(expr) {
  if (as.character(expr) == "B - A") {
    return(0) # Minimum error
  } else {
    return(1) # maximum error
  }
}

res <- GrammaticalExhaustiveSearch(grammarDef, evalFunc, terminationCost = 0)

print(res)

# }