#### Class examples: depth-first, breadth-first, best-first search (9/10/00)

Depth-First-Search [Nodes]
IF there are no more nodes THEN FAIL
ThisNode <-- First(Nodes)
IF ThisNode is the goal
THEN return ThisNode
ELSE
ChildNodes <-- Children(ThisNode)
Depth-First-Search
(Append-to-Front ChildNodes Rest(Nodes))

Breadth-First-Search [Nodes]
IF there are no more nodes THEN FAIL
ThisNode <-- First(Nodes)
IF ThisNode is the goal
THEN return ThisNode
ELSE
ChildNodes <-- Children(ThisNode)
Breadth-First-Search
(Append-to-Front Rest(Nodes) ChildNodes)

Depth-First-Search [Nodes]
IF there are no more nodes THEN FAIL
ThisNode <-- First(Nodes)
<< What if we have already examined ThisNode?
Suppose ThisNode occurs as an ancestor
in the tree?
Suppose ThisNode was found earlier to
be a dead end?
Suppose ThisNode is somewhere on the
list of Nodes? >>
IF ThisNode is the goal
THEN return ThisNode
<< Should we return the entire path from the
initial state to ThisNode? >>
ELSE
ChildNodes <-- Children(ThisNode)
<< Should we only include new child nodes?
That are not on the list of Nodes?
That have not been found to be dead ends? >>
Depth-First-Search
(Append-to-Front ChildNodes Rest(Nodes))

Best-First-Search [Nodes]
IF there are no more nodes THEN FAIL
ThisNode <-- Most-Promising(Nodes)
IF ThisNode is the goal
THEN return ThisNode
ELSE
ChildNodes <-- Children(ThisNode)
Best-First-Search
(Append-to-Front
ChildNodes
Remove-Node(ThisNode Nodes))