05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

Search algorithms are fundamental techniques in Artificial Intelligence (AI) used to explore a
problem space to find a solution. These algorithms are critical in areas such as problem-solving,
game-playing, pathfinding, and optimization. Search algorithms work by systematically exploring
possible solutions to a problem and selecting the most optimal one based on a predefined set of
criteria.

Search algorithms form the backbone of AI problem-solving, enabling systems to find solutions
to complex problems, whether it's pathfinding in a map, solving a puzzle, or optimizing a process.
Uninformed search algorithms are useful for simple or unstructured problems, while informed
search algorithms (such as A*) are more efficient and suited for problems where domain
knowledge can guide the search effectively. Each search algorithm has its strengths and
weaknesses, and the choice of algorithm depends on the problem's nature, complexity, and
computational constraints.

 Basic Problem-Solving Methods in AI

In AI, problem-solving refers to the process of finding solutions to complex tasks or goals by
breaking down a problem into manageable steps or actions. Problem-solving methods are typically
divided into two categories: problem formulation and search algorithms. These methods are
essential for developing intelligent agents capable of reasoning and decision-making.

Problem-solving in AI is a structured process that often involves searching through a state space
to find a solution. By representing problems as state spaces, AI systems can apply various search
algorithms (uninformed or informed) to explore possible solutions. The search algorithm used
depends on factors such as the problem's structure, the size of the state space, and the
computational resources available. State space search is central to AI problem-solving techniques
and underpins many AI applications, from game-playing to robotics and optimization problems.

One of the most common ways to model and solve a problem is through state space search.
Below are the basic methods used for problem-solving in AI, including an introduction to state
space search:

1. Problem Formulation

 Problem formulation is the process of transforming a real-world problem into a formal

problem that can be solved by an AI system. This involves:
o Initial state: The starting point of the problem.
o Goal state: The desired outcome or solution.
o Actions: The possible moves or operations that can be performed to transition
from one state to another.
o Transition model: A description of how actions change the state.

Page 1 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

o Path cost: The cost of performing a series of actions (if applicable, often used in
optimization problems).
o Solution: A sequence of actions that lead from the initial state to the goal state.

In AI, the goal is to find a sequence of actions that transitions from the initial state to the goal
state.

2. State Space Representation

In AI, state space is the set of all possible states that can be reached through a series of actions
from the initial state. The state space represents the problem in a structured way that allows the
agent to explore it systematically.

 State Space: A graph where:

o Each node represents a state (a particular configuration of the problem).
o Each edge represents an action that transitions the agent from one state to another.

State space search explores the space of possible states to find a solution. The search algorithm
aims to find a path from the initial state to the goal state.

3. State Space Search Methods

State space search methods are used to explore the space of possible states and find solutions to
the problem. These methods can be categorized into uninformed (blind) search and informed
(heuristic) search.

Uninformed (Blind) Search Methods

These algorithms explore the state space systematically without using additional domain
knowledge, only relying on the structure of the problem itself.

a. Breadth-First Search (BFS) : BFS explores all nodes at the present depth level before moving on
to nodes at the next level. It is guaranteed to find the shortest path in an unweighted state space.

 Key Features:
o Explores the search space level by level.
o Optimal solution if all actions have equal cost.
o Can be memory-intensive due to storing all nodes at each level.

b. Depth-First Search (DFS) :

DFS explores as far down a branch as possible before backtracking. It
uses a stack for storing nodes.

Page 2 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

 Key Features:
o Can get stuck in infinite loops in cyclic graphs if not properly handled.
o Can be more memory-efficient than BFS.
o Not guaranteed to find the optimal solution.

c. Uniform Cost Search (UCS) : UCSis an extension of BFS that explores nodes based on the least
cost, expanding the least-cost node first.

 Key Features:
o Guarantees the least-cost path.
o Requires a priority queue to manage nodes based on cost.
o More efficient for weighted problems compared to BFS.

Informed (Heuristic) Search Methods

Informed search methods use additional knowledge (heuristics) about the problem to guide the
search more efficiently toward the goal.

a. A (A-Star) Search* : A*
combines the cost to reach a node (g(n)) and the estimated cost to reach
the goal from that node (h(n)) to prioritize exploration.

 Key Features:
