Uninformed Search Algorithms

it is a class of search algorithm that  have no additional information on the goal node other than the one provided in the problem definition.  have no additional information on the goal node other than the one provided in the problem definition. Uninformed search is also called Blind search. These algorithms can only generate the successors and differentiate between the goal state and non goal state. 

The following uninformed search algorithms are discussed in this section.

Depth First Search
Breadth First Search
Uniform Cost Search

Depth-first search-
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
 The algorithm starts at the root node and explores as far as possible along each branch before backtracking. 
It uses last in- first-out strategy and hence it is implemented using a stack.
example-link for image
https://media.geeksforgeeks.org/wp-content/uploads/question-3-e1547112515247.png
Path:   S -> A -> B -> C -> G 
d        = the depth of the search tree 
n^i        = number of nodes in level i        
Time complexity: Equivalent to the number of nodes traversed in DFS. 
T(n) = 1 + n^2 + n^3 + ... + n^d = O(n^d)        
Space complexity: 
maximum storage space required at any point of dfs.
 S(n) = O(n*d)
Completeness: DFS is complete if the search tree is finite, meaning for a given finite search tree, DFS will come up with a solution if it exists. 
Optimality: DFS is not optimal, meaning the number of steps in reaching the solution, or the cost spent in reaching it is high. 

Breadth-first search 
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It is implemented using a queue.

example-same image
Path: S -> D -> G 
 s        = the depth of the shallowest solution. 
n^i        = number of nodes in level i        . 
Time complexity: Equivalent to the number of nodes traversed in BFS until the shallowest solution. T(n) = 1 + n^2 + n^3 + ... + n^s = O(n^s)        
Space complexity: Equivalent to how large can the fringe get. S(n) = O(n^s)        
Completeness: BFS is complete, meaning for a given search tree, BFS will come up with a solution if it exists. 

Optimality: BFS is optimal as long as the costs of all edges are equal. 

Uniform Cost Search: 
UCS is different from BFS and DFS because here the costs come into play. In other words, traversing via different edges might not have the same cost. The goal is to find a path where the cumulative sum of costs is the least. 

Path: S -> A -> B -> G 
Cost: 5 
Let C        = cost of solution. 
 epsilon      = arcs cost. 

Then C /epsilon =        effective depth 

Time complexity:   T(n) = O(n^C\epsilon)        , Space complexity:   S(n) = O(n^C/repsilon)

UCS is complete only if states are finite and there should be no loop with zero weight.
UCS is optimal only if there is no negative cost.