search

Procedures and classes for doing basic breadth-first and depth-first search, with and without dynamic programming.

search(initialState, goalTest, actions, successor, depthFirst=False, DP=True, maxNodes=10000)

Parameters:

initialState - root of the search
goalTest - function from state to Boolean
actions - a list of possible actions
successor - function from state and action to next state
depthFirst - do depth-first search if True, otherwise do breadth-first
DP - do dynamic programming if True, otherwise not
maxNodes - kill the search after it expands this many nodes

Returns:

path from initial state to a goal state as a list of (action, state) tuples

smSearch(smToSearch, initialState=None, goalTest=None, maxNodes=10000, depthFirst=False, DP=True)

Parameters:

smToSearch - instance of sm.SM defining a search domain; getNextValues is used to determine the successor of a state given an action
initialState - initial state for the search; if not provided, will use smToSearch.startState
goalTest - function that takes a state as an argument and returns True if it is a goal state, and False otherwise
maxNodes - maximum number of nodes to be searched; prevents runaway searches
depthFirst - if True, use depth first search; usually not a good idea
DP - if True, use dynamic programming; usually a good idea

Returns:

a list of the form

[(a0, s0), (a1, s1), (a2, s2), 
          ...]

where the a's are legal actions of c{smToSearch} and s's are states of that machine. s0 is the start state; the last state is a state that satisfies the goal test. If the goal is unreachable (within the search limit), it returns None.

pathValid(smToSearch, path)

Parameters:

smToSearch - instance of sm.SM defining a search domain
path - list of the form [(a0, s0), (a1, s1), (a2, s2), ...] where the a's are legal actions of c{smToSearch} and s's are states of that machine.

Returns:

True if taking action a1 in state s0 results in state s1, taking action a2 in state s1 results in state s2, etc. That is, if this path through the state space is executable in this state machine.

Classes
	SearchNode A node in a search tree
	Stack Simple implementation of stack using a Python list.
	Queue Simple implementation of queue using a Python list.

Variables
	somewhatVerbose = `False` If `True`, prints a trace of the search
	verbose = `False` If `True`, prints a verbose trace of the search
	__package__ = `None`

Module search

search(initialState, goalTest, actions, successor, depthFirst=False, DP=True, maxNodes=10000)

smSearch(smToSearch, initialState=None, goalTest=None, maxNodes=10000, depthFirst=False, DP=True)

pathValid(smToSearch, path)