Solving problems by

searching
Chapter 3
 Outline

• Problem-solving agents
• Problem types
• Problem formulation
• Example problems
• Basic search algorithms
2
 Problem solving agent

• A problem can be defined or formulated formally by 4 components:-

• Initial state :- Describes possible initial state from where problem solving agent
starts in.

• A set of actions and Successor Function:- Given a particular state x, Successor

Function (SF (x)) returns a set of <action, successor> ordered pairs, where each
action is one of the legal actions in state x and each successor is a state that can
be reached from x by applying the action.
Together, the initial state and successor function implicitly define the state space of
the problem i.e. the set of all states reachable from the initial state.
Initial state + SF => state space 3
 Problem solving …..

State space forms a graph in which the nodes are states and the arcs between nodes are
actions. (It defines all the possible configurations of the relevant objects associated with
the problem.)
• Goal test :- It determines whether a given state is a goal state.
• Path cost :- A path in the state space is a sequence of states connected by a sequence of
actions. A path cost function assigns a numeric cost to each path. The problem-solving
agent chooses a cost function that reflects its own performance measure.
Path cost = ∑Step costs => Sum of the costs of the individual actions along the path.
(Step cost of taking action a to go from state x to state y is denoted by c(x, a, y) )
4
 Problem solving…
• These four components that define a problem can be gathered together into a
single data structure that is given as input to a problem-solving algorithm.

• A solution to a problem is a path from the initial state to a goal state.

• Solution quality is measured by the path cost function, and an optimal solution has
the lowest path cost among all solutions.

• Problem solving agent use atomic representations.

Problem-solving agents

6
 Example: Romania
• On holiday in Romania; currently in Arad.
• Formulate goal:
• To be in Bucharest
• Formulate problem:
• states: various cities
• actions: drive between cities
• Find solution:
• sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest 7
• The initial sate for our agent romania is described as In(Arad).
• For example, from the state In(Arad) , the applicable actions are { Go(Sibiu), Go (Timisoara),
Go(Zerind)}.

• The transition model gives description of what each action does and is specified by a function
RESULT(s,a). It returns the state that results from doing action a in state s.

• The term successor is used to refer to any state reachable from a given state by single action.
For example, we have
RESULT(In(Arad), Go(Zerind))=In(Zerind)

• The agent’s goalin Romania is the singleton set {In(Bucharest)}

• The step cost of taking action a in state s to reach state s’ is denoted by c(s,a,s’). The step
costs are non-negative.

• A solution to a problem is an action sequence that leads from the initial state to a goal state.
• Optimal solution has the lowest path cost among all the solutions.
Romania with step costs in km
 Selecting a state space
• Real world is absurdly complex
state space must be abstracted for problem solving. The process of removing detail from a
presentation is called abstraction; for example the traveling companions, the current radio
program, the scenery out of the window, the proximity of law enforcement
officers, the distance to the next rest stop, the condition of the road, the weather, and so on. All
these considerations are left out of our state descriptions because they are irrelevant to the
problem of finding a route to Bucharest. T
• (Abstract) state = set of real states

• (Abstract) action = complex combination of real actions

• e.g., "Arad Zerind" represents a complex set of possible routes, detours, rest stops, etc.

• For guaranteed realizability, any real state "in Arad“ must get to some real state "in Zerind"

• (Abstract) solution =

• set of real paths that are solutions in the real world 10

• Each abstract action should be "easier" than the original problem

 Problem formulation for Toy problems

• Simple vacuum world problem

• 8 – puzzle problem (or Sliding block problem)
• 8 – queen problem
• Knuth number generation problem
 Simple vacuum world problem
(State space graph)

• states?
• actions?
• goal test?
The state space for the vacuum world. Links denote actions: L = Left,R=
• path cost? Right,S= Suck.
12
 Simple vacuum world problem
(State space graph)…

• states? dirt and location

• actions? Left, Right, Suck
• goal test? no dirt at all locations
• path cost? 1 per action 13
 The 8-puzzle problem

• states?
• actions?
• goal test?
• path cost?
14
 The 8-puzzle problem…

• It consists of 3*3 board with eight numbered tiles and a blank space. The tile adjacent to the
• blank space can slide into the space. The object is to reach a specified goal state as shown in the
figure.

• states? locations of tiles

