Search Algorithms

A search algorithm takes a search problem as input and returns a solution, or an

indication of Search algorithm failure. In this chapter we consider algorithms that
superimpose a search tree over the state space graph, forming various paths from
the initial state, trying to find a path that reaches a goal state.

Each node in the search tree corresponds to a state in the state space and the edges
Node in the search tree correspond to actions. The root of the tree corresponds to
the initial state of the problem. It is important to understand the distinction
between the state space and the search tree. The state space describes the (possibly
infinite) set of states in the world, and the actions that allow transitions from one
state to another.

The search tree describes paths between these states, reaching towards the goal.
The search tree may have multiple paths to (and thus multiple nodes for) any
given state, but each node in the tree has a unique path back to the root (as in all
trees).
Figure shows the first few steps in finding a path from Arad to Bucharest. The
root node of the search tree is at the initial state, Arad.
the available ACTIONS for that state, using the RESULT function to see where
those actions Generating lead to, and generating a new node (called a child node
or successor node) for each of the Child node

Successor node resulting states. Each child node has Arad as its parent node.
Parent node Now we must choose which of these three child nodes to consider
next. This is the essence of search—following up one option now and putting the
others aside for later.

Suppose we choose to expand Sibiu first. Figure (bottom) shows the result: a set
of 6 unex Frontier panded nodes (outlined in bold). We call this the frontier of
the search tree. We say that any Reached state that has had a node generated for
it has been reached (whether or not that node has been expanded).

Figure shows the search tree superimposed on the state-space graph. Separator
Note that the frontier separates two regions of the state-space graph: an interior
region here every state has been expanded, and an exterior region of states that
have not yet been reached
Best-_rst search

A very general approach

is called best-first search, in which we choose a node, n, with minimum value of
some Best-_rst search evaluation function, f (n). Figure shows the algorithm. 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, which this chapter
will cover.

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:

• node.STATE: the state to which the node corresponds;

• node.PARENT: the node in the tree that generated this node;
• node.ACTION: the action that was applied to the parent’s state to generate this
node;
• node.PATH-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.
Following the PARENT pointers back from a node allows us to recover the states
and actions along the path to that node. Doing this from a goal node gives us the
solution.
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.

The reached states can be stored as a lookup table (e.g. a hash table) where each
key is a state and each value is the node for that state.

Redundant paths
The search tree shown in Figure includes a path from Arad to Sibiu and back to
Repeated state Arad again. We say that Arad is a repeated state in the search tree,
generated in this case by Cycle a cycle (also known as a loopy path). So even
though the state space has only 20 states, the Loopy path complete search tree is
infinite because there is no limit to how often one can traverse a loop.

Redundant path A cycle is a special case of a redundant path. For example, we

can get to Sibiu via the path Arad–Sibiu (140 miles long) or the path Arad–
Zerind–Oradea–Sibiu (297 miles long).
This second path is redundant—it’s just a worse way to get to the same state—
and need not be considered in our quest for optimal paths.

Consider an agent in a 10_10 grid world, with the ability to move to any of 8
adjacent squares. If there are no obstacles, the agent can reach any of the 100
squares in 9 moves or fewer. But the number of paths of length 9 is almost 89 (a
bit less because of the edges of the grid), or more than 100 million. In other words,
the average cell can be reached by over a million redundant paths of length 9, and
if we eliminate redundant paths, we can complete a I search roughly a million
times faster. As the saying goes, algorithms that cannot remember the past are
doomed to repeat it. There are three approaches to this issue.

First, we can remember all previously reached states (as best-first search does),
allowing us to detect all redundant paths, and keep only the best path to each state.
This is appropriate for state spaces where there are many redundant paths, and is
the preferred choice when the table of reached states will fit in memory.

Second, we can not worry about repeating the past. There are some problem
formulations where it is rare or impossible for two paths to reach the same state.
An example would be an assembly problem where each action adds a part to an
evolving assemblage, and there is an ordering of parts so that it is possible to add
A and then B, but not B and then A.

For those problems, we could save memory space if we don’t track reached states
and we don’t check Graph search for redundant paths. We call a search algorithm
a graph search if it checks for redundant Tree-like search paths and a tree-like
search6 if it does not check.

The BEST-FIRST-SEARCH algorithm in Figure is a graph search algorithm; if

we remove all references to reached we get a treelike search that uses less memory
but will examine redundant paths to the same state, and thus will run slower.
Third, we can compromise and check for cycles, but not for redundant paths in
general.

Since each node has a chain of parent pointers, we can check for cycles with no
need for additional memory by following up the chain of parents to see if the state
at the end of the path has appeared earlier in the path. Some implementations
follow this chain all the way up, and thus eliminate all cycles; other
implementations follow only a few links (e.g., to the parent, grandparent, and
great-grandparent), and thus take only a constant amount of time, while
eliminating all short cycles (and relying on other mechanisms to deal with long
cycles).

Measuring problem-solving performance

Before we get into the design of various search algorithms, we will consider the
criteria used to choose among them. We can evaluate an algorithm’s performance
in four ways:
_ Completeness

Cost optimality
_ Time complexity
Space complexity

To understand completeness, consider a search problem with a single goal. That

goal could be anywhere in the state space; therefore a complete algorithm must
be capable of systematically exploring every state that is reachable from the initial
state.
In finite state spaces that is straightforward to achieve: as long as we keep track
of paths and cut off ones that are cycles (e.g. Arad to Sibiu to Arad), eventually
we will reach every reachable state. In infinite state spaces, more care is
necessary.
For example, an algorithm that repeatedly applied the “factorial” operator in
Knuth’s “4” problem would follow an infinite path from 4 to 4! to (4!)!, and so
on. Similarly, on an infinite grid with no obstacles, repeatedly moving forward in
a straight line also follows an infinite path of new states. In both cases the
algorithm never returns to a state it has reached before, but is incomplete because
wide expanses of the state space are never reached.

To be complete, a search algorithm must be systematic in the way it explores an

infinite Systematic state space, making sure it can eventually reach any state that
is connected to the initial state. For example, on the infinite grid, one kind of
systematic search is a spiral path that covers all the cells that are s steps from the
origin before moving out to cells that are s+1 steps away.

Unfortunately, in an infinite state space with no solution, a sound algorithm needs

to keep searching forever; it can’t terminate because it can’t know if the next state
will be a goal.

Time and space complexity are considered with respect to some measure of the
problem difficulty. In theoretical computer science, the typical measure is the size
of the state-space graph, jVj+jEj, where jVj is the number of vertices (state nodes)
of the graph and jEj is the number of edges (distinct state/action pairs).

But in many AI problems, the graph is represented only implicitly by the initial
state, actions, and transition model. For an implicit Depth state space, complexity
can be measured in terms of d, the depth or number of actions in
an optimal solution; m, the maximum number of actions in any path; and b, the
branching Branching factor factor or number of successors of a node that need to
be considered.