Artificial Intelligence

Dr. Sanga Chaki

Assistant Professor
Department of Computer Science and Engineering
Indian Institute of Information Technology Pune
Problem Solving by Searching –III
Depth-first search (DFS)
Depth-first search (DFS)
1. Depth-first search always expands the deepest node in the current frontier
of the search tree
2. The search proceeds immediately to the deepest level of the search tree,
where the nodes have no successors.
3. As those nodes are expanded, they are dropped from the frontier, so then
the search “backs up” to the next deepest node that still has unexplored
successors
4. To avoid processing a node multiple times, we use a Boolean visited array.
5. It uses a LIFO stack, which means that the most recently generated node is
chosen for expansion.
6. This must be the deepest unexpanded node because it is one deeper than
its parent—which, in turn, was the deepest unexpanded node when it was
selected.
7. Examples discussed in class
Depth-first search (DFS)
Example:
• The progress of Depth-
first search on a binary
tree.
• The unexplored region
is shown in light gray.
• Explored nodes with no
descendants in the
frontier are removed
from memory.
• Nodes at depth 3 have
no successors
• M is the only goal
node.
Depth-first search (DFS)
1. Actual (optimal) Path: ?
2. Traversed Path?
Depth-first search (DFS)
1. How does breadth-first search rate according to the four criteria of search
performance?
i. Completeness: Is the algorithm guaranteed to find a solution when
there is one?
ii. Optimality: Does the strategy find the optimal solution?
iii. Time complexity: How long does it take to find a solution?
iv. Space complexity: How much memory is needed to perform the
search?
Depth-first search (DFS)
1. Is it complete?
a) No, in certain cases
b) In infinite state spaces, it may fail if an infinite non-goal path is
encountered.
c) For example, in Knuth’s 4 problem, depth-first search would keep
applying the factorial operator forever.
Depth-first search (DFS)
1. DFS is nonoptimal
2. See example: depth first search
will explore the entire left
subtree even if node C is a goal
node.
3. If node J were also a goal node,
then depth-first search would
return J as a solution instead of
C. Even though C is a better
solution – path cost wise.
4. hence, depth-first search is not
optimal.
Depth-first search (DFS)
1. Time complexity?
2. How many nodes will it generate? How long will it take to find the solution?
3. The time complexity of depth-first graph search is bounded by the size of
the state space which may be infinite.
4. A depth-first tree search, may generate all of the O(bm) nodes in the search
tree, where m is the maximum depth of any node
5. This can be much greater than the size of the state space.
• As m>>d, so O(bm) >> O(bd) → unnecessarily more time is required
6. Note that m itself can be much larger than d (the depth of the shallowest
solution) and is infinite if the tree is unbounded.
7. So far, no clear advantage of DFS. So why include it? Because of the space
complexity.
Depth-first search (DFS) – Advantage in Space Complexity
1. For a graph search, there is no advantage (similar
to BFS)
2. But a depth-first tree search needs to store only
a single path from the root to a leaf node, along
with the remaining unexpanded sibling nodes
for each node on the path.
3. Once a node has been expanded, it can be
removed from memory as soon as all its
descendants have been fully explored
4. For a state space with branching factor b and
maximum depth m, depth-first search requires
storage of only O(bm) nodes – which is a lot less
than BFS [which is O(bd)]
Disadvantages of DFS
1. Depth First Search is an algorithm that explores a tree or graph by starting
at the root node and exploring as far as possible along each branch before
backtracking.
2. It follows a path from the root to a leaf node, then backtracks to explore
other paths.
3. This method can be inefficient when dealing with large or infinite trees, as
it may explore deep branches that do not contain the goal, leading to
wasted time and resources.
BFS vs DFS
1. Time complexity wise, BFS is better
2. Space complexity wise DFS is better
Depth-limited search (DLS)/Depth
Limited DFS
Depth-limited search (DLS)
1. Depth Limited Search is a modified version of DFS that imposes a limit on
the depth of the search.
2. This means that the algorithm will only explore nodes up to a certain
depth,
3. Effectively preventing it from going down excessively deep paths that are
unlikely to lead to the goal.
4. By setting a maximum depth limit, DLS aims to improve efficiency and
ensure more manageable search times.
5. If we provide DFS with a predetermined depth limit l.
6. That is, nodes at depth l are treated as if they have no successors.
7. This approach is called depth-limited search
Depth-limited search (DLS)