• actions? move blank left, right, up, down
• goal test? = goal state (given)
• path cost? 1 per move
15
[Note: optimal solution of n-Puzzle family is NP-hard]
8-Queen problem
The goal of the 8-queens problem is to place eight queens on a
chessboard such that no queen attacks any other.There are two
main kinds of formulation. An incremental formulation
involves operators that augment the state description, starting
with an empty state; for the 8-queens problem, this means that
each action adds a queen to the state. A complete-state
formulation starts with all 8 queens on the board and moves
them around. In either case, the path cost is of no interest
because only the final state counts. The first incremental
formulation one might try is the following:
8-Queen problem…
Knuth’ s Number Generation
 Problem formulation for Real world problems

• The route-finding problem is defined in terms of specified locations and transitions

along links between them.
• Route-finding algorithms are used in a variety of applications.
• Some, such as Web sites and in-car systems that provide driving directions, are
relatively straightforward extensions of the Romania example.
• Others, such as routing video streams in computer networks, military operations
planning, and airline travel-planning
• systems, involve much more complex specifications.
 Airline Travel Problem

Consider the airline travel problem that must be solved • Transition model: The state resulting from taking a
by a travel-planning Web site: flight will have the flight’s destination as the current
• States: Each state obviously includes a location (e.g., location and the flight’s arrival time as the current time.
an airport) and the current time. Furthermore, because Transition model gives the description of what each
the cost of an action (a flight segment) may depend on action does.
previous segments, their fare bases, and their status as • Goal test: Are we at the final destination specified by
domestic or international, the state must record extra the user?
information about these “historical” aspects.
• Path cost: This depends on monetary cost, waiting
• Initial state: This is specified by the user’s query. time, flight time, customs and immigration procedures,
• Actions: Take any flight from the current location, in seat quality, time of day, type of airplane,
any seat class, leaving after the current time, leaving frequent-flyer mileage awards, and so on.
enough time for within-airport transfer if needed.
 Some but not exhaustive list of Real world
problems
• Touring problems
• Traveling salesperson problem (TSP)
• VLSI layout problem
• Robot navigation
• Automatic assembly sequencing
• Protein design
 Travelling salesman problem
• It is related to route finding problems in which each city must be visited
exacltly once while finding the shortest tour.

• It is a NP-hard problem.
VLSI layout problem
• This problem requires positioning of millions of components and connections
on a chip to minimize area, minimize circuit delays, minimize stray
capacitances, and maximize manufacturing yield.

• The aim is to place cells on the chip so that they do not overlap and so that
there is room for the connecting wires to be placed between the cells.
 Robot navigation problem
• It is a route finding problem where the robot can move in a continous space with an infinite
set of possible actions and states.
• For a circular robot moving on a flat surface, the space is two dimensional.
• When the robot has arms and legs or wheels that must be controlled, the search space
becomes many-dimensional.
• The robots must deal with errors in their sensors and motor controls while addressing the
complexity of the problem.
Automatic assembly sequencing problem
• Here, the automatic assmbly sequencing of complex objects are carried out by robots.
• The aim is to find an order in which to assemble the parts of some object.
• If the wrong order is chosen, there will be no way to add some part later in the sequence
without undoing some of the work already done.
• In protein design problem the goal is to find a sequence of amino acids that wil fold
into a three-dimensional protein with the right properties to cure some disease.
 Basic AI problem solving techniques

• Problem solving by searching

• Problem solving by Reasoning / Inference

• Problem solving by Matching

24
 Informal Tree search algorithm

• Basic idea:
• offline, simulated exploration of state space by generating
successors of already-explored states (a.k.a.~expanding states)

25
Tree search example

26
Tree search example

27
Tree search example

28
Informal Graph search algorithms
Some examples of Graph search
 State vs. node
• A state is a (representation of) a physical configuration
• A node is a data structure constituting part of a search tree includes
state, parent node, action, path cost g(x), depth

• The Expand function creates new nodes, filling in the various fields
and using the SuccessorFn of the problem to create the
corresponding states.

31
Node Details
Implementation: general tree search

33
 Implementation of nodes in search algorithm

• A node is a bookkeeping data structure used to represent the search tree. A

state corresponds to a configuration of the world. 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. The appropriate data
structure for this is a queue.
• A particular search tree has 6 nodes at level 3. At the next level, there are 24
nodes. What is the branching factor at level 3?
 Implementation of nodes in search algorithm
