Generic Search Algorithm in Pseudo-code
Input: a start state s_0
for each state s the successors of s
a test goals(s) checking whether s is a goal state
Set frontier := {s_0}
while frontier is not empty do
select and remove from frontier a path s_0...s_k
if goal(s_k) then
return s_0...s_k (and terminate)
else for every successor s of s_k and s_0...s_k s to frontier
end if
end while
- Lines 1-3 are specifying the input of the program.
- Line 5 sets the frontier (the set of paths) to s$_0$.
- Line 7 remove a path and expand it.
- Lines 8-9 if the final state in the frontier is the goal state then return the path and end.
- Line 10 if the goal isn’t reached then add all expansions of successors to the frontier.
The algorithm maintains a set called the frontier containing the paths. It is also sometimes called the agenda. As long as the frontier is not empty is selects and removes a path from itself and adds the paths expansions. The differences between algorithms are with which path is removed and expanded in the frontier.
BFS vs DFS
In line 7, if you remove and expand the item that was added first that is called breadth first. If you remove and expand the one that was added last that is a depth first search.