AI Search Algorithms

Introduction to Search in AI
• Search is fundamental to problem-solving in
AI.
• Many AI problems can be modeled as search
problems.
• Examples: Finding a route on a map, Solving
puzzles, Game playing
 Components of a Search Problem
• Initial State
• Goal State
• State Space
• Successor Function
• Path Cost
1. Initial State
• Definition: The starting point or configuration of the problem before any actions have been taken.
• Example: In a puzzle game like the 8-puzzle, the initial state is the starting arrangement of the tiles.
• Purpose: Represents where the search begins.
2. Goal State
• Definition: The desired final state or configuration that the search aims to reach.
• Example: In the 8-puzzle, the goal state is the arrangement where the tiles are in the correct order.
• Purpose: Defines the condition(s) that must be satisfied to consider the problem solved.
State Space
• Definition: The set of all possible states or configurations that can be reached from the initial state by
applying actions.
• Example: For the 8-puzzle, the state space includes every possible arrangement of the tiles.
• Purpose: Represents the entire search domain, where the search algorithm explores to find a path from
the initial to the goal state.
4. Successor Function
• Definition: A function that takes a state as input and returns a set of successor states reachable from the
current state by applying possible actions.
• Example: In a chess game, the successor function generates all legal moves from a given board position.
• Purpose: Defines how the search moves from one state to another and enables the exploration of the
state space.
5. Path Cost
• Definition: A numeric value representing the cost of moving along a path from the initial state to a
particular state.
• Example: In a route-finding problem, path cost could be the total distance traveled or total travel time.
• Purpose: Used to evaluate and compare different paths, helping the algorithm find the least costly or most
efficient route to the goal.
 Types of Search Algorithms
• Uninformed (Blind) Search - No domain-specific knowledge
• Informed (Heuristic) Search - Uses domain knowledge to guide the search

• Search is fundamental in AI for decision-making and problem-

solving.
• Uninformed search is systematic but inefficient.
• Informed search uses heuristics to improve efficiency.
• Choosing the right search algorithm depends on the problem
constraints and available knowledge
Uninformed (Blind) Search
• No additional information about the goal state is used.
• Only the problem definition is known.

Pros:
• Simple to implement.
• Systematic.
Cons:
• Often inefficient.
• Time and space complexity can be high.
 Breadth-First Search (BFS)
• Explores neighbors first before going deeper
• Uses a queue (FIFO)
• Completeness: Yes
• Optimality: Yes (if cost = 1)
• Time/Space: O(b^d)
 Depth-First Search (DFS)
• Explores as far as possible down one branch
• Uses a stack (LIFO)
• Completeness: No
• Optimality: No
• Time: O(b^m)
• Space: O(bm)
Difference between BFS and DFS

Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental algorithms
used for traversing or searching graphs and trees. This article covers the basic difference
between Breadth-First Search and Depth-First Search.
1. BFS
Approach: BFS explores the graph level by level, starting from the source node. It visits all
the nodes at one level before moving to the next. BFS uses a queue to keep track of nodes
that need to be explored.
How it works: From the source node, BFS moves to all its direct neighbors (Layer 1), then
moves to the next layer (Layer 2), continuing until all nodes are visited.
Traversal Order:
•Starting from node 0:
•Layer 0: Visit node 0 (source node).
•Layer 1: Visit nodes 1, 2, 3 (neighbors of node 0).
•Layer 2: Visit nodes 4, 5, 6, 7 (neighbors of nodes 1,
2, 3).
•Output: 0, 1, 2, 3, 4, 5, 6, 7.

2. DFS
Approach: DFS explores as deep as possible along a branch before backtracking. It uses
a stack (or recursion) to keep track of nodes and backtracks when it reaches a dead end.
How it works: Starting from the source node, DFS goes deeper into the graph, visiting one
branch of the graph first before backtracking to explore others.

Traversal Order:
•Starting from node 0:
•Visit node 0 → Visit node 1 → Visit node 4 (deepest)
→ Backtrack to node 1 → Visit node 5 → Backtrack to
node 0 → Visit node 2 → Visit node 6 → Backtrack to
node 2 → Visit node 3 → Visit node 7.
•Output: 0, 1, 4, 5, 2, 6, 3, 7
 Parameters BFS DFS
Stands for BFS stands for Breadth First Search. DFS stands for Depth First Search.

