PROBLEM SOLVING BY

SEARCHING
 TABLE OF
CONTENTS
• Problem - solving agents
• Problem types
• Problem formulation
• Example problems
• Basic search algorithms
 Search
Problem STATE SPACE START
A search algorithm
ta ke s a p ro b le m a s
Th e s e t o f a ll
SPACE
a n in p u t a n d
re tu rn s a s o lu tio n in
p o s s ib le s ta te s Th e s e a rc h p ro b le m b e g in s
wh e re th e a g e n t
th e fo rm o f a c tio n c a n b e fo rm s a fro m a s p e c ific s ta rt s ta te ,

s e q u e n c e . It s ta rts s ta te s p a c e o f a re p re s e n tin g th e in itia l

with th e in itia l s e a rc h p ro b le m . c o n d itio n fro m wh ic h th e

a g e n t wh ic h a c ts
. a g e n t c o m m e n c e s its

a s a s ta rtin g p o in t e xp lo ra tio n .

fo r th e a g e n t’s
e xp lo ra tio n
 SEARCHING FOR SOLUTION
• search tree- possible action sequences starting at the initial state

• Nodes- states

• Expanding- the current state

• Generating- a new set of states

• parent node

• Child node

• FRONTIER - The set of all leaf nodes available for expansion at any given point

• Explored- every expanded node

Initial State:
currently in Arad.

Formulate goal:
be in Bucharest

Formulate problem:
states: various cities
actions: drive between cities

Find solution:
sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
•Transition(Sibiu, Go(Fagaras)) → Fagaras
•Transition(Fagaras, Go(Bucharest)) → Bucharest

Well-defined problems and solutions

A problem is defined by four items:
1.initial state e.g., "at Arad“

1.actions e.g., {Go(Sibiu), Go(Timisoara), Go(Zerind)}.

2.goal test {In(Bucharest )}

3.path cost (additive)

4. Transition model- The transition model defines the result of

applying an action to a state. It specifies how the state changes in
response to an action.
 Solution
A sequence of actions leading
from the initial state to a goal
state
 Example: The 8-puzzle

states?
actions?
goal test?
path cost?
THANK YOU!
 Search Strategy
A search strategy is defined by picking the order of node expansion
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 complexity are measured in terms of
b: maximum branching factor of the search tree
d: depth of the least-cost solution
m: maximum depth of the state space (may be ∞)
h

Breadth-first search
• Expand shallowest unexpanded node
• Implementation:
–fringe is a FIFO queue, i.e., new
successors go at end
Search Strategy
 Search Strategy
Complete? Yes (if b is finite)

Time? = O(b )
d

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

Optimal? Yes (if cost = 1 per step)

 Uniform-cost search
• Uniform-cost search is a searching algorithm
used for traversing a weighted tree or graph.
• This algorithm comes into play when a
different cost is available for each edge.
• The primary goal of the uniform-cost search
is to find a path to the goal node which has
the lowest cumulative cost.
• Uniform-cost search expands nodes according
to their path costs form the root node.
• This is implemented using a priority queue
where lower the cost higher is its priority.
 Depth-first search
Expand deepest unexpanded node
Implementation:
In DFS, nodes are pushed onto the stack as they are discovered.
The algorithm then continuously pops the top node from the
stack, explores it, and pushes its unvisited child nodes onto the
stack. This process continues until the stack is empty or the
goal is found.
 Depth-first search
Expand deepest unexpanded node
Implementation:
fringe = LIFO queue, i.e., put successors at front
 Depth-first search
• Completeness
Is DFS complete?
No, DFS is not complete in infinite-depth spaces or spaces with cycles. DFS can get stuck going down an infinite branch and never explore other
branches that might contain the goal.
Yes, DFS is complete in finite spaces, assuming it avoids cycles. If the graph is finite and there are no cycles, DFS will eventually explore all nodes
and find a solution if one exists.

Time Complexity
What is the time complexity of DFS?
The time complexity of DFS is O(b^m), where b is the branching factor (the maximum number of successors of any node), and m is the maximum
depth of the search tree.

Space Complexity
What is the space complexity of DFS?
The space complexity of DFS is O(bm) . This is because, at most, DFS needs to store the deepest path it is exploring, which can be up to m nodes
deep, with each node having up to b children.

Optimality
Is DFS optimal?
No, DFS is not optimal. DFS does not guarantee finding the least-cost solution or the shortest path. It might find a solution, but that solution is not
necessarily the best one.
 Depth-limited search
• The embarrassing failure of depth-first search in
infinite state spaces can be alleviated by supplying
depth-first search with a predetermined depth
limit.

• The depth limit solves the infinite-path problem.

• Depth-Limited Search (DLS) is a variant of

Depth-First Search (DFS) that sets a limit on the
depth to which the search can proceed. This is
particularly useful in scenarios where we want to
avoid getting stuck in deep or infinite paths.
 Depth-limited search

• Completeness: DLS search algorithm is complete if the solution is above the depth-
limit.
• Time Complexity: Time complexity of DLS algorithm is O(bℓ).
• Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
• Optimal: Depth-limited search can be viewed as a special case of DFS, and it is also
not optimal
 Iterative deepening search
• Iterative Deepening Search (IDS) is a search strategy that aims to combine the advantages of both Depth-
First Search (DFS) and Breadth-First Search (BFS). Here are the key points about IDS:
• Gradual Depth Increase: IDS starts with a depth limit of 0 and gradually increases the depth limit until the
goal node is found. It explores all nodes at a given depth limit before increasing the limit.
• Benefits of IDS:
• Memory Efficiency: Similar to DFS, IDS has modest memory requirements of O(bd), where b is the
branching factor and d is the depth of the shallowest goal node. This is because it only keeps track of nodes
at the current depth limit.
• Completeness: IDS is complete if the branching factor bbb is finite. This means it will eventually find a
solution if one exists.
• Optimality: IDS is optimal for finding the shortest path in a tree/graph where the path cost is non-
decreasing with depth. This is because it explores nodes level by level, similar to BFS.
function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or
failure
for depth = 0 to ∞ do result ← DEPTH-LIMITED-SEARCH(problem, depth)
if result = cutoff then return result
 Properties of iterative deepening
search
• Complete? Yes
•
• Time? O(bd)
•
• Space? O(bd)
•
• Optimal? Yes, if step cost = 1
 Bi-Directional search algorithm

• Bidirectional search algorithm runs two simultaneous searches,

one form initial state called as forward-search
• other from goal node called as backward-search, to find the
goal node.
• Bidirectional search replaces one single search graph with two
small subgraphs in which one starts the search from an initial
vertex and other starts from goal vertex.
• The search stops when these two graphs intersect each other.
• Bidirectional search can use search techniques such as BFS, DFS,
DLS, etc.
• Completeness − Bidirectional
search is complete if BFS is used
in both searches.

• Optimality − It is optimal if BFS is

used for search and paths have
uniform cost.

• Time and Space Complexity −

Time and space complexity is
O(b^{d/2})
RESOURCE PAGE