Artificial Intelligence

Outline
 Last Class
 Problem Solving
 Classical Approach
 Problem Representation
 Searching and Categories of the search algorithm
 Today
 Properties
of Search Algorithms
 Uninformed Search Algorithms
 Breadth-first search
 Depth-first search
 Depth-limited search
 Uniform-cost search
 Iterative deepening search
 Properties of Search Algorithms
 Following are the four essential properties of search
algorithms to compare the efficiency of these
algorithms:
 Completeness: Does it always find a solution if one exists?
 Optimality: whether the algorithm found a best solution
(lowest path cost) ?
 Time complexity: A measure of time for an algorithm to
complete its task. i.e. number of nodes generated/expanded
 Space complexity: The maximum storage space required at
any point during the search (Maximum nodes in memory)
 Uninformed Search Algorithms
 Use only the information available in the problem definition
 Carried out without any additional information that is
already provided in the problem statement
 How to traverse the tree, how to identify leaf and goal nodes
 Solution cost is not taken into account

 Breadth-first search
 Depth-first search
 Depth-limited search
 Uniform-cost search
 Iterative deepening search
 Breadth-first search (BFS)
 The most common search strategy for traversing a tree
or graph
 This algorithm searches breadthwise in a tree or graph
and progresses downward level by level
 The breadth-first search algorithm is an example of a
general-graph search algorithm.

 Breadth-first search implemented using FIFO queue

data structure.
Contd..
 Simple search algorithm
 Let S be the start state
 Initialize Q with the start node Q=(S) as the only
entry; set Visited = (S)
 If Q is empty, fail. Else pick node X from Q
 If X is a goal, return X, we’ve reached the goal
 (Otherwise) Remove X from Q
 Find all the children of state X not in Visited
 Add these to Q; Add Children of X to Visited
 Go to Step 2
 Contd..
S

A B

C D E F

G H

 Add S in output, mark as visited, and make first

currently working node (CWN), check for goal
 Output: S
 Contd..
S

A B

C D E F

G H
A B
 If S is not goal, Check all unvisited adjacent nodes of
S, enqueue them and also mark as visited
 Output: S A B
 Contd..
S

A B

C D E F

G H
A B
 Update CWN. Check first element in Q i.e. A. make it
CWN and dequeue it. Check for goal
 Output: S A B
 Contd..
S

A B

C D E F

G H
A B C D
 If A is not goal, Check all unvisited adjacent nodes of
A, enqueue them and also mark as visited
 Output: S A B C D
 Contd..
S

A B

C D E F

G H
A B C D
 Update CWN. Check first element in Q i.e. B. make it
CWN and dequeue it. Check for goal.
 Output: S A B C D
 Contd..
S

A B

C D E F

G H
A B C D E F
 If B is not goal, Check all unvisited adjacent nodes of
B, enqueue them and also mark as visited
 Output: S A B C D E F
 Contd..
S

A B

C D E F

G H
A B C D E F G H
 Update CWN. Check first element in Q i.e. C. make it
CWN and dequeue it. Check for goal.
 Output: S A B C D E F
 Contd..
S

A B

C D E F

G H
A B C D E F G H
 If C is not goal, Check all unvisited adjacent nodes of
C, enqueue them and also mark as visited
 Output: S A B C D E F G H
 Contd..
S

A B

C D E F

G H
A B C D E F G H
 Update CWN. Check first element in Q i.e. D. make it
CWN and dequeue it. Check for goal.
 Output: S A B C D E F G H
 Contd..
S

A B

C D E F

G H
A B C D E F G H
 Check all unvisited adjacent nodes of D, No unvisited
node, no enqueue, Update CWD and check for goal
 Output: S A B C D E F G H
 Contd..
 Now, as there is no unvisited node left, every node left
in Q will be made CWD and checked for goal,
sequentially, and gets removed from the Q.
 When the last node H is removed from Q and checked
for goal, the algorithm says YES.
 The path to achieve goal will be:

SABCDEF GH

 BFS travels a significant area of the search space if

the solution is located somewhere deep inside the tree
 Pros and Cons
 Advantages
 Provides a solution if any solution exists.
 If there are more than one solutions for a given
problem, then BFS will provide the minimal
solution which requires the least number of steps.
 Disadvantages
 It requires lots of memory since each level of the
tree must be saved into memory to expand the next
level.
 BFS needs lots of time if the solution is far away
from the root node.
 Performance Measurement
 Complete ?
 Yes (if b (max branch factor) is finite)
 Optimal ?
 Only if cost = 1 per step, otherwise not optimal in general
 Time ?
 O(n), where n is the number of nodes. Every node
is traversed
 Space ?
 O(n), as in worst case you need to hold all vertices
in the queue.
 Task
 Use BFS to traverse the graph starting from node A.
 Depth-first search (BFS)
 A recursive algorithm for traversing a tree or graph
data structure.
 It starts from the root node and follows each path to
its greatest depth node before moving to the next path.
That’s why called the depth-first search
 The searching process is similar to the BFS algorithm.

 DFS is implemented using LIFO i.e. stack data

structure.
 Flow: Root node--->Left node ----> right node.
 Contd..
 Search from root node S->A->B->D->E,
 After traversing E, it will backtrack the tree as E has no other
successor and still goal node is not found. After backtracking it
will traverse node C and then G, and here it will terminate as it
found goal node.
 Example
S

A B

C D E F
S

G H

 Add S in output and Stack, mark as visited, and make

first currently working node (CWN), check for goal
 Output: S
 Example
S

A B

C D E F A
S

G H

 If S is not goal, check next unvisited deepest adjacent

node i.e. A. push A and also mark as visited
 Output: S A
 Example
