Solving

Problems by
Searching-III
PREPARED BY:
MRS. S. R. GHORPADE
Searching for Solutions
A solution is an action sequence, so search
algorithms work by considering various possible
action sequences.
 The possible action sequences starts at the initial
state and form a search tree with the initial state
at the root;
 The branches are actions and the nodes
correspond to states in the state space of the
problem.
 Partial search trees for finding a route from Arad to Bucharest. Nodes that have
been expanded are shaded; nodes that have been generated but not yet expanded are
outlined in bold; nodes that have not yet been generated are shown in faint dashed
lines.
Searching for Solutions

 Figure shows the first few steps in growing the

search tree for finding a route from Arad to
Bucharest.
 The root node of the tree corresponds to the
initial state, In(Arad).
 The first step is to test whether this is a goal
state.
Searching for Solutions
 Then there is a need to consider taking various
actions.
 One can do this by expanding the current state;
that is, applying each legal action to the current
state, thereby generating a new set of states.
 In this case, one can add three branches from the
parent node In(Arad) leading to three new child
nodes: In(Sibiu), In(Timisoara), and In(Zerind).
Now one must choose which of these three
possibilities to consider further.
Searching for Solutions
 This is the essence of search—following up one
option now and putting the others aside for
later, in case the first choice does not lead to a
solution.
 Suppose we choose Sibiu first.
 We check to see whether it is a goal state (it is
not) and then expand it to get In(Arad),
In(Fagaras), In(Oradea), and
In(RimnicuVilcea).
 We can then choose any of these four or go
back and choose Timisoara or Zerind.
Searching for Solutions
 Each of these six nodes is a leaf node, that
is, a node with no children in the tree.
 The set of all leaf nodes available for
expansion at any given point is called the
frontier.
 In Figure the frontier of each tree consists
of those nodes with bold outlines.
 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.
Searching for Solutions
 The process of expanding nodes on the frontier
continues until either a solution is found or there
are no more states to expand.
 The general TREE-SEARCH algorithm is shown
informally in Figure.
 Search algorithms all share this basic structure;
they vary primarily according to how they choose
which state to expand next—the so-called search
strategy.
Searching for Solutions
 The search tree includes the path from Arad to
Sibiu and back to Arad again!
 We say that In(Arad) is a repeated state in the
search tree, generated in this case by a loopy
path.
 Considering such loopy paths means that the
complete search tree for Romania is infinite
because there is no limit to how often one can
traverse a loop.
Searching for Solutions
 Loops can cause certain algorithms to fail,
making otherwise solvable problems
unsolvable.
 Fortunately, there is no need to consider loopy
paths.
 We can rely on more than intuition for this:
because path costs are additive and step costs
are nonnegative, a loopy path to any given state
is never better than the same path with the loop
removed.
Searching for Solutions
 Loopy paths are a special case of the more
general concept of redundant paths, which exist
whenever there is more than one way to get from
one state to another.
 Consider the paths Arad–Sibiu (140 km long)
and Arad–Zerind–Oradea–Sibiu (297 km long).
 Obviously, the second path is redundant—it’s
just a worse way to get to the same state.
Searching for Solutions

 If you are concerned about reaching the

goal, there’s never any reason to keep
more than one path to any given state,
because any goal state that is reachable by
extending one path is also reachable by
extending the other.
Searching for Solutions

 In some cases, it is possible to define the

problem itself so as to eliminate redundant
paths.
 For example, if we formulate the 8-queens
problem so that a queen can be placed in any
column, then each state with n queens can be
reached by n! different paths; but if we
reformulate the problem so that each new queen
is placed in the leftmost empty column, then
each state can be reached only through one path.
Searching for Solutions

 In other cases, redundant paths are unavoidable.

 This includes all problems where the actions are
reversible, such as route-finding problems and
sliding-block puzzles.
 Route finding on a rectangular grid is a particularly
important example in computer games.
Searching for Solutions
 In such a grid, each state has four successors, so a
search tree of depth d that includes repeated states
has 4^d leaves; but there are only about 2*d^2
distinct states within d steps of any given state.
 For d = 20, this means about a trillion nodes but
only about 800 distinct states. Thus, following
redundant paths can cause a tractable problem to
become intractable. This is true even for algorithms
that know how to avoid infinite loops.
Searching for Solutions
 Theway to avoid exploring redundant paths is to
remember where one has been.
 To do this, we augment the TREE-SEARCH
algorithm with a data structure called the explored
set (also known as the closed list), which
remembers every expanded node.
 Newly generated nodes that match previously
generated nodes—ones in the explored set or the
frontier—can be discarded instead of being added
to the frontier.
Searching for Solutions
 The new algorithm, called GRAPH-SEARCH, is