• 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.
• Queues are characterized by the order in which they store the inserted nodes.
• Three common variants are:
• FIFO queue, which pops the oldest element of the queue;
• LIFO queue (also known as a stack), which pops the newest element of the queue;
• Priority queue, which pops the element of the queue with the highest priority according to
some ordering function
 Evaluating Search strategies
• Performance of search strategies are evaluated along the following dimensions:-
• Completeness: does it always find a solution if one exists?

• Time complexity: number of nodes generated

• Space complexity: maximum number of nodes in memory

• Optimality: does it always find a least-cost solution?

• Time and space complexities are measured in terms of

• b: the branching factor or maximum number of successors of any node

• d: the depth of the shallowest goal node (i.e., the number of steps along the path from the root)
36
• m: the maximum length of any path in the state space (may be ∞)
 Evaluating Search strategies…
• Time is often measured in terms of the number of nodes generated during the
search, and space in terms of the maximum number of nodes stored in memory.

• For the most part, we describe time and space complexities for search on a tree; for
a graph, the answer depends on how “redundant” the paths in the state space are.

• To assess the effectiveness of a search algorithm, we can consider just the search
cost— which typically depends on the time complexity but can also include a term
for memory usage.

• Or we can use the total cost, which combines the search cost and the path cost of
the solution found (also sometimes called solution cost).
 Search strategies
They are of 2 types:-
• Uninformed search / Blind search
Blind search has no additional information about the states
beyond that provided in the problem definition. All they can
do is generate successor and distinguish a goal state from a
non-goal state.
• Informed search / Heuristic search
Informed search identifies whether one non-goal state is
“more promising” than another one.
All search strategies are distinguished by the order in which nodes are expanded. 38
 Uninformed search strategies
• Uninformed search strategies use only the information available in the
problem definition. Popular ones are:
• Breadth-first search (BFS)
• Uniform-cost search (UCS)
• Depth-first search (DFS)
• Depth-limited search (DLS)
• Iterative deepening search (IDS)
39
• Bidirectional search (BDS)
 Breadth-first search

• It is a strategy in which the root node is expanded first, then all the successors
of the root node are expanded, then their successors. At a given depth in the
search tree, all the nodes are expanded before any node at the next level is
expanded.

• A FIFO queue is used i.e, new successors join the tail of the queue.
40
Breadth Fast Search Algorithm
 Breadth-first search algorithm

• Create a variable NODE-LIST (FIFO queue) and set it to initial state.

• Until a goal state is found or the NODE-LIST is empty,
Do

A. If NODE-LIST is empty then quit.

else remove the first element from NODE-LIST and call it V(visited)

42
 Breadth-first search algorithm

B. For each rule ( from the rule set ) whose L.H.S matches with the
state described in V
Do
I. Apply the rule to generate a new state.

II. If the new state is a goal state then quit and return the state.

III. Otherwise add the new state to the end of the NODE-LIST.

43
 Breadth-first search

• Expand shallowest unexpanded node

• Implementation:
• fringe is a FIFO queue, i.e., new successors go at end

44
 Breadth-first search

• Expand shallowest unexpanded node

• Implementation:
• fringe is a FIFO queue, i.e., new successors go at end
45
 Breadth-first search

• Expand shallowest unexpanded node

• Implementation:
46
• fringe is a FIFO queue, i.e., new successors go at end
 Properties of breadth-first search

• Complete? Yes (if b is finite)

• Time? 1+b+b2+b3+… +bd = O(bd)

• Space? O(bd) (keeps every node in memory)

• Optimal? Yes ( if path cost is a non-decreasing function of depth i.e path cost = 1 per step)

• Space is the bigger problem (more than time)

47
Breadth Fast Search
 Uniform cost search (UCS)

• This algorithm comes into play when a different cost is available for each
edge.
• When all step costs are equal, breadth-first search is optimal because it always
expands the shallowest unexpanded node.
• By a simple extension, we can find an algorithm that is optimal with any
step-cost function. Instead of expanding the shallowest node, uniform-cost
search expands the node n with the lowest path cost g(n).
• This is done by storing the frontier as a priority queue ordered by g.
•
Uniform cost search (UCS)…
function UNIFORM-COST-SEARCH(problem) returns a solution, or failure

• node ←a node with STATE = problem.INITIAL-STATE, PATH-COST = 0

• frontier ←a priority queue ordered by PATH-COST, with node as the only element

• explored ←an empty set

• loop do

• if EMPTY?( frontier) then return failure

• node←POP( frontier ) /* chooses the lowest-cost node in frontier */

