aima.core.search.informed

Class RecursiveBestFirstSearch

java.lang.Object

aima.core.search.informed.RecursiveBestFirstSearch

All Implemented Interfaces:

SearchForActions

public class RecursiveBestFirstSearch
extends java.lang.Object
implements SearchForActions

Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.26, page 99.

 function RECURSIVE-BEST-FIRST-SEARCH(problem) returns a solution, or failure
   return RBFS(problem, MAKE-NODE(problem.INITIAL-STATE), infinity)
   
 function RBFS(problem, node, f_limit) returns a solution, or failure and a new f-cost limit
   if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
   successors <- []
   for each action in problem.ACTION(node.STATE) do
       add CHILD-NODE(problem, node, action) into successors
   if successors is empty then return failure, infinity
   for each s in successors do // update f with value from previous search, if any
     s.f <- max(s.g + s.h, node.f)
   repeat
     best <- the lowest f-value node in successors
     if best.f > f_limit then return failure, best.f
     alternative <- the second-lowest f-value among successors
     result, best.f <- RBFS(problem, best, min(f_limit, alternative))
     if result != failure then return result
 

Figure 3.26 The algorithm for recursive best-first search.
This version additionally provides an option to avoid loops. States on the current path are stored in a hash set if the loop avoidance option is enabled.

Author:

Ciaran O'Reilly, Mike Stampone, Ruediger Lunde

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	METRIC_MAX_RECURSIVE_DEPTH
static java.lang.String	METRIC_NODES_EXPANDED
static java.lang.String	METRIC_PATH_COST

Constructor Summary

Constructors

Constructor and Description
RecursiveBestFirstSearch(EvaluationFunction ef)
RecursiveBestFirstSearch(EvaluationFunction ef, boolean avoidLoops) Constructor which allows to enable the loop avoidance strategy.
RecursiveBestFirstSearch(EvaluationFunction ef, boolean avoidLoops, NodeExpander nodeExpander)

Method Summary

Modifier and Type	Method and Description
java.util.List<Action>	findActions(Problem p) Returns a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.
EvaluationFunction	getEvaluationFunction()
Metrics	getMetrics() Returns all the search metrics.
NodeExpander	getNodeExpander() Returns the node expander used by the search.

Methods inherited from class java.lang.Object

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

Field Detail

METRIC_NODES_EXPANDED

public static final java.lang.String METRIC_NODES_EXPANDED

See Also:

Constant Field Values

METRIC_MAX_RECURSIVE_DEPTH

public static final java.lang.String METRIC_MAX_RECURSIVE_DEPTH

See Also:

Constant Field Values

METRIC_PATH_COST

public static final java.lang.String METRIC_PATH_COST

See Also:

Constant Field Values

Constructor Detail

RecursiveBestFirstSearch

public RecursiveBestFirstSearch(EvaluationFunction ef)

RecursiveBestFirstSearch

public RecursiveBestFirstSearch(EvaluationFunction ef,
                                boolean avoidLoops)

Constructor which allows to enable the loop avoidance strategy.

RecursiveBestFirstSearch

public RecursiveBestFirstSearch(EvaluationFunction ef,
                                boolean avoidLoops,
                                NodeExpander nodeExpander)

Method Detail

findActions

public java.util.List<Action> findActions(Problem p)

Description copied from interface: SearchForActions

Returns a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.

Specified by:

findActions in interface SearchForActions

Parameters:

p - the search problem

Returns:

a list of actions to the goal if the goal was found, a list containing a single NoOp Action if already at the goal, or an empty list if the goal could not be found.

getEvaluationFunction

public EvaluationFunction getEvaluationFunction()

getNodeExpander

public NodeExpander getNodeExpander()

Description copied from interface: SearchForActions

Returns the node expander used by the search. Useful for progress tracing.

Specified by:

getNodeExpander in interface SearchForActions

getMetrics

public Metrics getMetrics()

Returns all the search metrics.

Specified by:

getMetrics in interface SearchForActions