Artificial Intelligence
Module 2
Artificial Intelligence Module 2
BCS545B
Syllabus
• Solving Problems by Searching
– Artificial Intelligence: Start Russell, Peter Norvig
Chapter 3 (3.1, 3.2, 3.3, 3.4)
Artificial Intelligence Module 2
BCS545B
Solving Problems by
Searching
Chapter 1
Artificial Intelligence Module 2
BCS545B
Topics Covered in this Chapter
• Problem Solving Agents
• Example Problems
• Searching for Solutions
• Uniformed Search Strategies
Artificial Intelligence Module 2
BCS545B
Problem-Solving
• A problem can be defined formally by the following
components:
– Initial State
– Actions
– Transaction Model
– Goal Test
– Path Cost
Artificial Intelligence Module 2
BCS545B
Example problems
• 8-puzzle
– States: A state description specifies the location of each of the eight tiles
and the blank in one of the nine squares.
– Initial state: Any state can be designated as the initial state. Note that
any given goal can be reached from exactly half of the possible initial
states.
– Actions: The simplest formulation defines the actions as movements of
the blank space Left, Right, Up, or Down. Different subsets of these are
possible depending on where the blank is.
– Transaction model: Given a state and action, this returns the resulting
state
– Goal test: This checks whether the state matches the goal configuration.
– Path cost: Each step costs 1, so the path cost is the number of steps in
the path.
Artificial Intelligence Module 2
BCS545B
Example Problems
• 8 Queens Problem
– States: Any arrangement of 0 to 8 queens on the board
is a state.
– Initial state: No queens on the board.
– Actions: Add a queen to any empty square.
– Transaction model: Returns the board with a queen
added to the specified square.
– Goal test: 8 queens are on the board, none attacked.
Artificial Intelligence Module 2
BCS545B
Real World Problems
• Protein Design: It is a challenging real-world problem that involves
determining the sequence of amino acids that will fold into a three-
dimensional protein with specific properties.
– States: Each state corresponds to a specific sequence of amino acids.
– Initial State: The initial state is defined by the desired properties or functions of
the protein that the designer aims to achieve.
– Actions: Actions involve selecting or modifying amino acids in the sequence. The
choices made during the design process determine the final properties of the
protein.
– Transaction Model: The transition model defines how the sequence of amino acids
changes when certain actions are taken.
– Goal Test: The goal test checks whether the designed protein meets the specified
criteria, such as having the desired three-dimensional structure and functional
properties.
– Path Cost: The cost of a particular sequence may depend on factors such as
energy requirements, stability, or other biochemical considerations.
Artificial Intelligence Module 2
BCS545B
Some other Real-world Problems
• Route-finding problem - Touring problems,
Traveling Salesman problem
• VLSI layout
• Robot navigation
Artificial Intelligence Module 2
BCS545B
Searching for Solutions
• The process of solving problems using search
algorithms involves exploring the state space
through a search tree. Few Key terms:
– Search Tree – Child Node
– Node – Leaf Node
– Initial State – Frontier
– Goal State – Open List
– Expanding (or – Search Strategy
Generating) Nodes – Repeated State
– Parent Node – Loopy path
Artificial Intelligence
BCS545B
Module 2 – Redundent path
Searching for Solutions
• Tree Search Algorithm:
– function TREE-SEARCH (problem) returns a solution,
or failure
• initialize the frontier using the initial state of problem
• loop do
– if the frontier is empty then return failure
– choose a leaf node and remove it from the frontier
– if the node contains a goal state then return the corresponding
solution
– expand the chosen node, adding the resulting nodes to the frontier
Artificial Intelligence Module 2
BCS545B
Searching for Solutions
• Graph Search Algorithm:
– function GRAPH-SEARCH (problem) returns a solution,
or failure
• initialize the frontier using the initial state of problem
• loop do
– if the frontier is empty then return failure
– choose a leaf node and remove it from the frontier
– if the node contains a goal state then return the corresponding
solution (add the node to the explored set)
– expand the chosen node, adding the resulting nodes to the frontier
(only if not in the frontier or explored set)
Artificial Intelligence Module 2
BCS545B
Graph Search Vs. Tree Search
Artificial Intelligence Module 2
BCS545B
Infrastructure of Search Engine
• We have a structure that contains four components:
– [Link]: the state in the state space to which the node
corresponds
– [Link]: the node in the search tree that generated this
node
– [Link]: the action that was applied to the parent to
generate the node
– [Link]-COST: the cost, traditionally denoted by g(n), of
the path from the initial state to the node, as indicated by
the parent pointers
Here n is an indication of any node of the tree
Artificial Intelligence Module 2
BCS545B
Infratructure of search algorithms
Parent
Node
Action = Right
Path-Cost = 6
State
Artificial Intelligence Module 2
BCS545B
Infratructure of search algorithms
• The appropriate data structure for this search
algorithms are:
– queue
• EMPTY?
• POP
• INSERT
– stack
– prioriety queue
Artificial Intelligence Module 2
BCS545B
Measuring Problem-Solving performance
• We evaluate an algorithm’s performance in four
ways
– Completeness: Is the algorithm guaranteed to find a
solution when there is one?
– Optimality: Does the strategy find the optimal solution?
– Time Complexity: How long does it take to find a
solution?
– Space Complexity: How much memory is needed to
perform the search?
Artificial Intelligence Module 2
BCS545B
Uninformed Search Strategies
• Uninformed search strategies have no additional
information about states beyond what is provided
in the problem definition
• They can only generate successors and distinguish
a goal state from a non-goal state.
• The goal is to find a solution without utilizing any
additional knowledge or heuristics.
• We learn two search algorithms
– Breadth First Search
– Depth First Search
Artificial Intelligence Module 2
BCS545B
Breadth First Search
• In this searching technique, the nodes are expanded level by level,
starting from the root and moving to deeper levels
• We use Queue datastructure for the frontier. New Nodes are added to
the back of the queue
• Completeness: BFS is complete, as it is guaranteed to find a solution if
the shallowest goal node is at some finite depth.
• Time Complexity: The time complexity is exponential (O()), where b is
the branching factor and d is the depth of the shallowest goal node.
The worst case is when the solution is at the last node generated at
depth d.
• Space Complexity: The space complexity is also exponential (O())
Artificial Intelligence Module 2
BCS545B
Breadth First Search: Algorithm
Artificial Intelligence Module 2
BCS545B
Breadth First Search: Example Problem
B
F
E
Artificial Intelligence Module 2
BCS545B
Breadth First Search: Solution
B
F
E
Artificial Intelligence Module 2
BCS545B
Uniform Cost Search
• Uniform-cost search expands the node with the lowest path cost (g(n)) and uses
a priority queue for node selection.
• Key Features:
– Expands nodes based on path cost, not depth.
– Goal test is applied when a node is selected for expansion.
– Ensures optimality by checking if a better path to a node exists.
• Example: Finding the shortest path from A to B.
• Optimality: Uniform-cost search is optimal if all step costs are nonnegative. The
algorithm explores the optimal path before expanding any suboptimal paths.
• Complexity:
– Worst-case time and space complexity: O(b^(1 + C*/𝜖)).
– Can be much greater than breadth-first search due to exploring many low-cost nodes.
Artificial Intelligence Module 2
BCS545B
Uniform Cost Search Algorithm
Artificial Intelligence Module 2
BCS545B
Uniform Cost Search Example Problem
Start at S to
S 6
5 G*
D 2
9 6 E
A 2 2
1 7
3 B C 2
9
5 7
G1 G3
G2 8
F
Artificial Intelligence Module 2
BCS545B
Uniform Cost Search: Solution
Artificial Intelligence Module 2
BCS545B
Depth First Search
• In this searching technique, the nodes are expanded sub-tree by
sub-tree, starting from the root and moving to deeper levels
• We use Stack datastructure for the frontier. New Nodes are added
to the top of the stack
• Completeness: DFS is incomplete, as it cannot guarante to find a
solution if the shallowest goal node at some finite depth.
• Time Complexity: The time complexity is exponential (O())
• Space Complexity: The space complexity is also exponential (O())
Artificial Intelligence Module 2
BCS545B
Depth First Search: Algorithm
Artificial Intelligence Module 2
BCS545B
Depth First Search: Example Problem
B
F
E
Artificial Intelligence Module 2
BCS545B
Depth First Search: Solution
B
F
E
Artificial Intelligence Module 2
BCS545B
Depth Limited Search
Depth Limited Search is a modified version of DFS that imposes a limit on the depth of the
search. This means that the algorithm will only explore nodes up to a certain depth,
•
effectively preventing it from going down excessively deep paths that are unlikely to lead to
the goal. By setting a maximum depth limit, DLS aims to improve efficiency and ensure
more manageable search times.
• How Depth Limited Search Works
– Initialization: Begin at the root node with a specified depth limit.
– Exploration: Traverse the tree or graph, exploring each node’s children.
– Depth Check: If the current depth exceeds the set limit, stop exploring that path and backtrack.
– Goal Check: If the goal node is found within the depth limit, the search is successful.
Backtracking: If the search reaches the depth limit or a leaf node without finding the goal,
backtrack and explore other branches.
–
• Applications of Depth Limited Search in AI
Pathfinding in Robotics: DLS is employed for nonholonomic motion planning of robots in the
presence of obstacles. By imposing restriction on the depth it makes the robot stop after exploring a
–
particular depth of an area and restricting the robot from too much wandering.
Network Routing Algorithms: A DLS can be implemented to compute paths between nodes in
computer networks restricting the number of hops to prevent loops.
–
Puzzle Solving in AI Systems: DLS can be used to solve puzzles such as the 8-puzzle or Sudoku by
manipulating possible moves a fixed number of times that reduces how many steps are taken in the
–
search.
Game Playing: In AI for games, instead, DLS can be used to plan forward a few moves up to a
certain level of depth to help decide how much effort to put into a given decision.
–
Depth Limited Search Algorithm
Depth Limited Search Problem
A Start State: A
Goal State: H
B Max Depth: 2
C
D E F
G H I K
L M
Iterative Deepening DFS
• There are two common ways to traverse a graph, BFS and DFS
. Considering a Tree (or Graph) of huge height and width, both
BFS and DFS are not very efficient due to following reasons.
– DFS first traverses nodes going through one adjacent of root, then
next adjacent. The problem with this approach is, if there is a node
close to root, but not in first few subtrees explored by DFS, then DFS
reaches that node very late. Also, DFS may not find shortest path to
a node (in terms of number of edges).
– BFS goes level by level, but requires more space. The space required
by DFS is O(d) where d is depth of tree, but space required by BFS is
O(n) where n is number of nodes in tree
• IDDFS combines depth-first search’s space-efficiency and
breadth-first search’s fast search
Iterative Deepening DFS Algorithm
Iterative Deepening DFS Problem
A Start State: A
Goal State: M
B C
D E F
G H I K
L M
Bidirectional Search
• Bidirectional search is a graph search algorithm which find smallest
path from source to goal vertex. It runs two simultaneous search –
– Forward search from source/initial vertex toward goal vertex
– Backward search from goal/target vertex toward source vertex
• We can consider bidirectional approach when-
– Both initial and goal states are unique and completely defined.
– The branching factor is exactly the same in both directions.
• Performance measures
– 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(bd/2).
Comparing uninformed Search Strategies
•Breadth-First Search (BFS):
•Complete: Yes (if branching factor bbb is finite).
•Time Complexity: O(bd)O(b^d)O(bd), where ddd is the depth of the shallowest solution.
•Space Complexity: O(bd)O(b^d)O(bd) (stores all nodes at the current depth).
•Optimal: Yes (if all step costs are identical).
•Uniform-Cost Search (UCS):
•Complete: Yes (if step costs are positive).
•Time Complexity: O(b1+C∗/ϵ)O(b^{1+C^*/\epsilon})O(b1+C∗/ϵ), where C ∗C^*C ∗ is the cost of the optimal solution and ϵ\epsilonϵ is th
cost.
•Space Complexity: O(b1+C∗/ϵ)O(b^{1+C^*/\epsilon})O(b1+C∗/ϵ).
•Optimal: Yes (it finds the least-cost path).
•Depth-First Search (DFS):
•Complete: No (can get stuck in infinite paths in infinite state spaces).
•Time Complexity: O(bm)O(b^m)O(bm), where mmm is the maximum depth of the search tree.
•Space Complexity: O(b)O(b)O(b) (only needs to store the current path).
•Optimal: No (may find a suboptimal solution).
Comparing uninformed Search Strategies
•Depth-Limited Search:
•Complete: No (if the solution is deeper than the depth limit).
•Time Complexity: O(bl)O(b^l)O(bl), where lll is the depth limit.
•Space Complexity: O(bl)O(b^l)O(bl).
•Optimal: No (only guarantees optimality if the depth limit equals the depth of the shallowest solution).
•Iterative Deepening Search (IDS):
•Complete: Yes (combines DFS and BFS).
•Time Complexity: O(bd)O(b^d)O(bd) (similar to BFS, due to repeated state expansions).
•Space Complexity: O(bd)O(bd)O(bd) (only stores nodes along the current path).
•Optimal: Yes (if all step costs are identical).
•Bidirectional Search:
•Complete: Yes (if both searches use breadth-first).
•Time Complexity: O(bd/2)O(b^{d/2})O(bd/2) (exploits meeting in the middle).
•Space Complexity: O(bd/2)O(b^{d/2})O(bd/2) (needs to store one frontier).
•Optimal: Yes (if both searches are breadth-first).
Comparing uninformed Search Strategies