BFS(Breadth First Search) uses Queue data DFS(Depth First Search) uses Stack
Data Structure
structure for finding the shortest path. data structure.

DFS is also a traversal approach in

BFS is a traversal approach in which we which the traverse begins at the root
Definition first walk through all nodes on the same node and proceeds through the nodes
level before moving on to the next level. as far as possible until we reach the
node with no unvisited nearby nodes.

Conceptual DFS builds the tree sub-tree by sub-

BFS builds the tree level by level.
Difference tree.

Approach It works on the concept of FIFO (First In It works on the concept of LIFO (Last
used First Out). In First Out).

BFS is more suitable for searching vertices DFS is more suitable when there are
Suitable for
closer to the given source. solutions away from source.

DFS is used in various applications

BFS is used in various applications such as such as acyclic graphs and finding
bipartite graphs, shortest paths, etc. If strongly connected components etc.
Applications weight of every edge is same, then BFS There are many applications where
gives shortest path from source to every both BFS and DFS can be used like
other vertex. Topological Sorting, Cycle Detection,
etc.
 When to Use: DFS vs BFS?
When to Use DFS:
•Exploring All Paths: DFS is useful when you need to explore all possible paths, such as
in maze solving or finding connected components in a graph.
•Backtracking Problems: DFS is great for problems that involve backtracking, like
solving puzzles, detecting cycles, or performing topological sorting in a graph.
•Memory Efficiency in Deep Graphs: DFS uses less memory on deep but narrow
graphs, as it only needs to store a single branch at a time.
•Tree Traversal: DFS is used for pre-order, in-order, and post-order traversal of trees.

When to Use BFS:

•Shortest Path in Unweighted Graphs: BFS is ideal for finding the shortest path in
unweighted graphs because it explores all nodes at the current level before moving
deeper.
•Level-Order Traversal: BFS is perfect for level-order traversal of trees or graphs,
visiting all nodes at the same depth.
•Shallow/Wide Graphs: BFS works well on shallow but wide graphs, as it explores level
by level and efficiently handles many nodes at a given depth.
•Minimum Moves or Steps: Problems like finding the minimum number of moves (e.g.,
puzzles like Word Ladder) are better solved with BFS.
 Problem Statement: Given an undirected graph, return a vector of all
nodes by traversing the graph using breadth-first search (BFS).

Approach:
Initial Configuration:
• Queue data structure: follows FIFO, and
will always contain the starting.
• Visited array: an array initialized to 0
• In BFS, we start with a “starting” node,
mark it as visited, and push it into the
queue data structure.
• In every iteration, we pop out the node ‘v’
and put it in the solution vector, as we are
traversing this node.
• All the unvisited adjacent nodes from ‘v’
are visited next and are pushed into the
queue. The list of adjacent neighbors of
the node can be accessed from the
adjacency list.
• Repeat steps 2 and 3 until the queue
becomes empty, and this way you can
easily traverse all the nodes in the graph.
 BFS explores the graph level by level, starting
from a chosen root node (vertex A in this case).
Here's how the traversal proceeds:
1.Initialization:
•Enqueue the starting node A into a queue.
•Mark A as visited to avoid revisiting it.
2.Exploration:
•Step 1: Dequeue A from the queue (current
node) and visit it. Then enqueue its
neighbors B and C, and mark them as visited.
•Step 2: Dequeue B and visit it. Then
enqueue its neighbors D and E, marking
them as visited.
•Step 3: Dequeue C and visit it. Then
Final BFS Traversal Order: enqueue its neighbor F, and mark F as
The nodes are visited in the visited.
following order: •Step 4: Dequeue D and visit it. Since D has
A -> B -> C -> D -> E -> F no neighbors, move to the next node.
•Step 5: Dequeue E and visit it.
Similarly, E has no neighbors.
•Step 6: Dequeue F and visit it. F has no
neighbors.
 from collections import deque

def bfs(graph, start_vertex):

Python Code for BFS visited = set()
queue = deque([start_vertex])
visited.add(start_vertex)

while queue:
vertex = queue.popleft()
print(vertex, end=" ")

for neighbor in graph[vertex]:

if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

# Example graph represented as an adjacency list

graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}

bfs(graph, 'A')
 Uniform Cost Search (UCS)
