UNINFORMED SEARCHING IN AI

Question 1

What’s the time complexity of BFS & DFS

Answer 1

It’s b^d, where

b –> Branching factor: Max number of children that a node has.

d –> Depth of the node.

Question 2

What’s the space Complexity of BFS & DFS

Answer 2

BFS –> b^(d+1)
DFS –> b*d

b –> Branching factor: Max number of children that a node has.

d –> Depth of the node.

Question 3

Explain Depth Limit Search(DLS)

Answer 3

This is similar to DFS, it introduces a predetermined limit for the depth. This is done to overcome the disadvantage of DFS, which is blind alley.
DLS is not complete because solution may lie beyond the cut-off depth.
It takes O(b^l) time and O(bl) space, where l is the depth limit.

Question 4

Explain DFS Iterative Deepening

Answer 4

DFS-ID calls DFS for different depths starting from an initial value. In every call, DFS is restricted from going beyond given depth.
DFS-ID is complete and gives optimal result.

Question 5

What’s the time and space complexity of Uniform Cost Search(UCS)

Answer 5

Time complexity –> (b^c)/m
Space complexity –> b^(d+1), where

b –> Branching factor.
c –> Cost of optimal path.
d –> Depth of the node.
m –> minimum edge length.