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
, orNone
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, andFalse
otherwise. - dfs – An optional boolean argument. If
True
, will run depth-first search. IfFalse
(default), will run breadth-first search.
Returns: A list of states, beginning with
start_state
, representing the path; orNone
if no path from start to goal exists.
-
lib601.search.
uniform_cost_search
(successors, start_state, goal_test, heuristic=<function <lambda>>)¶ 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, wherechild
is a state that is directly reachable from the input state, andcost
is the cost of transitioning directly from the state being considered tochild
. - 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, andFalse
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; orNone
if no path from start to goal exists.- 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