• if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

• add node.STATE to explored

• for each action in problem.ACTIONS(node.STATE) do

• child ←CHILD-NODE(problem, node, action)

• if child .STATE is not in explored or frontier then

• frontier ←INSERT(child , frontier )

• else if child .STATE is in frontier with higher PATH-COST then

• replace that frontier node with child

 Uniform cost search (UCS)…
• In addition to the ordering of the queue by path cost, there are two other
significant differences from breadth-first search.
1) The first is that the goal test is applied to a node when it is selected for
expansion rather than when it is first generated. The reason is that the first goal
node that is generated may be on a suboptimal path.
2)The second difference is that a test is added in case a better path is found to a
node currently on the frontier.

• Both of these modifications come into play in the next example where the
problem is to get from Sibiu to Bucharest in the Romania Touring problem.
Uniform cost search (UCS)…
 Uniform cost search (UCS)…

• The successors of Sibiu are Rimnicu Vilcea and Fagaras, with costs 80 and 99, respectively.
• The least-cost node, Rimnicu Vilcea, is expanded next, adding Pitesti with cost 80 + 97=177.
• The least-cost node is now Fagaras, so it is expanded, adding Bucharest with cost 99+211=310.
• Now a goal node has been generated, but uniform-cost search keeps going, choosing Pitesti for
expansion and adding a second path to Bucharest with cost 80+97+101= 278.
• Now the algorithm checks to see if this new path is better than the old one; it is, so the old one is
discarded. Bucharest, now with g-cost 278, is selected for expansion and the solution is returned.
• It is easy to see that uniform-cost search is optimal in general. Uniform-cost search expands nodes in
order of their optimal path cost. (It is because step costs are nonnegative and paths never get shorter
as nodes are added.)
• Hence, the first goal node selected for expansion must be the optimal solution.
 Uniform-cost search
• Expand least-cost unexpanded node
• Implementation:
• fringe = queue ordered by path cost

• Equivalent to breadth-first if step costs all equal

• Complete? Yes, if step cost ≥ ε, where ε is each step to get closer to the goal node
• Time? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε)) where C* is the cost of
the optimal solution
• Space? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε))
• Optimal? Yes – nodes expanded in increasing order of g(n) 104
 Depth-first search( DFS)

• It is a strategy that expands the deepest node in the search tree.

• Here a stack is used.

107
 Depth-first search( DFS)

1. Form a one element stack consisting of the root node.

2. Until the stack is empty or the goal node is found out, repeat the
following:-
1. Remove the first element from the stack. If it is the goal node announce
success, return.

2. If not, add the first element’s children if any, to the top of the stack.

3. If the goal node is not found announce failure.

108
 Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

109
 Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

110
 Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at fron

111
 Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

112
 Depth-first search

• Expand deepest unexpanded node

• Implementation:
• fringe = LIFO queue, i.e., put successors at front

113
 Depth-first search

• Expand deepest unexpanded node

• Implementation:
• fringe = LIFO queue, i.e., put successors at front

114
 Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

115
 Depth-first search

• Expand deepest unexpanded node

• Implementation:
• fringe = LIFO queue, i.e., put successors at front

116
 Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

117
 Depth-first search

• Expand deepest unexpanded node

• Implementation:
• fringe = LIFO queue, i.e., put successors at front

118
 Depth-first search

• Expand deepest unexpanded node

• Implementation:
• fringe = LIFO queue, i.e., put successors at front

119
 Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front

120
 Properties of depth-first search
• Complete? No: fails in infinite-depth spaces, spaces with loops
• We may modify the algorithm to avoid repeated states along the path
DFS is complete in finite spaces.

• Time? The number of nodes generated is of the order of O(bm) . It is terrible if m is much
larger than d

• but if solutions are dense, may be much faster than breadth-first

• Space? It only stores the unexpanded nodes. So it requires 1 +b + b +b ….. m times = O(bm),
i.e., linear space!

• Optimal? No. If it makes a wrong choice, it may go down a very long path and finds a
solution, where as there may be a better solution at a higher level in the tree.
121
 DFS Algorithm

● DFS will continue to visit neighbors in a recursive pattern

● Whenever we visit v from u, we recursively visit all unvisited neighbors of v. Then we
backtrack (return) to u.

● Note: it is possible that w2 was unvisited when we recursively visit w1, but became
visited by the time we return from the recursive call.
u

v w3
w1 w2
 DFS Algorithm