• Expands the node with the lowest path cost
• Uses a priority queue
• Completeness & Optimality: Yes
• Time/Space: O(b^C*/ε)
 Comparison Table (Uninformed)
• BFS - Complete: Yes, Optimal: Yes, Time:
O(b^d), Space: O(b^d)
• DFS - Complete: No, Optimal: No, Time:
O(b^m), Space: O(bm)
• UCS - Complete: Yes, Optimal: Yes,
Time/Space: O(b^C*/ε)
• BFS expanding layer by layer
• DFS going deep
•
• Breadth First Search
• In Breadth First Search(BFS), the root node of
the graph is expanded first, then all the
successor nodes are expanded and then their
successor and so on i.e. the nodes are
expanded level wise starting at root level.
• For Example :
• Depth First Search
• In Depth First Search(DFS), the deepest node is expanded in
the current unexplored node of the search tree. The search
goes into depth until there is no more successor nodes.
• For Example :
Example:
Question. Which solution would DFS find to move from node S to node G if run on the
graph below?

Solution. The equivalent search tree for the

above graph is as follows. As DFS traverses the
tree "deepest node first", it would always pick
the deeper branch until it reaches the solution
(or it runs out of nodes, and goes to the next
branch). The traversal is shown in blue arrows.
Path: S -> A -> B -> C -> G

d = the depth of the search tree = the

number of levels of the search tree.
ni = number of nodes in level i i .

Time complexity: Equivalent to the number of

nodes traversed in DFS. T(n)=1+n2+n3+...
+nd=O(nd) T(n)=1+n2+n3+...+nd=O(nd)

Space complexity: Equivalent to how large can

the fringe get. S(n)=O(n×d) S(n)=O(n×d)

Completeness: DFS is complete if the search

tree is finite, meaning for a given finite search
tree, DFS will come up with a solution if it
exists.
Optimality: DFS is not optimal, meaning the
number of steps in reaching the solution, or the
cost spent in reaching it is high.
Example:
Question. Which solution would BFS find to move
from node S to node G if run on the graph below?
Solution. The equivalent search tree for the
above graph is as follows. As BFS traverses
the tree "shallowest node first", it would
always pick the shallower branch until it
reaches the solution (or it runs out of nodes,
and goes to the next branch). The traversal
is shown in blue arrows.
Path: S -> D -> G
s s = the depth of the shallowest solution.
ni ni = number of nodes in level i i .
Time complexity: Equivalent to the number of nodes
traversed in BFS until the shallowest solution.
T(n)=1+n2+n3+...+ns=O(ns) T(n)=1+n2+n3+...
+ns=O(ns)
Space complexity: Equivalent to how large can the
fringe get. S(n)=O(ns) S(n)=O(ns)
Completeness: BFS is complete, meaning for a given
search tree, BFS will come up with a solution if it
exists.

Optimality: BFS is optimal as long as the costs of all

edges are equal.
UCS is different from BFS and DFS because here the costs come into play.
In other words, traversing via different edges might not have the same cost.
The goal is to find a path where the cumulative sum of costs is the least.

Uniform Cost Search (UCS) Algorithm

• Use Priority Queue
• Sorted increasing order of path cost
• Guaranteed to find optimal solution.
• UCS expands node with least path cost g(n) so far

When all steps 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
Uniform Cost Search (UCS) is a
type of uninformed search that
performs a search based on the
lowest path cost. UCS helps us find
the path from the starting node to the
goal node with the minimum path
cost. Considering the scenario that
we need to move from point A to
point B, which path would you
choose? A->C->B or A->B:

The path cost of going from path A to path B is 5 and the

path cost of path A to C to B is 4 (2+2). As UCS will consider
the least path cost, that is, 4. Hence, A to C to B would be
selected in terms of uniform cost search.
Cost of a node is defined as:
cost(node) = cumulative cost of all nodes from root
cost(root) = 0
Example:
Question. Which solution would UCS find to move from node S to node G if run on the graph
below?
Example:
Question. Which solution would UCS find to move from node S to node G if run
on the graph below?

Solution. The equivalent search tree for the above graph is as follows. The cost of
each node is the cumulative cost of reaching that node from the root. Based on the
UCS strategy, the path with the least cumulative cost is chosen. Note that due to the
many options in the fringe, the algorithm explores most of them so long as their
cost is low, and discards them when a lower-cost path is found; these discarded
traversals are not shown below. The actual traversal is shown in blue.
 Path: S -> A -> B -> G