S

A B

C
C D E F A
S

G H

 If A is not goal, check next unvisited deepest adjacent

node i.e. C. push C and also mark as visited
 Output: S A C
 Example
S

A B
G
C
C D E F A
S

G H

 If C is not goal, check next unvisited deepest adjacent

node i.e. G. push G and also mark as visited
 Output: S A C G
 Example
S

A B
G
C
C D E F A
S

G H

 If G is not goal, check next unvisited deepest adjacent

node. No node. pop G.
 Output: S A C G
 Example
S

A B
H
C
C D E F A
S

G H

 The next node in stack is C. backtrack, check next

unvisited deepest adjacent node of C i.e. H. push H
and mark visited Output: S A C G H
 Contd..
 As H is the goal, so, it will stop and pop the nodes
from stack.
 The path to achieve the goal is :

SACGH

 To traverse all the nodes:

 Example
S

A B D
H
C
C D E F A
S

G H
 The next node in stack is now, H. check next unvisited
deepest adjacent node. No node. Pop H, C. Now A has
one unvisited node D, push D and mark visited
Output: S A C G H D
 Example
S

A B
B
D
C D E F A
S

G H
 The next node in stack is now, D. No unvisited
deepest adjacent node. Pop D, A. Now S has one
unvisited node B, push B and mark visited
 Output: S A C G H D B
 Example
S

A B

E
C D E F B
S

G H
 The next node in stack is now, B. Two unvisited
deepest adjacent node. Push E and mark visited
 Output: S A C G H D B E
 Example
S

A B
F
E
C D E F B
S

G H
 The next node in stack is now, E. No unvisited deepest
adjacent node. Pop E. Now B has one unvisited node
F. push F and mark visited
 Output: S A C G H D B E F
 Example
S

A B

F
C D E F B
S

G H
 The next node in stack is now, F. No unvisited deepest
adjacent node. Pop F. Similarly pop B and finally S.
 Output: S A C G H D B E F
 Contd..
 So, the whole tree is traversed using DFS and the path
is:
SACGHDBEF
 Pros and Cons
 Advantages
 DFS requires very less memory as it only needs to store a
stack of the nodes on the path from root node to the current
node.
 It takes less time to reach to the goal node than BFS
algorithm (if it traverses in the right path).
 Disadvantages
 There is the possibility that many states keep re-occurring,
and there is no guarantee of finding the solution.
 DFS algorithm goes for deep down searching and sometime
it may go to the infinite loop.
 Performance Measurement
 Complete ?
 Complete within finite space but fails in infinite-depth spaces,
spaces with loops. NO
 Optimal ?
 NO, as it may generate a large number of steps or high cost to
reach to the goal node.
 Time ?
 O(n), where n is the number of nodes traversed.
 Space ?
 O(d), where d is the maximum depth of the tree.
 Depth-Limited Search Algorithm
 Similar to depth-first search with a predetermined
limit, to guarantee that the algorithm ends.
 The node at the depth limit will be treated as it has no
successor nodes further.
 Can solve the drawback of the infinite path in the DFS

 Can be terminated with two Conditions of failure:

 Standard failure value: It indicates that problem does not
have any solution.
 Cutoff failure value: It defines no solution for the problem
within a given depth limit.
 Contd..
 An example with depth limit of 2.

 Will traverse downward until level 2. if finds goal,

terminates otherwise expand downwards by
increasing depth limit (Level number)
 Pros and Cons
 Advantages
 Depth-limited search is Memory efficient.

 Disadvantages
 Depth-limited search also has a disadvantage of
incompleteness.
 It may not be optimal if the problem has more than one
solution.
 Performance Measurement
 Complete ?
 complete if the solution is above the depth-limit.
 Optimal ?
 Yes (only if l > d) i.e. depth limit is above the maximum
depth of the tree
 Time ?
 O(bl) where, l -> depth-limit, b-> node at every state
 Space ?
 O(bl).
 Uniform-cost Search
 A searching algorithm to traverse a weighted tree or
graph
 A different cost is available for each edge
 The primary goal is to find a path to the goal node,
having the lowest cumulative cost
 It searches next nodes according to their path costs
 Implemented by the priority queue.
 i.e. It gives maximum priority to the lowest
cumulative cost
 If the path cost of all edges is the same, its simply BFS
 Pros and Cons
 Advantages
 optimal because at every state the path with the least cost is
chosen.

 Disadvantages
 It does not care about the number of steps involved in
searching and only concerned about path cost.
 Performance Measurement
 Complete ?
 Yes, finds a solution if there is a solution.
 Optimal ?
 Optimal as it only selects a path with the lowest path cost.
 Time ?
 O(b(c/ϵ)) where, ϵ -> is the lowest cost, c -> optimal cost
 Space ?
 O(b(c/ϵ))
 Task

 Find the best path and also calculate the cost.

Optimal Solution??
 Iterative deepening Depth First Search(IDDFS)
 A combination of DFS and BFS algorithms
 It searches for the best depth in each iteration
 Searches until a certain depth and the depth keeps
increasing at every iteration until it reaches the goal
state.
 Advantages:
 It combines the benefits of BFS and DFS search algorithm
in terms of fast search and memory efficiency.
 Disadvantages:
 Main drawback is that it repeats all the work of the previous
phase.
 Contd..

 1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
 Performance Measurement
 Complete ?
 Yes, (by limiting the depth).
 Optimal ?
 Yes (if step cost is uniform)
 Time ?
 O(bd), where ‘b‘ – maximum branching factor in a
tree and ‘d‘ – the depth of the least-cost solution.
 Space ?
 O(bd)
END