shown informally in Figure.
 The specific algorithms in this chapter draw on this
general design.
 Clearly, the search tree constructed by the GRAPH-
SEARCH algorithm contains at most one copy of
each state, so we can think of it as growing a tree
directly on the state-space graph, as shown in
Figure.
 A sequence of search trees generated by a graph search on the
Romania problem At each stage, each path is extended by one
step. Notice that at the third stage, the northernmost city
(Oradea) has become a dead end: both of its successors are
already explored via other paths.
Searching for Solutions
 The algorithm has another nice property: the
frontier separates the state-space graph into the
explored region and the unexplored region, so
that every path from the initial state to an
unexplored state has to pass through a state in
the frontier.
 This property is illustrated in Figure.
Searching for Solutions

 As every step moves a state from the

frontier into the explored region while
moving some states from the unexplored
region into the frontier, we see that the
algorithm is systematically examining the
states in the state space, one by one, until it
finds a solution.
 The separation property of GRAPH-SEARCH, illustrated on a
rectangular-grid problem. The frontier (white nodes) always separates the
explored region of the state space (black nodes) from the unexplored
region (gray nodes). In (a), just the root has been expanded. In (b), one
leaf node has been expanded. In (c), the remaining successors of the root
have been expanded in clockwise order.
Infrastructure for search
algorithms
 Search algorithms require a data structure to
keep track of the search tree that is being
constructed.
 For each node n of the tree, we have a
structure that contains four components:
Infrastructure for search
algorithms
 [Link]: the state in the state space to which
the node corresponds;
 [Link]: the node in the search tree that
generated this node;
 [Link]: the action that was applied to the
parent to generate the node;
 [Link]-COST: the cost, traditionally denoted
by g(n), of the path from the initial state to the
node, as indicated by the parent pointers.
 Given the components for a parent node, it
is easy to see how to compute the
necessary components for a child node.
 The function CHILD-NODE takes a
parent node and an action and returns the
resulting child node:
Infrastructure for search
algorithms

 The node data structure is depicted in Figure.

 Nodes are the data structures from which the search tree is constructed.
Each has a parent, a state, and various book keeping fields. Arrows
point from child to parent.
Infrastructure for search
algorithms
 Notice how the PARENT pointers string
the nodes together into a tree structure.
 These pointers also allow the solution path
to be extracted when a goal node is found;
we use the SOLUTION function to return
the sequence of actions obtained by
following parent pointers back to the root.
Infrastructure for search
algorithms
 Up to now, we have not been very careful to
distinguish between nodes and states, but in
writing detailed algorithms it’s important to make
that distinction.
A node is a bookkeeping data structure used to
represent the search tree.
A state corresponds to a configuration of the
world.
Infrastructure for search
algorithms
 Thus,
nodes are on particular paths, as defined by
PARENT pointers, whereas states are not.
 Furthermore, two different nodes can contain the
same world state if that state is generated via two
different search paths.
 Now that we have nodes, we need somewhere to
put them.
 The frontier needs to be stored in such a way that
the search algorithm can easily choose the next
node to expand according to its preferred strategy.
Infrastructure for search
algorithms
 The appropriate data structure for this is a
queue. The operations on a queue are as
follows:
• EMPTY?(queue) returns true only if there are
no more elements in the queue.
• POP(queue) removes the first element of the
queue and returns it.
• INSERT(element, queue) inserts an element
and returns the resulting queue.
Infrastructure for search
algorithms
 Queues are characterized by the order in which
they store the inserted nodes.
 Three common variants are the first-in, first-out
or FIFO queue, which pops the oldest element
of the queue; the last-in, first-out or LIFO
queue (also known as a stack), which pops the
newest element of the queue; and the priority
queue, which pops the element of the queue
with the highest priority according to some
ordering function.
Infrastructure for search
algorithms
 The explored set can be implemented with a
hash table to allow efficient checking for
repeated states.
 With a good implementation, insertion and
lookup can be done in roughly constant time
no matter how many states are stored.
 One must take care to implement the hash
table with the right notion of equality between
states.
Infrastructure for search
algorithms
 For example, in the traveling salesperson problem, the
hash table needs to know that the set of visited cities
{Bucharest,Urziceni,Vaslui} is the same as
{Urziceni,Vaslui,Bucharest}.
 Sometimes this can be achieved most easily by insisting
that the data structures for states be in some canonical
form; that is, logically equivalent states should map to the
same data structure.
 In the case of states described by sets, for example, a bit-
vector representation or a sorted list without repetition
would be canonical, whereas an unsorted list would not.
Thank You