Search Algorithms
Best first search algorithms:
function BEST-FIRST-SEARCH(problem, f) returns a solution node or failure
node←NODE(STATE=[Link])
frontier←a priority queue ordered by f , with node as an element
reached←a lookup table, with one entry with key problem. INITIAL and value node
while not IS-EMPTY(frontier) do
node←POP(frontier)
if [Link]-GOAL([Link]) then return node
for each child in EXPAND(problem, node) do
s←[Link]
if s is not in reached or [Link]-COST < reached[s].PATH-COST then
reached[s]←child
add child to frontier
return failure
function EXPAND(problem, node) yields nodes
s←[Link]
for each action in [Link](s) do
s’←[Link](s, action)
cost←[Link]-COST + [Link]-COST(s, action,s’)
yield NODE(STATE=s’, PARENT=node, ACTION=action, PATH-COST=cost)
Figure The best-first search algorithm, and the function for expanding a node.
A very general approach is called best-first search, in which we choose a node, n, with minimum
value of some evaluation function, f(n). On each iteration we choose Evaluation function a node on
the frontier with minimum f(n) value, return it if its state is a goal state, and otherwise apply
EXPAND to generate child nodes. Each child node is added to the frontier if it has not been reached
before, or is re-added if it is now being reached with a path that has a lower path cost than any
previous path. The algorithm returns either an indication of failure, or a node that represents a path
to a goal. By employing different f(n) functions, we get different specific algorithms,
Search data structures
Search algorithms require a data structure to keep track of the search tree. A node in the tree
is represented by a data structure with four components:
• [Link]: the state to which the node corresponds;
• [Link]: the node in the tree that generated this node;
• [Link]: the action that was applied to the parent’s state to generate this node;
• [Link]-COST: the total cost of the path from the initial state to this node. In mathematical
formulas, we use g(node) as a synonym for PATH-COST.
We need a data structure to store the frontier. The appropriate choice is a queue of some
kind, because the operations on a frontier are:
• IS-EMPTY(frontier) returns true only if there are no nodes in the frontier.
• POP(frontier) removes the top node from the frontier and returns it.
• TOP(frontier) returns (but does not remove) the top node of the frontier.
• ADD(node, frontier) inserts node into its proper place in the queue.
Three kinds of queues are used in search algorithms:
Priority queue • A priority queue first pops the node with the minimum cost according to some
evaluation function, f . It is used in best-first search.
FIFO queue • A FIFO queue or first-in-first-out queue first pops the node that was added to the
queue first; we shall see it is used in breadth-first search.
LIFO queue • A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most
Stack recently added node; we shall see it is used in depth-first search.
Breadth-first search and uniform-cost search algorithms.
function BREADTH-FIRST-SEARCH(problem) returns a solution node or failure
node←NODE([Link])
if [Link]-GOAL([Link]) then return node
frontier←a FIFO queue, with node as an element
reached← {[Link]}
while not IS-EMPTY(frontier) do
node←POP(frontier)
for each child in EXPAND(problem, node) do
s←[Link]
if [Link]-GOAL(s) then return child
if s is not in reached then
add s to reached
add child to frontier
return failure
function UNIFORM-COST-SEARCH(problem) returns a solution node, or failure
return BEST-FIRST-SEARCH(problem, PATH-COST)
Iterative deepening and depth-limited tree-like search.
function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution node or failure
for depth = 0 to ∞ do
result←DEPTH-LIMITED-SEARCH(problem, depth)
if result ≠ cutoff then return result
function DEPTH-LIMITED-SEARCH(problem, l) returns a node or failure or cutoff
frontier←a LIFO queue (stack) with NODE([Link]) as an element
result←failure
while not IS-EMPTY(frontier) do
node←POP(frontier)
if [Link]-GOAL([Link]) then return node
if DEPTH(node) > l then
result←cutoff
else if not IS-CYCLE(node) do
for each child in EXPAND(problem, node) do
add child to frontier
return result
Bidirectional best-first search
function BIBF-SEARCH(problemF, fF, problemB, fB) returns a solution node, or failure
nodeF ←NODE([Link]) // Node for a start state
nodeB←NODE([Link]) // Node for a goal state
frontierF ←a priority queue ordered by fF, with nodeF as an element
frontierB←a priority queue ordered by fB, with nodeB as an element
reachedF ←a lookup table, with one key [Link] and value nodeF
reachedB←a lookup table, with one key [Link] and value nodeB
solution←failure
while not TERMINATED(solution, frontierF, frontierB) do
if fF(TOP(frontierF)) < fB(TOP(frontierB)) then
solution←PROCEED(F, problemF, frontierF, reachedF, reachedB, solution)
else solution←PROCEED(B, problemB, frontierB, reachedB, reachedF, solution)
return solution
function PROCEED(dir, problem, frontier, reached, reached2, solution) returns a solution
// Expand node on frontier; check against the other frontier in reached2.
// The variable “dir” is the direction: either F for forward or B for backward.
node←POP(frontier)
for each child in EXPAND(problem, node) do
s←[Link]
if s not in reached or PATH-COST(child) < PATH-COST(reached[s]) then
reached[s]←child
add child to frontier
if s is in reached2 then
solution2←JOIN-NODES(dir, child, reached2[s]))
if PATH-COST(solution2) < PATH-COST(solution) then
solution←solution2
return solution