Flag all vertices as not

visited

Flag yourself as visited

For unvisited neighbors,

call RDFS(w) recursively

We can also record the paths using pred[ ].

Example
Adjacency List Visited Table (T/F)
0 0 F -

8 1 F -

2 F -

source 2 3 F -
9
4 F -
1
5 F -

3 7 6 F -

6 7 F -
4
5 8 F -

9 F -

Pred
Initialize visited
table (all False)

Initialize Pred to -1
Example
Adjacency List Visited Table (T/F)
0 0 F -

1 F -
8 2 T -

3 F -
source 2 9 4 F -

1 5 F -

6 F -
3 7
7 F -
6
4 8 F -
5 9 F -

Pred
Mark 2 as visited

RDFS( 2 )
Now visit RDFS(8)
 Example
Adjacency List Visited Table (T/F)
0
0 F -
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 F -

Pred
Mark 8 as visited
Recursive
calls RDFS( 2 )
RDFS(8) mark Pred[8]
2 is already visited, so visit RDFS(0)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 F -

Pred
Mark 0 as visited
Recursive
calls RDFS( 2 )
RDFS(8) Mark Pred[0]
RDFS(0) -> no unvisited neighbors, return
to call RDFS(8)
 Example
Back to 8
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 F -

Pred

Recursive
calls RDFS( 2 )
RDFS(8)
Now visit 9 -> RDFS(9)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 F -

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
Mark 9 as visited
Recursive
calls RDFS( 2 )
RDFS(8) Mark Pred[9]
RDFS(9)
-> visit 1, RDFS(1)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 F -

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
Mark 1 as visited
Recursive
calls RDFS( 2 )
RDFS(8) Mark Pred[1]
RDFS(9)
RDFS(1)
visit RDFS(3)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 F -

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
Mark 3 as visited
Recursive
calls RDFS( 2 )
RDFS(8) Mark Pred[3]
RDFS(9)
RDFS(1)
RDFS(3)
visit RDFS(4)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
RDFS( 2 ) Mark 4 as visited
Recursive RDFS(8)
calls RDFS(9) Mark Pred[4]
RDFS(1)
RDFS(3)
RDFS(4) STOP all of 4’s neighbors have been visited
return back to call RDFS(3)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 F -

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8
Back to 3
Pred
RDFS( 2 )
Recursive RDFS(8)
calls RDFS(9)
RDFS(1)
RDFS(3)
visit 5 -> RDFS(5)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 T 3

3 7 6 F -
6 7 F -
4
5 8 T 2

9 T 8

Pred
RDFS( 2 )
Recursive RDFS(8) Mark 5 as visited
calls RDFS(9)
Mark Pred[5]
RDFS(1)
RDFS(3)
RDFS(5)
3 is already visited, so visit 6 -> RDFS(6)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 T 3

3 7 6 T 5
6 7 F -
4
5 8 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9) Mark 6 as visited
calls
RDFS(1) Mark Pred[6]
RDFS(3)
RDFS(5)
RDFS(6)
visit 7 -> RDFS(7)
 Example
Adjacency List Visited Table (T/F)
0
0 T 8
8 1 T 9

2 T -
source 2 9 3 T 1

1 4 T 3

5 T 3

3 7 6 T 5
6 7 T 6
4
5 8 T 2

9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9) Mark 7 as visited
calls
RDFS(1) Mark Pred[7]
RDFS(3)
RDFS(5)
RDFS(6)
RDFS(7) -> Stop no more unvisited neighbors
 Example
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

7 T 6
6
4 8 T 2
5
9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1)
RDFS(3)
RDFS(5)
RDFS(6) -> Stop
 Example
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

7 T 6
6
4 8 T 2
5
9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1)
RDFS(3)
RDFS(5) -> Stop
 Example
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

7 T 6
6
4 8 T 2
5
9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1)
RDFS(3) -> Stop
 Example
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

7 T 6
6
4 8 T 2
5
9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1) -> Stop
 Example
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

7 T 6
6
4 8 T 2
5
9 T 8

Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9) -> Stop
calls
 Example
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

7 T 6
6
4 8 T 2
5
9 T 8

Pred
RDFS( 2 )
RDFS(8) -> Stop
Recursive
calls
 Example
Adjacency List Visited Table (T/F)
0 0 T 8

1 T 9
8
2 T -

3 T 1
source 2 9 4 T 3
1 5 T 3

3 7 6 T 5

