47 Generic tree search

function Tree-Search(problem, strategy) returns a solution or failure
    initialize the search tree using the start state of problem as the root node
    put the root node into Frontier
 
    loop do
        if Frontier is empty then
            return failure
 
        choose a node from Frontier according to strategy
        remove the chosen node from Frontier
 
        if the node contains a goal state then
            return the corresponding solution
 
        else
            expand the node using problem
            add the resulting nodes to Frontier

Important things :

• Frontier : to store the nodes waiting for expansion.
• Expansion : to find and display the children of the node.
• Expansion strategy : to decide which node in Frontier to expand (like depth first search), also called to explore.

Depth First Search (DFS)

• The order of the nodes to be expanded (tie is broken from left to right)

Breadth-First Search (BFS)

• The order of the nodes to be expanded (tie is broken from left to right)