function GRAPH-SEARCH(problem) returns a solution, or failure
frontier ← a queue initially containing one path, for the problem's initial state
reached ← a table of {state: node}; initially empty
solution ← failure
while frontier is not empty and solution can possibly be improved do
parent ← some node that we choose to remove from frontier
for child in EXPAND(parent) do
s ← child.state
if s is not in reached or child is a cheaper path than reached[s] then
reached[s] ← child
add child to frontier
if s is a goal and child is cheaper than solution then
solution = child
return solution
function EXPAND(problem, parent) returns a list of nodes
s ← parent.state
nodes ← an empty list
for action in problem.actions(s) do
s' ← problem.result(s, action)
cost ← parent.path-cost + problem.step-cost(_s, action, s')
add node to nodes
return nodes
Figure ?? In the GRAPH-SEARCH algorithm, we keep track of the best solution found so far, as well as the states that we have already reached, and a frontier of paths from which we will choose the next path to expand. In any specific search algorithm, we specify (1) the criteria for ordering the paths in the frontier, and (2) the procedure for determining when it is no longer possible to improve on a solution.
function TREE-SEARCH(problem) returns a solution, or failure
initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution
expand the chosen node, adding the resulting nodes to the frontier
function GRAPH-SEARCH(problem) returns a solution, or failure
initialize the frontier using the initial state of problem
initialize the explored set to be empty
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
if the node contains a goal state then return the corresponding solution
add the node to the explored set
expand the chosen node, adding the resulting nodes to the frontier
only if not in the frontier or explored set
Figure ?? An informal description of the general tree-search and graph-search algorithms. The parts of GRAPH-SEARCH marked in bold italic are the additions needed to handle repeated states.