Search Algorithms

In Artificial
Intelligence

Eng/ Maram Hatem

Content of presentation
01 03
Introduction to Search
Algorithms in AI
State Space Search Types of Search Uninformed search
Algorithms algorithms
02

04
Informed search
06 algorithms

Examples 05
State Space Search
 State space search is a fundamental concept in artificial intelligence (AI) and forms the basis for many
problem-solving methods.

 It involves exploring a set of possible states—each representing a different configuration of a

problem—to find a sequence of actions that leads from an initial state to a goal state.

 Core Principles:

1. Initial State – The starting point of the problem where the search begins.
2. Goal State – The desired outcome or solution configuration.
3. Transitions – Actions or operations that move the system from one state to another.
4. Path Cost – The cumulative cost associated with a path between states, often minimized in optimal
solutions.
5. Representation – State spaces can be represented as trees (for non-repetitive structures) or graphs (for
problems with cycles or repeated states).
State Space Search
 How the Process Works:
1. Define the State Space – Identify all possible states and transitions.
2. Choose a Search Strategy – Depending on available knowledge:
a. Uninformed Searches (e.g., Breadth-First Search, Depth-First Search) explore without heuristics.
b. Informed Searches (e.g., A* Algorithm) use heuristics to guide toward the goal.
3. Perform the Search – Start exploring states from the initial state based on the chosen strategy.
4. Expand Nodes – Generate successor states for each explored node.
5. Avoid Repetition – Maintain a list of visited states to prevent redundant work.
6. Terminate the Search – Stop once the goal state is reached or no solutions remain.

 Real-World Examples
1. Puzzle Solving: In problems like the 8-puzzle or Rubik’s Cube, each configuration is a state; moves
represent transitions.
2. Robotics: A robot finding its way through a maze models each location as a state, with movement
actions forming transitions.

 Importance in AI : State space search structures the way AI systems reason and plan. It applies
to path finding, robot navigation, game playing, and automated planning—making it a cornerstone for
intelligent decision-making.
Introduction to Search Algorithms in AI
 An AI search algorithm is a systematic method used to explore a set of potential solutions in order to
find the best answer to a given query or problem. It starts from an initial state representing the current
snapshot of the problem and evaluates possible actions or transitions to reach a goal state, which is
the desired solution. The algorithm navigates through these states by assessing path costs—
resources or effort needed for each step—to prioritize efficient and optimal solutions.

 For example, in a chess AI application, the search algorithm considers all possible moves and their
outcomes to decide the best next move by calculating the optimal tactic. This process involves
systematically examining the state of the game board, predicting results from different actions, and
selecting the move that maximizes the chance of winning.

 AI search algorithms have a broad range of applications, such as problem-solving in computer

science, decision-making in logistics, analyzing Mars rover data at NASA, and enhancing medical
diagnosis and drug discovery. They help process vast data and complex scenarios more quickly and
accurately than manual methods, making them essential for many industries.
Introduction to Search Algorithms in AI
 The main elements of AI search algorithms include:
● States: Represent the condition or situation at a particular point.
● Actions: The possible transitions or moves between states.
● Goals: The target or desired outcome of the search.
● Path Costs: The cost associated with moving between states, used to guide the search for efficiency.

 Search algorithms use these components to construct a search space, typically represented as
a search tree or a search graph:
● Search Tree: A branching structure generated from the initial state without revisiting past states.
● Search Graph: A more efficient structure that accounts for repeated states and shared paths, reducing
redundancy.
 Understanding this structure is key to selecting the right algorithm.

 Search algorithms in artificial intelligence (AI) are evaluated based on four essential properties that
help compare their efficiency and suitability for different problems:
1. Completeness: A search algorithm is complete if it guarantees finding a solution whenever one exists
for any given input. This means it will always return a result if a path to the goal state can be found.
Introduction to Search Algorithms in AI
2. Optimality: An algorithm is optimal if it guarantees the best solution among all possibilities, typically the
one with the lowest path cost. This ensures that the solution provided is the most efficient or least costly.

3. Time Complexity: This measures the amount of time or computational steps the algorithm requires to
complete its task. It is usually expressed in terms of the number of nodes the algorithm generates or
expands during the search.

4. Space Complexity: This represents the maximum memory or storage needed by the algorithm at any
point during the search process. It accounts for the number of states or nodes held in memory as the
algorithm runs.

 These properties guide the selection and design of search algorithms depending on the problem
constraints, such as available resources and the need for guaranteed or optimal solutions.
Introduction to Search Algorithms in AI
 Types of Search Algorithms : Search algorithms
in AI are broadly classified into two main
categories:

1. Uninformed Search (Blind Search): These

algorithms have no additional information about
goal location other than the problem definition.
They explore the search space systematically.
Examples include Breadth-First Search (BFS),
Depth-First Search (DFS), and Uniform Cost
Search.

2. Informed Search (Heuristic Search): These use

heuristic functions to estimate the cost to reach
the goal, allowing more efficient exploration.
Examples include Greedy Best-First Search and
A*.
 Search Algorithms in AI
 Uninformed search algorithms is also known as blind search algorithms, are a class of
