Searching

There are 2 basic ways to perform a search:

• Blind search -- can only move according to position in search.
• Heuristic search -- use domain-specific information to decide where to search next.

Blind Search Depth-First Search

1. Set L to be a list of the initial nodes in the problem.
2. If L is empty, fail otherwise pick the first node n from L
3. If n is a goal state, quit and return path from initial node.
4. Otherwise remove n from L and add to the front of L all of n's children. Label each child with its path from initial node. Return to 2.

Note: All numbers in Fig 1 refer to order visited in search.

Breadth-First Search

1. Set L to be a list of the initial nodes in the problem.
2. If L is empty, fail otherwise pick the first node n from L
3. If n is a goal state, quit and return path from initial node.
4. Otherwise remove n from L and add to the end of L all of n's children. Label each child with its path from initial node. Return to 2.

Note: All numbers in Fig 1 refer to order visited in search.