o Guaranteed to find the optimal solution if the heuristic is admissible (i.e., it
doesn't overestimate the cost).
o Efficient for pathfinding in problems like navigation and game AI.

b. Greedy Best-First Search : Greedy best-first search uses only the heuristic function to guide the
search toward the goal.

 Key Features:
o May be faster than A* but is not guaranteed to find the optimal solution.
o Often used when an optimal solution is not necessary.

4. Problem-Solving Methods in AI (Broad Techniques)

Problem-solving in AI is not limited to the search algorithm. Other common methods for solving
problems include:

a. Divide and Conquer

 Description: This method breaks a problem into smaller sub-problems, solves each sub-
problem, and combines the results to form a solution.

Page 3 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

 Example: Merge sort and quicksort algorithms are examples of divide and conquer
techniques.

b. Dynamic Programming

 Description: Dynamic programming is used to solve problems by breaking them down

into simpler overlapping subproblems and solving each subproblem only once, saving its
solution for future use.
 Example: Fibonacci sequence calculation, shortest path algorithms (e.g., Bellman-Ford).

c. Backtracking

 Description: Backtracking is used for solving constraint satisfaction problems (CSPs). It

systematically searches through possible solutions and backtracks when it encounters an
invalid solution.
 Example: Solving puzzles like Sudoku, 8-Queens problem.

d. Constraint Satisfaction Problems (CSPs)

 Description: CSPs are a class of problems where the solution must satisfy a set of
constraints. Techniques for solving CSPs include backtracking, constraint propagation,
and heuristics.
 Example: Map coloring, scheduling problems.

5. Example of State Space Search in Problem Solving

Let's consider a simple missionary and cannibal problem where three missionaries and three
cannibals need to cross a river using a boat that can carry at most two people at a time. The state
space represents the configurations of missionaries and cannibals on both sides of the river.

 Initial state: (3 missionaries, 3 cannibals, on the left side)

 Goal state: (0 missionaries, 0 cannibals, on the right side)
 Actions: Move a missionary or a cannibal, or both, to the other side.

The state space would include various configurations such as:

 (3, 3, left) → Initial state

 (2, 2, left) → Move one missionary and one cannibal
 (2, 3, left) → Move two cannibals

The goal is to use search methods (e.g., BFS, DFS, or A*) to explore the state space and find a
sequence of moves to get from the initial state to the goal state.

Page 4 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

 Defining Problems as a State Space Search in AI

In Artificial Intelligence (AI), defining a problem as a state space search is a critical technique
for problem-solving. It involves representing the problem as a collection of possible states and
finding a sequence of actions that lead to a goal state. The idea is to search through the state space,
which consists of all the states that can be reached from the initial state by applying a series of
actions. Defining a problem as a state space search provides a structured way to represent and
explore a problem's solution space. By modeling problems in terms of states, actions, and
transitions, AI systems can search for a path to the goal using various search algorithms. Whether
it's navigating a maze, solving a puzzle, or optimizing a solution, state space search methods are
foundational to AI problem-solving.

Key Concepts in State Space Search

To define a problem as a state space search, we need to identify several key components:

1. State Space:
o The state space represents all possible configurations or states of the problem.
o Each state can be considered a node in a graph.
o The edges between nodes represent the actions that transition from one state to
another.
2. Initial State:
o The starting configuration or state from where the search begins.
o This is where the agent begins the problem-solving process.
3. Goal State:
o The desired configuration or the solution.
o The search aims to reach this state from the initial state by applying a series of
actions.
4. Actions:
o These are the operations or moves that can be made to transition from one state to
another.
o Each action can be considered as an edge between two nodes (states) in the state
space.
5. Transition Model:
o Defines how actions lead to transitions between states.
o It is often represented by a set of rules or functions that describe how each action
changes the current state.
6. Path Cost (Optional):
o In some problems, actions have a cost associated with them.
o The total cost of a path is the sum of the costs of the individual actions taken to
reach the goal state.
o The search algorithm might aim to minimize this cost (e.g., in shortest path
problems).
7. Solution:
o A sequence of actions that leads from the initial state to the goal state.

Page 5 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

o The search algorithm’s objective is to find such a solution.

Steps in Defining a Problem as a State Space Search

1. Identify the Components of the Problem:

o Initial state: Where does the problem start?
o Goal state: What does the solution look like?
o Actions: What operations can change the state?
o Transition model: How do actions change the state?
o Path cost: Does the cost of actions matter (if yes, how to calculate)?
2. Construct the State Space:
o The state space is a graph of nodes, where each node represents a possible state of
the system.
o The edges between nodes represent the actions that transition from one state to
another.
3. Choose a Search Algorithm:
o Depending on the problem, different search algorithms can be used to explore the
state space. Common algorithms include:
 Breadth-First Search (BFS)
 Depth-First Search (DFS)
 A Search*
 Uniform Cost Search (UCS)
 Greedy Best-First Search
4. Search for a Solution:
o The search algorithm explores the state space, evaluating states and actions until it
finds a sequence of actions that leads to the goal state.
o If the problem is large or complex, heuristics may be used to make the search
more efficient.

Example of Defining a Problem as a State Space Search

Problem: Missionaries and Cannibals

Consider the classic Missionaries and Cannibals problem:

 Problem Statement: Three missionaries and three cannibals need to cross a river using a
boat. The boat can carry at most two people at a time. At no point can there be more
cannibals than missionaries on either side of the river, or the cannibals will eat the
missionaries.

Page 6 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

Defining the State Space:

1. State Representation:
o A state can be represented as a tuple: (M, C, B), where:
 M represents the number of missionaries on the left side of the river.
 C represents the number of cannibals on the left side of the river.
 B represents the position of the boat (L for left and R for right).
o Example: (3, 3, L) represents 3 missionaries, 3 cannibals, and the boat on the
left side of the river.
2. Initial State:
o The initial state is (3, 3, L), where all the missionaries and cannibals are on the
left side of the river.
3. Goal State:
o The goal state is (0, 0, R), where all the missionaries and cannibals have
successfully crossed to the right side of the river.
4. Actions:
o The actions are the possible boat crossings, which can involve:
 Moving one missionary (M → M-1, C → C).
 Moving one cannibal (M → M, C → C-1).
 Moving two missionaries (M → M-2, C → C).
 Moving two cannibals (M → M, C → C-2).
 Moving one missionary and one cannibal (M → M-1, C → C-1).
o The transition model will depend on whether the boat is on the left or right side,
and each action should maintain the constraint that at no point can there be more
cannibals than missionaries on either side of the river.
5. Transition Model:
o If the boat is on the left side (L), the state changes according to the selected
action, and the boat moves to the right side (R).
o If the boat is on the right side (R), the same transition occurs, but the boat moves
to the left side (L).
6. Path Cost:
o If path cost is considered, the cost can be defined as the number of crossings made
by the boat (for example, each crossing could have a cost of 1).

State Space Example:

1. Initial State: (3, 3, L)

2. Goal State: (0, 0, R)
3. Possible Actions (State Transitions):
o Move 1 missionary: (3, 3, L) → (2, 3, R)
o Move 1 cannibal: (3, 3, L) → (3, 2, R)
o Move 2 missionaries: (3, 3, L) → (1, 3, R)

Page 7 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

o Move 2 cannibals: (3, 3, L) → (3, 1, R)

o Move 1 missionary and 1 cannibal: (3, 3, L) → (2, 2, R)

Page 8 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

 Exhaustive Search Methods

Exhaustive search methods in AI are those that explore all possible states or configurations in the
problem space to find a solution. These methods are often used when the state space is small or
when a guaranteed solution is needed. Below are some key exhaustive search algorithms:

1. Breadth-First Search (BFS) : BFS is an uninformed (blind) search algorithm that explores
all the nodes at the present depth level before moving on to nodes at the next level. It is a
complete and optimal algorithm when the path cost is the same for all actions.

 How It Works:
1. Start from the root node (initial state).
2. Explore all adjacent nodes (child nodes).
3. Move to the next level of nodes and repeat until the goal state is found.
 Key Features:
o Completeness: BFS is complete, meaning it will always find a solution if one
exists.
o Optimality: If all actions have the same cost, BFS will find the shortest path.
o Time Complexity: O(bd), where b is the branching factor and d is the depth of the
solution.
o Space Complexity: O(bd), as it stores all nodes at the current depth.
 Example: Finding the shortest path in an unweighted graph.

2. Depth-First Search (DFS) : DFS is an uninformed search algorithm that explores as deep as
possible along a branch before backtracking. It uses a stack (or recursion) to manage the nodes.

 How It Works:
1. Start from the root node.
2. Explore a child node, then its children, recursively.
3. Backtrack if a goal is not found or a node has no unexplored children.
4. Repeat the process for other unexplored branches.
 Key Features:
o Completeness: DFS is not guaranteed to find a solution if there are infinite
branches or loops.
o Optimality: DFS does not guarantee an optimal solution.
o Time Complexity: O(bm), where mm is the maximum depth of the tree and bb is
the branching factor.
o Space Complexity: O(bm), as it needs to store the current path.
 Example: Traversing a tree or solving puzzles (e.g., 8-puzzle).

Page 9 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

3. Uniform Cost Search (UCS) : Uniform Cost Search (UCS) is a search algorithm used in
Artificial Intelligence (AI) and graph theory to find the optimal path from a start node to a goal
node. It is a type of uninformed search algorithm that expands the least-cost node first.

 Key Features of UCS:

o Cost-Based Expansion: Unlike Breadth-First Search (BFS), UCS considers the
cost of reaching a node rather than the number of edges.
o Uses a Priority Queue: Nodes are expanded based on the lowest path cost,
stored in a priority queue.
o Guaranteed Optimality: If all costs are positive, UCS finds the least-cost
solution.
o Complete Algorithm: It will always find a solution if one exists.
o Time Complexity: O(bC), where b is the branching factor and C is the cost of the
optimal solution.
o Space Complexity: O(bC), since it keeps all nodes in memory.
 Algorithm Steps:

1. Initialize: Add the start node to a priority queue (min-heap) with a cost of 0.
2. Expand the Lowest-Cost Node: Remove the node with the lowest path cost from the
queue.
3. Check Goal State: If the node is the goal, return the path and cost.
4. Generate Successors: Expand the node’s neighbors and update costs.
5. Update the Priority Queue: If a new path to a node is cheaper, update it in the queue.
6. Repeat Until Goal is Reached.

 Example of UCS:

Consider a graph where:

 A → B (cost = 1)
 A → C (cost = 4)
 B → D (cost = 2)
 C → D (cost = 1)

If we run UCS from A to D, it will first expand B (cost = 1), then D (cost = 1+2 = 3), giving the
optimal path A → B → D.

4. Bidirectional Search : Bidirectional search is a search algorithm that simultaneously searches

from both the initial state and the goal state. The two searches meet in the middle, reducing the
overall search time.

 How It Works:
1. Perform BFS from the initial state and goal state simultaneously.
2. Stop when the two searches meet at a common state.
3. Combine the two search paths to form the solution.

Page 10 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

 Key Features:
o Completeness: It is complete if both searches are guaranteed to meet.
o Optimality: If both searches are BFS, the solution will be optimal.
o Time Complexity: O(bd/2), reducing the time complexity by half compared to a
single BFS.
o Space Complexity: O(bd/2), similar to the time complexity.
 Example: Finding the shortest path between two nodes in a graph.

Heuristic Search Methods

Heuristic search methods use domain-specific knowledge (heuristics) to guide the search process
more efficiently, aiming to find a solution more quickly than exhaustive search methods. These
are often used when the search space is large or when an optimal solution is not strictly required.

1. Hill Climbing : Hill climbing is a local search algorithm that continuously moves towards the
direction of the steepest ascent (or descent) to find a solution. It is a greedy algorithm and
focuses on improving the current state.

 How It Works:

1. Start at the initial state.

2. Evaluate all possible neighboring states.
3. Move to the neighbor with the best evaluation (steepest climb).
4. Repeat until a goal state is reached or a stopping condition is met.
 Key Features:
o Completeness: Hill climbing can get stuck in local optima and is not guaranteed
to find the global optimum.
o Optimality: It may not find the optimal solution.
o Time Complexity: O(bd), where bb is the branching factor and d is the depth of
the goal.
o Space Complexity: O(b), as it only needs to store the current state.
 Example: Solving optimization problems like the traveling salesman problem (TSP) or
function maximization.

2. Best-First Search : Best-First Search is a heuristic search algorithm that selects the most
promising node based on a heuristic function (often denoted as h(n)), which estimates the cost to
reach the goal from node n. It is often implemented using a priority queue.

 How It Works:
1. Start from the initial state.
2. Evaluate the heuristic value for each neighboring state.

Page 11 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

3. Move to the state with the best heuristic value.

4. Repeat until the goal state is reached.
 Key Features:
o Completeness: Not guaranteed to find a solution if the heuristic is not well-
designed.
o Optimality: Not guaranteed to find the optimal solution.
o Time Complexity: Depends on the heuristic and search space.
o Space Complexity: O(bd), as it stores the entire search tree.
 Example: Pathfinding algorithms like A* use best-first search.

3. A * Search Algorithm : A* is an informed search algorithm that combines the best features of
BFS and Best-First Search. It uses both the cost to reach a node g(n) and an estimated cost to
reach the goal h(n), where the evaluation function is f(n)= g(n) + h(n). It is one of the most
efficient search algorithms, often used in pathfinding and graph traversal.

 How It Works:
1. Start from the initial state.
2. Maintain a priority queue of nodes, sorted by f(n) = g(n) + h(n), where:
 g(n): The cost to reach the current node.
 h(n): The estimated cost to reach the goal (heuristic).
3. Pop the node with the lowest f(n) from the queue and explore its neighbors.
4. Continue until the goal state is reached.
 Key Features:
o Completeness: A* is complete and will always find a solution if one exists.
o Optimality: A* is optimal if the heuristic function is admissible (it never
overestimates the true cost).
o Time Complexity: O(bd), but much more efficient than BFS due to the heuristic.
o Space Complexity: O(bd), as it stores all generated nodes.
 Example: Pathfinding in games, robotics navigation, and GPS route planning.

4. Greedy Search Algorithm: The Greedy Search algorithm is one of the strategies like Divide
and conquer used to solve the problems. This method is used for solving optimization problems.
An optimization problem is a problem that demands either maximum or minimum results. Let's
understand through some terms.
The Greedy Search algorithm is the simplest and straightforward approach. It is not an algorithm,
but it is a technique. The main function of this approach is that the decision is taken on the basis
of the currently available information. Whatever the current information is present, the decision is
made without worrying about the effect of the current decision in future.
This technique is basically used to determine the feasible solution that may or may not be optimal.
The feasible solution is a subset that satisfies the given criteria. The optimal solution is the solution
which is the best and the most favorable solution in the subset. In the case of feasible, if more than

Page 12 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

one solution satisfies the given criteria then those solutions will be considered as the feasible,
whereas the optimal solution is the best solution among all the solutions.

 How Greedy Algorithms Work

1. Initialize: Start from an initial state.
2. Select the Best Choice: Pick the option that looks best at the moment.
3. Make an Irreversible Decision: Once a choice is made, it is not reconsidered.
4. Repeat Until Goal: Continue this process until reaching the goal state.

 Characteristics of Greedy Algorithms

o Local Optimization: Makes the best local choice at each step.
o Fast Execution: Generally faster than exhaustive search algorithms.
o Not Always Optimal: May not guarantee the best global solution.
o Works Best with Optimal Substructure & Greedy Choice Property:
a. Optimal Substructure → A problem can be solved optimally by solving its
subproblems.
b. Greedy Choice Property → A local optimal choice leads to a globally optimal
solution.

o Time Complexity: O(n) or O(n log n), depending on specific problem and how data is
stored.
o Space Complexity: O(n), it only needs to store small amount of information proportional
to the input size.

 When to Use a Greedy Algorithm in AI?

o When a quick solution is needed.
o When the problem has optimal substructure.
o When approximate solutions are acceptable.
o Avoid when backtracking or global optimization is needed.

Page 13 of 14
 05010102AM01 : AI & ML -II

UNIT 2: Search Algorithms in AI

 Summary of Exhaustive and Heuristic Search Algorithms

Complete Space
Algorithm Type Optimality Time Complexity
ness Complexity
Yes (if equal
BFS Exhaustive Yes O(bd) O(bd)
cost)
DFS Exhaustive No No O(bm) O(bm)
UCS Exhaustive Yes Yes O(bC) O(bC)
Bidirectional
Exhaustive Yes Yes(if BFS) O(bd/2) O(bd/2)
Search
Hill Climbing Heuristic No No O(bd) O(b)
Best-First Depends on
Heuristic No No O(bd)
Search heuristic
Yes (if admissible
A Search* Heuristic Yes O(bd) O(bd)
heuristic)
Greedy Search Heuristic No No O(n) or O(n log n) O(n)

Each search method has its advantages and drawbacks, and the choice of algorithm depends on
the specific characteristics of the problem at hand (e.g., size of the state space, presence of
optimal solutions, and available heuristic functions).

Page 14 of 14