search algorithms that do not use any domain-specific knowledge about the problem being
solved.
Uninformed search algorithms rely on the information provided in the problem definition, such as
the initial state, actions available in each state, and the goal state.

 These are called "blind" because they do not have a heuristic function to guide the search
towards the goal instead, they explore the search space systematically.

 Uninformed search algorithms provide basic search strategies for exploring problem spaces
where no additional knowledge is available beyond the problem definition.

 These algorithms are important for solving a wide range of problems in AI, such as path finding,
puzzle solving, and state-space search.
While these algorithms may not always be the most efficient, they provide a baseline for
understanding and solving complex problems in AI.
 Search Algorithms in AI
 Types of Uninformed Search Algorithms:

1. Breadth-First Search (BFS)

Breadth-First Search explores nodes level by level,
starting from the initial state and expanding all
neighboring nodes before moving to the next depth
level. It uses a FIFO (queue) data structure.
BFS is ideal for finding the shortest path in un weighted
graphs and is complete and optimal when all actions
have equal cost. However, it consumes a lot of memory,
especially for large or deep search spaces, making it
less practical for complex problems.
Pros: Guarantees optimal solution, simple to
implement.
Cons: High space complexity, slow on deep trees.
 Search Algorithms in AI
 Types of Uninformed Search Algorithms:

1. Breadth-First Search (BFS)

BFS is a queue (FIFO), which ensures nodes are explored in the order they are
discovered.
 Algorithm:
1. Initialize a queue and a visited list to keep track of visited nodes (First empty list)
2. Start by enqueuing the root node and marking it as visited
3. While the queue is not empty:
a. Dequeue a node n from the front
b. Process node n (e.g., print it, check if it’s the goal)
c. Enqueue all unvisited neighbors (or children in a tree) of node n and mark them as
visited
4. Repeat until all nodes are explored or the goal is found
 Search Algorithms in AI
Example : 1. Using Breadth-First Search (BFS) find path to node (E).
2. Using Breadth-First Search (BFS) find path to node (F).
 Search Algorithms in AI
 Types of Uninformed Search Algorithms:

2. Depth-First Search(DFS)
Depth-First Search DFS explores as deep as possible
along each branch before backtracking. It uses a LIFO
(stack) structure or recursion, making it space-efficient.
DFS is effective in scenarios where solutions are
located deep in the search tree or when exploring all
possible paths. However, it’s neither complete nor
optimal in infinite or cyclic spaces without additional
checks.
Pros: Low memory usage, faster in deep trees
Cons: Can get stuck in loops, doesn’t guarantee
shortest path
 Search Algorithms in AI
 Types of Uninformed Search Algorithms:

2. Depth-First Search(DFS)
DFS use stack (LIFO) to determine the next node to visit, whether explicitly or through
recursion.
Algorithm:
1. Initialize a stack and a visited list (First empty list)
2. Push the root node onto the stack
3. While the stack is not empty:
a. Pop the node from the top
b. If not already visited:
c. Process it (e.g., print or check if it’s the goal)
d. Mark it as visited
e. Push its children onto the stack
4. Repeat until the stack is empty or the goal is found
 Search Algorithms in AI
Example : 1. Using Depth-First Search (DFS) find path to node (E).
2. Using Depth-First Search (DFS) find path to node (F).
 Search Algorithms in AI
 Types of Uninformed Search Algorithms:

3. Uniform Cost Search(UCS)

Uniform Cost Search expands the least-cost node first
using a priority queue. It behaves like BFS when all
costs are equal but outperforms it when costs vary.
UCS is complete and optimal, making it suitable for
path finding problems involving variable edge costs
(e.g., GPS routing). However, like BFS, it can be slow
and memory-intensive for large graphs.
Pros: Always finds the lowest-cost path
Cons: Slow in large spaces, requires cost function and
priority queue.
 Search Algorithms in AI
 Types of Uninformed Search Algorithms:

3. Uniform Cost Search(UCS)

How UCS work :
1. Initialization: UCS starts with the root node. It is added to the priority queue with a cumulative cost
of zero since no steps have been taken yet.
2. Node Expansion: The node with the lowest path cost is removed from the priority queue. This node
is then expanded, and its neighbors are explored.
3. Exploring Neighbors: For each neighbor of the expanded node, the algorithm calculates the total
cost from the start node to the neighbor through the current node. If a neighbor node is not in the
priority queue, it is added to the queue with the calculated cost. If the neighbor is already in the queue
but a lower cost path to this neighbor is found, the cost is updated in the queue.
4. Goal Check: After expanding a node, the algorithm checks if it has reached the goal node. If the
goal is reached, the algorithm returns the total cost to reach this node and the path taken.
5. Repetition: This process repeats until the priority queue is empty or the goal is reached.
 Search Algorithms in AI
Example1 : Given the following graph, using Uniform Cost Search (UCS), determine:
1. The path from the start node to the goal node. [A → G]
2. The total cost of that path.
 Search Algorithms in AI
Example2 : Given the following graph, using Uniform Cost Search (UCS), determine:
1. The path from the start node to the goal node. [S → E]
2. The total cost of that path.
Thanks!
Do you have any questions?