7 T 6
6
4 8 T 2
5
9 T 8

Pred
RDFS( 2 ) -> Stop

Recursive
calls
Example
0 Adjacency List Visited Table (T/F)
8 0 T 8

1 T 9

source 2 2 T -
9
3 T 1
1
4 T 3

3 7 5 T 3

6 6 T 5
4
5 7 T 6

8 T 2

9 T 8

Pred
Check our paths, does DFS find valid paths? Yes.

Try some examples.

Path(0) ->
Path(6) ->
Path(7) ->
 Depth-limited search

• The problem with DFS is that the search can go down an infinite branch and
thus never return. Depth limited search avoids this problem by imposing a
depth limit l which effectively terminates the search at that depth. That is ,
nodes at depth l are treated as if they have no successors.
• The choice of depth parameter l is an important factor. If l is too deep , it is
wasteful in terms of both time and space. But if l < d (the depth at which
solution exists) i,e the shallowest goal is beyond the depth limit, then this
algorithm will never reach a goal state.
147
 Depth-limited search

Depth-first search with depth limit l,

i.e., nodes at depth l have no successors
Recursive implementation:

148
 Properties of depth- limited search

• Complete? No. if l<d, the shallowest goal is beyond the depth limit and if l>d, then
depth-limited search is non-optimal.

• Time? O(b l ).

• Space? O(bl), i.e., linear space.

• Optimal? No.
149
 Iterative deepening search (IDS)
• The problem with depth-limited search is deciding on a suitable
depth parameter, which is not always easy.

• To overcome this problem there is another search called iterative

deepening search. This search method simply tries all possible
depth limits; first 0, then 1, then 2 etc. until a solution is found.
Iterative deepening combines the benefits of DFS and BFS. It may
appear wasteful as it is expanding nodes multiple times. But the
overhead is small in comparison to the growth of an exponential
search tree.

• The IDS is preferred when the search space is large and the depth
of the solution is not known.
150
Iterative deepening search

151
Iterative deepening search l =0

152
Iterative deepening search l =1

153
Iterative deepening search l =2

154
Iterative deepening search l =3

155
 Iterative deepening search

• Number of nodes generated in a breadth first search to depth d with branching

factor b:
NBFS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd

• Number of nodes generated in an iterative deepening search to depth d with

branching factor b:
NIDS = (d+1)b0 + d b^1 + (d-1)b^2 + … + 3bd-2 +2bd-1 + 1bd
as the nodes at the bottom level d are expanded once, the nodes at (d-1) are
expanded twice, those at (d – 3) are expanded three times and so on back to the
root.

156
 Iterative deepening search

• For b = 10, d = 5,
• NBFS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
• NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
• Overhead = (123,456 - 111,111)/111,111 = 11%
we can see that compared to the overall number of expansions , the total is not
substantially increased.

157
 Properties of iterative deepening search

• Complete? Yes , like BFS it is complete when b is finite.

• Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
• Space? O(bd) , like DFS memory requirement is linear.
• Optimal? Yes, if like BFS path cost is a non-decreasing function of
the depth of the node, it is optimal.
In general iterative deepening is the preferred uninformed search
method when there is a large search space and the depth of the
solution is not known. 158
Summary of algorithms

163
Bidirectional Search (BDS)
 BDS (contd…)
•The time complexity of bidirectional search using breadth-first searches in both
directions is O(bd/2). The space complexity is also O(bd/2). This is because search
stops in the midway as soon as any one of the search paths from initial state
(forward search) meets with any one of the search paths from goal state
(backward search).

•For the similar condition, the time complexity of breadth first search from initial
state to goal state is O(bd). The space complexity is also O(bd). It is because
searching proceeds only in one direction i.e. from initial state to goal state (only
forward search).

• The motivation is that bd/2 + bd/2 is much less than bd, or in the figure, the area of
the two small circles is less than the area of one big circle centered on the start
and reaching to the goal.
Comparing Uninformed Search Strategies
 Repeated states
• Failure to detect repeated states can turn a linear problem into an
exponential one!

171
 Repeated states

• In most searching algorithm, the state space generates an

exponentially larger search tree. This occurs mainly because of
repeated nodes. If we can avoid the generation of repeated nodes we
can limit the number of nodes that are created and stop the expansion
of repeated nodes.

172
 Repeated states

• There are three methods having increasing order of computational

overhead to control the generation of repeated nodes:-

173
 Repeated states

