Graph Search (lib601.search)

Procedures and classes for doing breadth-first and depth-first search, and uniform-cost search.

class lib601.search.SearchNode(state, parent, cost=0.0)

A class representing a single node in a search tree.

Parameters:
  • state – The search-space state represented by this node.
  • parent – This node’s parent, as an instance of SearchNode, or None if this node is the root of the search tree.
  • cost – The cost of the entire path from the root of the search tree to this node.
path()
Returns:A list of states representing the partial path from the root of the search tree to this node.
lib601.search.search(successors, start_state, goal_test, dfs=False)

Run a basic (BFS or DFS) search from start_state, until goal_test is satisfied, using the dynamic programming principle.

Parameters:
  • successors – A function defining the search domain; takes a state as input and returns a list of the states that are directly reachable from that state.
  • start_state – The state from which to start the search.
  • goal_test – A function whose input is a state, and which outputs True if that state satisfies the goal conditions, and False otherwise.
  • dfs – An optional boolean argument. If True, will run depth-first search. If False (default), will run breadth-first search.
Returns:

A list of states, beginning with start_state, representing the path; or None if no path from start to goal exists.

Run a uniform-cost search from start_state, until goal_test is satisfied.

Parameters:
  • successors – A function defining the search domain; takes a state as input and returns a list of pairs of the states that are directly reachable from this state with the associated cost. The list returned by this function should be a list of (child, cost) tuples, where child is a state that is directly reachable from the input state, and cost is the cost of transitioning directly from the state being considered to child.
  • start_state – The state from which to start the search.
  • goal_test – A function whose input is a state, and which outputs True if that state satisfies the goal conditions, and False otherwise.
  • heuristic – A function mapping states to numerical heuristic values. Defaults to a function that always returns 0.
Returns:

A list of states (beginning with start_state), representing the path; or None if no path from start to goal exists.