• Start node: A
• Goal node: F
• What happens in DFS?
Depth-limited search (DLS)

• Start node: A
• Goal node: F
• What happens in DFS?
• DFS Sequence:
• A–B–D–G–H–E–I–C–F
• Issue: what if tree has too many
levels?
• Not optimal, high cost
Depth-limited search (DLS)

• Start node: A
• Goal node: F
• What happens in
DLS?
• Let limit depth = 2
• DLS Sequence:
• A–B–D–E–C–
F
Depth-limited search - Steps
1. Initialization: Begin at the root node with a specified depth limit.
2. Exploration: Traverse the tree or graph, exploring each node's children.
3. Depth Check: If the current depth exceeds the set limit, stop exploring that
path and backtrack.
4. Goal Check: If the goal node is found within the depth limit, the search is
successful.
5. Backtracking: If the search reaches the depth limit or a leaf node without
finding the goal, backtrack and explore other branches.
Depth-limited search - Performance
1. Let l = limit, d = depth of goal node.
2. DLS can be incomplete if we choose l < d, that is, the shallowest goal is
beyond the set depth limit.
3. DLS can be nonoptimal if we choose l > d.
4. Its time complexity is O(bl) and its space complexity is O(bl) – same logic as
DFS
5. Depth-first search can be viewed as a special case of depth-limited search
with l = ∞.
Iterative Deepening DFS (IDDFS)
Iterative Deepening DFS (IDS/IDDFS)
1. Iterative deepening search (or iterative deepening depth-first search) is a
general strategy, often used in combination with depth-first tree search,
that finds the best depth limit.
2. It does this by gradually increasing the limit—first 0, then 1, then 2, and so
on—until a goal is found.
3. This will occur when the depth limit reaches d, the depth of the shallowest
goal node
IDDFS – Example 1

• The DFS Traversal:

• A- B- D- H- E- I- C- F- G
• The BFS Traversal:
• A- B- C- D- E- F- G
IDDFS – Example 1

• The IDDFS Traversal:

• Iteration 1: A

• Iteration 2: A – B – C

• Iteration 3: A – B – D – E –
C–F –G
Iterative Deepening DFS (IDS/IDDFS)
1. IDDFS calls DFS/DLS for different depths starting from an initial value.
2. In every call, DFS is restricted from going beyond given depth.
3. So basically, we do DFS in a BFS fashion.
4. IDDFS combines depth-first search’s space-efficiency and breadth-first
search’s fast search (for nodes closer to root).
5. Like DFS, its memory requirements are modest: O(bd)
6. Like BFS, its time complexity is: O(bd)
7. Like breadth-first search, it is complete when the branching factor is finite
8. It is optimal when the path cost is a nondecreasing function of the depth of
the node
9. In general, iterative deepening is the preferred uninformed search method
when the search space is large and the depth of the solution is not known.
IDDFS – Example 2
Four iterations of
iterative deepening
search on a binary tree,
with varying depths.
Bidirectional Search
Bidirectional Search
1. In usual graph search using BFS/DFS we begin our search usually from
source vertex and proceed in one direction - towards the goal vertex.
2. The idea behind bidirectional search is to run two simultaneous searches—
• one forward from the initial state and
• the other backward from the goal,
• hoping that the two searches meet in the middle.
3. Bidirectional search is a graph search algorithm which find smallest path
from source to goal vertex.
Bidirectional Search
1. It runs two simultaneous search –
i. Forward search from source/initial vertex toward goal vertex
ii. Backward search from goal/target vertex toward source vertex
2. Bidirectional search replaces single search graph, which is likely to grow
exponentially, with two smaller sub graphs – one starting from initial
vertex and other starting from goal vertex.
3. The search terminates when two graphs intersect.
Bidirectional Search

