aima.core.search.uninformed

Class IterativeDeepeningSearch

java.lang.Object

aima.core.search.uninformed.IterativeDeepeningSearch

All Implemented Interfaces:

SearchForActions, SearchForStates

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

Artificial Intelligence A Modern Approach (3rd Edition): Figure 3.18, page 89.

 function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure
   for depth = 0 to infinity  do
     result <- DEPTH-LIMITED-SEARCH(problem, depth)
     if result != cutoff then return result
 

Figure 3.18 The iterative deepening search algorithm, which repeatedly applies depth-limited search with increasing limits. It terminates when a solution is found or if the depth- limited search returns failure, meaning that no solution exists.

Author:

Ravi Mohan, Ciaran O'Reilly, Ruediger Lunde

Field Summary

Fields

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

Constructor Summary

Constructors

Constructor and Description
IterativeDeepeningSearch()
IterativeDeepeningSearch(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.
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 metrics of the search.
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

Constructor Detail

IterativeDeepeningSearch

public IterativeDeepeningSearch()

IterativeDeepeningSearch

public IterativeDeepeningSearch(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.

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.

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

Description copied from interface: SearchForActions

Returns all the metrics of the search.

Specified by:

getMetrics in interface SearchForActions

Specified by:

getMetrics in interface SearchForStates