1. Don’t generate a node that is the same as the parent node.

2. Don’t create paths with cycles in them. To do this we can check

each ancestor node and refuse to create a state that is the same
as this set of nodes.

3. Don’t generate any state that is the same as any state generated
before. This requires that every state is kept in memory. (space
complexity is O(bd ) )
174
Graph search

175
 Summary

• Problem formulation usually requires abstracting away real-world details to

define a state space that can feasibly be explored

• Variety of uninformed search strategies

• Iterative deepening search uses only linear space and not much more time than
other uninformed algorithms

176
Informed Search Strategy
Informed Search Strategy
(Best-first search)
 Heuristic search techniques
• Blind searches (uninformed searches)are normally
very inefficient. By adding domain knowledge we can
improve the search process.
• The idea behind the heuristic search is that we explore
the node that is most likely to be nearest to a goal
state.
• A heuristic function has some knowledge about the
problem so that it can judge how close the current
state is to the goal state.
• A heuristic function h(n) = estimated cost of the
cheapest path from the state at node n to a goal state.
 Informed Search Strategy
(Heuristic functions)
• The choice of f determines the search strategies.
• Most best first algorithms include as a component of f a heuristic function,
denoted h(n)
• h(n) = estimated cost of the cheapest path from the state at node n to a goal
state.
• h(n) takes a node as input, unlike g(n) in UCS, it depends only on the state
at that node.
• For example, in Romania, one might estimate the cost of the cheapest path
from Arad to Bucharest via the straight-line distance from Arad to
Bucharest.
 Heuristic functions (contd…)

• Heuristic functions are the most common form in which additional knowledge
of the problem is imparted to search algorithm.

• For the present context, we consider these heuristic function to be arbitrary,

nonnegative, problem-specific functions, with one constraint :
If n is a goal state, then h(n) = 0.
 Best-first search
• Idea: use an evaluation function f(n) for each node
• Use this to estimate the degree of "desirability“ for each node.
• Then expand the most desirable unexpanded node.

• Implementation:
Order the nodes in fringe or sequence in decreasing order of desirability.
• Two special cases of Best-first search where h(n) is used as f(n) to guide search:
• Greedy best-first search [only h(n) is used as f(n)]
• A* search [h(n) + g(n) is used as f(n)]
 Greedy best-first search

• It tries to expand the node that is closest to the goal state.

• It follows a single path but switch over to a different path if it
appears to be more promising at any stage.

• A promising node is selected by applying a suitable HF

[Heuristic Function, h(n)]to each competing node.
Data structures used for best-first search
• OPEN
• It is a priority queue of nodes which have been generated
and have had the heuristic function applied to them but
which have not yet been expanded. ( priority is evaluated
by a HF value).

• CLOSED
• It contains nodes that have already been expanded. ( it is
used to ensure that the same node is not expanded more
than once.)
 Greedy best-first search

• Evaluation function f(n) = h(n) (heuristic)

= estimate of cost from n to goal

• e.g., hSLD(n) = straight-line distance from n to Bucharest

• Greedy best-first search expands the node that appears to be closest to goal
 Greedy best-first search algorithm

1. Start with OPEN containing just the initial state.

2. Until a goal is found or there are no nodes left on OPEN do:

a) Pick the best node from OPEN.

b) Generate its successors.

Greedy best-first search algorithm (contd…)

c) For each successor do:

i) If it has not been generated before , evaluate it, add it to OPEN, and
record its parent.
ii) If it has been generated before, change the parent if this new path is
better than the previous one. In that case , update the cost of getting
to this node and to any successors that this node may already have.
Greedy best-first search example: (Romania
example)
Greedy best-first search example (contd…)
Greedy best-first search example (contd…)
Greedy best-first search example (contd…)
 Properties of Greedy best-first search

• Complete? No – can get stuck in loops, e.g., Iasi Neamt Iasi Neamt
….

• Time? O(bm), but a good heuristic can give dramatic improvement

• Space? O(bm) -- keeps all nodes in memory
• Optimal? No
Properties of Greedy best-first search (contd…)
 *
A search

• Idea: avoid expanding paths that are already expensive

• Evaluation function f(n) = g(n) + h(n)
• g(n) = cost so far to reach n
• h(n) = estimated cost from n to goal
• f(n) = estimated total cost of path through n to goal
 *
A search

• The Best first search algorithm is a simplified version of A* algorithm .