1. Suppose we want to find if there exists a path from vertex 0 to vertex 14.
2. Here we can execute two searches, one from vertex 0 and other from
vertex 14.
3. When both forward and backward search meet at vertex 7, we know that
we have found a path from node 0 to 14 and search can be terminated
now.
Bidirectional Search
1. But how do we search backward?
• By defining the concept of predecessors of each node.
• Let the predecessors of a state x be all those states that have x as a
successor.
• Bidirectional search requires a method for computing predecessors and
uses that information for searching backwards.
2. When to use bidirectional approach?
We can consider bidirectional approach when-
a) Both initial and goal states are unique and completely defined.
b) The branching factor is exactly the same in both directions.
Bidirectional Search - Advantage
1. In many cases it is faster
2. It reduces the amount of required exploration.
3. Suppose if branching factor of tree is b and distance of goal vertex from
source is d, then the normal BFS/DFS searching complexity would be O(bd).
4. On the other hand, if we execute two search operation then the
complexity would be O(bd/2) for each search
5. Total complexity would be O(bd/2 + bd/2) which is far less than O(bd).
6. Completeness : Bidirectional search is complete if BFS is used in both
searches.
7. Optimality : It is optimal if BFS is used for search and paths have uniform
cost.
8. Time and Space Complexity : Time and space complexity is O(bd/2).
Comparison of Uninformed Search Strategies

Source: Artificial Intelligence A Modern Approach: Russel et al.

Practice - BFS, DFS, UCS, DLS and IDDFS
Heuristic/Informed Searches in AI
Informed/Heuristic Searches in AI
1. Heuristic search is an AI strategy that uses heuristic functions to make
educated guesses about which paths are most likely to lead to a solution
2. Makes search process more efficient than uninformed (or "blind") search
methods that explore every possibility.
3. It prioritizes promising paths to quickly find good solutions in complex
search spaces
4. Heuristic function or a heuristic:
• A heuristic function provides an estimated cost or value from the current
state to the goal.
• Like a shortcut or a rule of thumb based on domain knowledge.
Heuristics
1. A rule or piece of information used in or enabling problem-solving or
decision-making.
2. These rules are only loosely defined.
3. Heuristic in everyday life:
• Availability heuristic: You might become afraid to fly after seeing extensive
news coverage of a recent plane crash, even though air travel is
statistically very safe.
• Representativeness heuristic: You might assume a person in a suit and tie
is a lawyer, because they fit the stereotype of a lawyer, even if you don't
know them.
• Familiarity heuristic: When buying sneakers, you might choose a pair
you've seen worn by many other people.
Heuristic in AI
1. In mathematical optimization and computer science, heuristic is a
technique designed for problem solving more quickly when classic methods
are too slow
2. Used when classic methods fail to find any exact solution in a search space.
3. In general, solutions are approximate but fast
4. This is achieved by trading optimality, completeness, accuracy, or
precision for speed.
5. In a way, it can be considered a shortcut.
Heuristic in AI
1. A heuristic function h(n), also simply called a heuristic, provides an estimate of
the cost from the current node n to the goal.
2. This estimate is a key component of an evaluation function
f(n) = g(n) + h(n)
Where g(n) = actual cost to reach node n from start node
h(n) = heuristic cost to reach from node n to goal node
3. It is a function that ranks alternatives in search algorithms at each branching
step based on available information to decide which branch to follow.
4. Helps in solving problems in polynomial time – reduced form non-polynomial
time – quick solution
5. Helps in reducing the search space
6. Heuristic functions produce heuristic values – which guide the search/problem
solution – so that unnecessary expansion of nodes are not performed or is
reduced.
Types of Heuristics
1. Distance heuristics: Mostly used in pathfinding problem
• Euclidean Distance method or Euclidean Heuristic
• Manhattan distance method
2. Problem-Specific Heuristics:
• Number of Tiles Out of Place: In the n-puzzle, this counts how many tiles
are not in their final correct position.
• Estimated Time to Completion: In scheduling problems, this could be an
estimate of how long a job will take, which helps prioritize jobs with
shorter estimated completion times.
• Traffic Information: A navigation system can use real-time traffic data as a
heuristic to avoid busy routes.
Euclidean Heuristic
1. Based on Euclidean distance between nodes in a Euclidean space of d-
dimensions
2. If we consider 2d space, the distance between two nodes A(x1, y1) and
B(x2, y2) is measured as:

3. Here, d = h(A,B) = heuristic value derived from heuristic function

4. Next, these values guide how we choose the next node for expansion in
search.
Euclidean Heuristic - Example
1. Starting from S, I can legally
go to A/B/C
A
2. If we want to reach goal G
fastest, the easiest way is to
find the straight-line distance
from each of these options
to G S B G