Cost: 5

Let C = cost of solution.

ε = arcs cost.

Then C/ε= C/ε= effective depth

Time complexity: [Tex]T(n) = O(n^C ^/ ^\

varepsilon) [/Tex], Space complexity:
[Tex]S(n) = O(n^C ^/ ^\varepsilon) [/Tex]

Advantages:
• UCS is complete only if states are finite and there should be no loop
with zero weight.
• UCS is optimal only if there is no negative cost.
Disadvantages:
• Explores options in every "direction".
• No information on goal location.
Solve the following example using Uniform Cost Search
 Informed (Heuristic Search)
• Heuristic: estimate of cost from current state to goal
• Improves efficiency over uninformed methods

Heuristic Function
 A heuristic is a function h(n) that estimates
the cost to reach the goal from node n.
 It must be:
o Admissible: Never overestimates the
true cost.
o Consistent (Monotonic): For all nodes
n and successors n',
h(n) ≤ cost(n, n') + h(n').
. Informed (Heuristic) Search

Uses domain-specific knowledge (heuristics) to guide the search.

Examples:

Algorithm Description
Best-First Search Selects the most promising node based on a heuristic.
Greedy Search Uses heuristic function h(n) to select the next node.
Uses f(n) = g(n) + h(n) (cost + heuristic) to select optimal
A Search*
paths.
Recursive Best-First Search
Memory-efficient version of A*.
(RBFS)
Moves in the direction of increasing value (or decreasing
Hill Climbing
cost).
Simulated Annealing Probabilistic technique to escape local minima.
Informed Search Algorithms
Heuristic Function
Greedy Best First Search
Greedy Best First Search
Greedy Best First Search
Advantages of Greedy Best First Search
A* Search Algorithm
A* Search Algorithm Example
Formula
f(n) = g(n) + h(n)
Make a table: Node, g(n),
h(n),f(n),parent node
Where:
f(n):
The total estimated cost of the path
from the start node to the goal node,
passing through node n. This is the
value used to prioritize which node to
explore next.
g(n):
The actual cost incurred to reach node n
from the start node. This represents the
"past cost."
h(n):
The estimated cost (heuristic) to reach
the goal node from node n. This
represents the "future cost" and must
be an admissible heuristic, meaning it
never overestimates the true cost to the
goal.
A* Search Algorithm Example
 Best-First Search
• Selects node with lowest heuristic value h(n)
• Greedy strategy: picks seemingly best path
• Not always optimal
 A* Search
• Combines path cost and heuristic: f(n) = g(n) +
h(n)
• Optimal if h(n) is admissible (never
overestimates)
• Widely used in GPS, robotics, games
 Example – A* vs. Greedy Search
• Diagram showing pathfinding on a graph
• Highlight different choices made by each
 Heuristics
• Admissible: Never overestimates
• Consistent: h(n) ≤ c(n, n') + h(n')
• Good heuristics reduce search time
dramatically
Search Problem Example: 8-Puzzle
• Initial State: Random arrangement of tiles
• Goal State: Tiles ordered from 1 to 8, blank at
the end
• State Space: All possible tile configurations (9!
states)
• Successor Function: Move blank tile
up/down/left/right
• Path Cost: Number of moves
 BFS Example: 8-Puzzle
• Explores all nodes level by level
• Finds shortest path but uses a lot of memory
• Not practical for deep puzzles (memory
explosion)
 DFS Example: 8-Puzzle
• Follows one path deep before backtracking
• Memory efficient but may get stuck in loops
• Not guaranteed to find shortest solution
 UCS Example: Route Finding
• Start: Arad, Goal: Bucharest
• Path cost = distance
• UCS expands cities based on total path cost
• Guaranteed to find shortest path
 A* Example: Route Finding
• Start: Arad, Goal: Bucharest
• f(n) = g(n) + h(n) where h(n) = straight-line
distance to Bucharest
• A* finds optimal path efficiently if h(n) is
admissible
 Heuristic Example: 8-Puzzle
• h1: Number of misplaced tiles
• h2: Sum of Manhattan distances (more
accurate)
• A* with h2 generally performs better than
with h1
 Summary
• Search is key to AI problem-solving
• Choose the right algorithm based on:
• Problem size and structure, Time and space
constraints, Availability of heuristics
Questions / Discussion