• A* uses the same f, g ,h functions as well as the lists OPEN and
CLOSED.
• A* algorithm:-
1) start with OPEN containing only the initial node. Set that node’s g
value to zero , its h value to whatever it is and its f value to h + 0 = h.
initially closed is empty.
 *
A search

2. Until a goal node is found, repeat the procedure:

I. if there are no nodes on OPEN, report failure. Otherwise, pick
the node from OPEN with the lowest f value. Call it
BESTNODE. Remove it from OPEN , place it on CLOSED . If
BESTNODE is a goal node, then exit and report a solution; else
generate the successors of BESTNODE. For each such
successor, do the following:
 *
A search
a) Set SUCCESSOR to point back to BESTNODE.

b) Compute g(SUCCESSOR) = g( BESTNODE) + the cost of

getting from BESTNODE to SUCCESSOR.

c) See if SUCCESSOR is the same as any node on OPEN. If so,

call that node OLD. Since this node already exists in the graph,
we can throw SUCCESSOR away and add OLD to the list of
BESTNODES successors.
 *
A search

determine the parent link:- If the path just found to SUCCESSOR is

cheaper than the current best path to OLD, then reset OLD’s parent – link
to BESTNODE; else, don’t update anything.
d) if SUCCESSOR is not in OPEN but in CLOSED, call it OLD and add OLD
to the list of BESTNODE’s successors. Check to see if the new path is
better as in step (c) . If it is, then set the parent link and g and f value
appropriately. Propagate the new cost downward and determine the better
path. If required set the parent link accordingly.
 *
A search

e) If SUCCESSOR is neither in OPEN nor in CLOSED , then put it on

OPEN and add it to the list of BESTNODE’s successors. Compute
f(SUCCESSOR) = g(SUCCESSOR) + h( SUCCESSOR)
 *
A search example
 *
A search example(Romania example)
 *
A search example
 *
A search example
A* search example
 *
A search example
 Properties of A*

• Complete? Yes (unless there are infinitely many nodes with f ≤ f(G) )
• Time? Exponential
• Space? Keeps all nodes in memory
• Optimal? Yes if h(n) is admissible.
 Admissible heuristics
• A heuristic h(n) is admissible if for every node n,
h(n) ≤ h*(n), where h*(n) is the true cost to reach the
goal state from n.

• An admissible heuristic never overestimates the cost

to reach the goal, i.e., it is optimistic
• Example: hSLD(n) (never overestimates the actual road
distance)
• Theorem: If h(n) is admissible, A* using
TREE-SEARCH is optimal
 Consistent heuristics

• A heuristic is consistent if for every node n, every successor n' of n generated by any action a,
h(n) ≤ c(n,a,n') + h(n')

• If h is consistent, we have

f(n') = g(n') + h(n')

= g(n) + c(n,a,n') + h(n')
≥ g(n) + h(n)
= f(n)

• i.e., f(n) is non-decreasing along any path.

• Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal
Some Example Search Graphs
 Some Example Search Graphs (contd…)
• In this problem the start state is S, and the goal state is G. The transition costs are next to the edges, and the heuristic
estimate, h, of the distance from the state to the goal is in the state’s node. Assume ties are always broken by choosing the
state which comes first alphabetically.
• 1. What is the order of states expanded using Depth First Search? Assume DFS terminates as soon as it reaches the goal
state.
• Answer: S, A, B, D, F ,G
• 2. What is the order of states expanded using Breadth First Search?
• Answer: S, A, B, C, D, E, F, G
• 3. What is the order of states expanded using Best First Search? Assume BFS terminates as soon as it reaches the
• goal state.
• Answer: S, B, D, F, G
• 4. What is the order of states expanded using A* search?
• Answer: S, A, B, D, C, E, F, G
• 5. What is a least cost path from S to G?
• Answer: S, A, C, F, G
 Admissible heuristics

E.g., for the 8-puzzle:

• h1(n) = number of misplaced tiles

• h2(n) = total Manhattan distance

(i.e., no. of squares from desired location of each tile)

• h1(S) = ?
• h2(S) = ?
 Admissible heuristics

E.g., for the 8-puzzle:

• h1(n) = number of misplaced tiles

• h2(n) = total Manhattan distance
(i.e., no. of squares from desired location of each tile)

• h1(S) = ? 8
• h2(S) = ? 3+1+2+2+2+3+3+2 = 18
8-puzzle heuristics: explanation
8-puzzle heuristics: explanation (contd…)