3. Obviously, B has least

distance
4. So, next we will choose B for
expansion – guided by the
heuristic of Euclidean C

distance
Euclidean Heuristic - Example

A
h(A)
g(A)
• F(A) = g(A) + h(A) = 6 + 10 = 16
• F(B) = g(B) + h(B) = 7 + 4 = 10 S
g(B) B
h(B)
G
• F(C) = g(C) + h(C) = 5 + 13 = 18

h(C)
g(C)

C
Tiles out-of-place Heuristic
1. Example in AI: Consider the 8-puzzle
1 3 2 1 2 3

6 5 4 4 5 6

8 7 7 8

Intermediate State Goal State

2. For each tile, how many steps should the agent move it, to reach the goal
from the start?
3. Manhattan Distance: 0 + 1 + 1 + 2+ 0 + 2 + 2 + 0 + 2 = 10
Tiles out-of-place Heuristic
1. Example in AI: Consider the 8-puzzle
1 2 3
7 8 5 1 3 2 10
4 5 6
3 2 6 5 4
7 8
4 6 1 8 7 2
Goal State
Start State Intermediate State 1

1 2 3

4 6 5
5 3 2
7 8
Some State 8 1 4
Intermediate State 2

Intermediate State 3 6 7
14
Tiles out-of-place Heuristic
1. Example in AI: Consider the 8-puzzle
1 2 3
7 8 5 1 3 2 10
4 5 6
3 2 6 5 4
7 8
4 6 1 8 7 2

Start State Goal State

Intermediate State 1

1 2 3

4 6 5
5 3 2
7 8
Some State 8 1 4
Intermediate State 2

Intermediate State 3 6 7
14
Tiles out-of-place Heuristic
1. Example in AI: Consider the 8-puzzle
1 3 2 1 2 3

6 5 4 4 5 6

8 7 7 8

Start State Goal State

2. Count the number of misplaced tiles

3. Heuristic: = 5
4. Now, follow that path in the search tree which is having least number of
misplaced tiles towards Goal state
Informed/Heuristic Search
Strategies
Informed Search Strategies
1. Informed search - Uses problem-specific knowledge beyond the definition
of the problem itself
2. The general approach we consider is called best-first search.
3. A node is selected for expansion based on an evaluation function, f(n).
4. The evaluation function [f(n)] is construed as a cost estimate
5. So, the node with the lowest evaluation (best node) is expanded first.
6. The choice of f determines the search strategy.
7. In uninformed search strategies, when we are at a node, we can consider
any of the adjacent nodes as the next node to be expanded - blindly
explore nodes without considering any cost function.
8. The idea of Informed search is to use an evaluation function/heuristic to
decide which adjacent node is most promising
9. And then choose that node for further exploration.
Informed Search Strategies
1. Most of the best-first algorithms include as a component of f a heuristic
function, denoted h(n): estimated cost of the cheapest path from the state
at node n to a goal state.
2. Heuristic functions are the most common form in which additional
knowledge of the problem is imparted to the search algorithm.
3. For now, we consider heuristic functions to be arbitrary, nonnegative,
problem-specific functions, with one constraint: if n is a goal node, then
h(n)=0.
Greedy Best First Search
Greedy Best First Search
1. Greedy best-first search tries to expand the node that is closest to the goal,
on the grounds that this is likely to lead to a solution quickly.
2. Thus, it evaluates nodes by using just the heuristic function; that is,
f(n) = h(n)
Greedy Best First Search – Example 1
1. What is given?
2. Heuristic = Euclidean distance between each node and the goal node

Node-Goal Distance in st line

A-G 40
B-G 32
C-G 25
D-G 35
E-G 19
F-G 17
H-G 10
G-G 0
Greedy Best First Search – Example 1 Node-Goal Distance in st line
A-G 40
B-G 32
C-G 25
D-G 35
OPEN LIST CLOSED LIST E-G 19
Node H(n) Node Parent F-G 17
A 40 H-G 10
G-G 0
Greedy Best First Search – Example 1 Node-Goal Distance in st line
A-G 40
OPEN LIST CLOSED LIST B-G 32
Node H(n) Node Parent C-G 25
B 32 A - D-G 35
C 25 E-G 19
D 35 F-G 17
H-G 10
Rearrange according to heuristic values G-G 0

