aima.core.search.uninformed

Class DepthLimitedSearch

java.lang.Object

aima.core.search.uninformed.DepthLimitedSearch

All Implemented Interfaces:

SearchForActions, SearchForStates

public class DepthLimitedSearch
extends java.lang.Object
implements SearchForActions, SearchForStates

Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.17, page 88.

 function DEPTH-LIMITED-SEARCH(problem, limit) returns a solution, or failure/cutoff
   return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE), problem, limit)
   
 function RECURSIVE-DLS(node, problem, limit) returns a solution, or failure/cutoff
   if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
   else if limit = 0 then return cutoff
   else
       cutoff_occurred? <- false
       for each action in problem.ACTIONS(node.STATE) do
           child <- CHILD-NODE(problem, node, action)
           result <- RECURSIVE-DLS(child, problem, limit - 1)
           if result = cutoff then cutoff_occurred? <- true
           else if result != failure then return result
       if cutoff_occurred? then return cutoff else return failure
 

Figure 3.17 A recursive implementation of depth-limited search.

Author:

Ravi Mohan, Ciaran O'Reilly, Mike Stampone, Ruediger Lunde

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor and Description
DepthLimitedSearch(int limit)
DepthLimitedSearch(int limit, 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, an empty list if the goal could not be found.
Node	findNode(Problem p)
java.lang.Object	findState(Problem p) Returns a state which is might be but not necessary is a goal state of the problem.
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_PATH_COST

public static final java.lang.String METRIC_PATH_COST

See Also:

Constant Field Values

CUTOFF_NODE

public static final Node CUTOFF_NODE

Constructor Detail

DepthLimitedSearch

public DepthLimitedSearch(int limit)

DepthLimitedSearch

public DepthLimitedSearch(int limit,
                          NodeExpander nodeExpander)

Method Detail

findActions

public 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, an empty list if the goal could not be found.

Specified by:

findActions in interface SearchForActions

Parameters:

p - the search problem

Returns:

if goal found, the list of actions to the Goal. If already at the goal you will receive a List with a single NoOp Action in it. If fail to find the Goal, an empty list will be returned to indicate that the search failed.

findState

public java.lang.Object findState(Problem p)

Description copied from interface: SearchForStates

Returns a state which is might be but not necessary is a goal state of the problem.

Specified by:

findState in interface SearchForStates

Parameters:

p - the search problem

Returns:

a state.

findNode

public Node findNode(Problem p)

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

Specified by:

getNodeExpander in interface SearchForStates

getMetrics

public Metrics getMetrics()

Returns all the search metrics.

Specified by:

getMetrics in interface SearchForActions

Specified by:

getMetrics in interface SearchForStates