Artificial Intelligence

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