OPEN LIST CLOSED LIST

Node H(n) Node Parent
C 25 A -
B 32
D 35
Greedy Best First Search – Example 1 Node-Goal Distance in st line
A-G 40
B-G 32
C-G 25
D-G 35
OPEN LIST CLOSED LIST
E-G 19
Node H(n) Node Parent
F 17 A - F-G 17
E 19 C A H-G 10
B 32 G-G 0
D 35
Greedy Best First Search – Example 1 Node-Goal Distance in st line
A-G 40
B-G 32
C-G 25
D-G 35
OPEN LIST CLOSED LIST
E-G 19
Node H(n) Node Parent
G 0 A - F-G 17
E 19 C A H-G 10
B 32 F C G-G 0
D 35 G F

1. Using the closed list, backtrack to get

the required path from start to goal
node using Best First Search
2. Path: A – C – F – G
Greedy Best First Search – Advantage
1. Simple and easy to implement
2. Fast and efficient
3. Having low memory requirements.
Greedy Best First Search – Example 2
Greedy Best First Search
1. It can be non-optimal
2. It can be incomplete
3. The worst-case time and space complexity for the tree version is O(bm),
where m is the maximum depth of the search space.
4. With a good heuristic function, however, the complexity can be reduced
substantially.
5. The amount of the reduction depends on the particular problem and on
the quality of the heuristic.
Greedy Best First Search – Practice
1. Start at S
2. Goal is I
A* Search
A* Search
1. Most important informed search strategies
2. Used to find optimal path from initial state to goal state
3. A* search algorithm uses the following function to evaluate nodes for
further exploration at each step of search until goal node is reached.
f(n) = g(n) + h(n)
• g(n) = actual cost from initial state to the state at current node n
• h(n) = estimated cost from the state at node n to a goal state which is given
by the heuristic
A* Search Algorithm Steps
1. Initialization: Start by adding the initial node to the open set with its f(n).
2. Loop: While the open set is not empty, the node with the lowest f(n) value
is removed from the queue.
3. Goal Check: If this node is the goal, the algorithm terminates and returns
the discovered path.
4. Node Expansion: Otherwise, expand the node (find all its neighbors),
calculating g, h, and f values for each neighbor. Add each neighbor to the
open set if it's not already present, or if a better path to this neighbor is
found.
5. Repeat: The loop repeats until the goal is reached or if there are no more
nodes in the open set, indicating no available path.
A* Search – Example 1

1. Detailed working explained in class

with multiple examples – please follow
class notes

1. Select a node for

expansion and then
check if it is a goal node.
2. Path: A – B – D – F – G
A* Search – Example 3
Heuristic Function in A* Algorithm
1. The effectiveness of the A* algorithm largely depends on the heuristic
used.
2. The choice of heuristic can dramatically affect the performance and
efficiency of the algorithm.
3. A good heuristic is one that helps the algorithm find the shortest path by
exploring the least number of nodes possible.
4. The two properties of a good heuristic include:
a) Admissibility
b) Consistency (or Monotonicity)
Properties of Heuristic Function in A* Algorithm
1. Admissibility:
• A heuristic is admissible if it never
overestimates the cost of reaching the
goal.
• Its main purpose is to ensure that the
algorithm finds an optimal solution,
meaning the cheapest or shortest path
• The classic example of an admissible
heuristic is the straight-line distance in a
spatial map.
• Straight-line distance is admissible because
the shortest path between any two points
is a straight line, so the straight line cannot
be an overestimate
Properties of Heuristic Function in A* Algorithm
1. Consistency (or Monotonicity):
• A heuristic function is said to be consistent, or monotone, if for every
node N and each successor P of N, the estimated cost of reaching the goal
from N is no greater than the step cost of getting to P plus the estimated
cost of reaching the goal from P. That is:
Properties of Heuristic Function in A* Algorithm
1. In the A* search algorithm, using a consistent heuristic means that once a
node is expanded, the cost by which it was reached is the lowest possible
2. A consistent heuristic is also admissible, i.e. it never overestimates the cost
of reaching the goal (the converse, however, is not always true)
3. Why do you think these two are necessary properties for A* search
heuristics?
Thank You