Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is uninformed search algorithm in AI?
3.
Types of Uninformed Search Algorithms
4.
Breadth First Search
5.
Depth First Search
6.
Uniform Cost Search
6.1.
Algorithm
6.2.
Example
7.
Depth Limited Search
7.1.
Algorithm
7.2.
Example
8.
Iterative Deepening Depth First Search
8.1.
Algorithm
8.2.
Example
8.3.
Features of Uninformed Search Algorithms
9.
Frequently Asked Questions
9.1.
What is uninformed search algorithm in AI?
9.2.
What are search algorithms in AI?
9.3.
What is breadth-first search algorithm in artificial intelligence?
9.4.
How many types of uninformed search are there?
10.
Conclusion
Last Updated: Mar 27, 2024
Easy

Uninformed Search Algorithms in Artificial Intelligence

Author Sinki Kumari
3 upvotes
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Uninformed search, also called blind search, is an algorithm that explores a problem space without prior knowledge, focusing solely on the initial state and possible actions.

One of the important categories of Algorithms is Uninformed Search Algorithms in Artificial Intelligence.

Uninformed Search Algorithms in Artificial Intelligence

This article will discuss the important Uninformed Search Algorithms like BFS, DFS, DLS, IDDFS, etc. So without further ado, let’s start by first exploring Uninformed Search Algorithms in Artificial Intelligence!

What is uninformed search algorithm in AI?

Uninformed Search Algorithms or Blind Search Algorithms are the search algorithms that are used to find the solutions to the problem which does not have any domain knowledge associated with it. It is used in Artificial Intelligence to find relevant solutions by exploring all the possibility sets of the problem space.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Types of Uninformed Search Algorithms

These are the various types of Uninformed Search Algorithms in Artificial Intelligence:

Types of Uninformed Search Algorithms
  1. Breadth First Search ( BFS )
  2. Depth First Search ( DFS )
  3. Uniform Cost Search ( UCS )
  4. Depth Limited Search ( DLS ) 
  5. Iterative Deepening Depth First Search ( IDDFS )

 

Let’s discuss them one by one in detail.

Breadth First Search

Breadth First Search ( BFS ) is used to explore all the neighbouring states or nodes of the initial node, thus guaranteeing the shortest path between nodes in a tree-like data structure. It is used to reach the goal state using the shortest path between the initial and goal state. 

Breadth First Search

 

The Queue data structure is used in BFS. The initial node is first pushed into the Queue, and then after visiting the front node, all the neighbouring nodes are pushed into the Queue. Thus it ensures that the goal state is reached using the shortest path by exploring all the neighbours at once.
 

Refer to this article to learn in detail about the BFS. 

Depth First Search

Depth First Search ( DFS ) is used to find the solutions by exploring all the nodes till the end of a branch is reached and then backtracking and exploring other branches in the same way. It is a recursive algorithm. DFS searches along each branch by going into the deep. 

Depth First Search

 

The Stack data structure is used in DFS in a similar way queue was used in BFS. First, the initial state is pushed into the stack, and then the top element is popped out, and its neighbours are pushed into the stack. In this way, it makes sure to traverse along each branch separately. 
 

Refer to this article to learn in detail about the DFS. 

Uniform Cost Search

Uniform Cost Search ( UCS ) is used to find the solution to a problem along with minimizing the cost of the path from the initial state to the goal state. UCS works by selecting the path with the minimum cost at each step after exploring all the possible paths. 

Uniform Cost Search

 

The cost function f(n) is defined in UCS, which gives the cost of the path from the initial step to each node n. It traverses the path with the lowest value of f(n), thus ensuring the lowest cost path.

Let’s see the algorithm to find UCS using the Priority queue.

Algorithm

  1. Initialize a priority queue to explore the nodes according to their costs.
     
  2. Set the cost of the initial state as 0 and push it into the priority queue.
     
  3. Repeat the following steps until the priority queue is not empty:

    1. Remove the topmost node, which is the node with the lowest cost.
       
    2. If this node is equal to the goal node, end the search.
       
    3. Else, calculate the path costs of the neighbours of the current node.
       
    4. Update the cost of the neighbour node if it already exists in the priority queue; else, push this node.
       
  4. If the search doesn’t end in the above loop, no solution exists.

Example

Let’s see the steps of UCS in the following example.

Steps of UCS


1. Start from the initial node A and set the cost to reach A as 0. Insert A into the priority queue.

          Priority Queue: ( A, 0 )

2. Extract the node with the minimum cost from the priority queue. Node A is selected since it has the lowest cost. Insert its neighbours B and D into the queue.

Current Node: A, Cost: 0 

Priority Queue: (B, 2), (D, 4)

3. Extract the node with the minimum cost from the priority queue. The node B is selected. Insert its neighbours C and G into the queue.

Current Node: B, Cost: 2 

Priority Queue: (G, 1), (D, 4), (C, 5 )

4. Again, extract the node with the minimum cost from the priority queue. The node G is selected. Stop since G is equal to the goal node.

Current Node: G, Cost: 3
 

The shortest path from A to G found by UCS is A  -> B -> G, with a total cost of 3. 
 

Let’s see the complexities of the above algorithm.

Time Complexity: The worst-case time complexity of UCS is O(b^d), where b is the branching factor of the search tree, and d is the depth of the goal node.

Space Complexity: The space complexity of UCS is also O(b^d) but can be further reduced to O(bd) if we use a binary heap as the priority queue.

Depth Limited Search

Depth Limited Search ( DLS ) is a modified DFS algorithm that is designed in such a way as to overcome the problem of infinite loops that may occur in the DFS algorithm due to the presence of cycles. 

Depth Limited Search

 

Instead of performing the DFS up to the entire length of a branch, DLS limits the depth of exploration by performing DFS only till a predefined level. 

Let’s see the algorithm to find DLS.

Algorithm

  1. Start with the initial state of the problem.
     
  2. Explore the current state and generate its successors.
     
  3. If the depth of the current state is equal to the predefined limit, stop the search.
     
  4. Else, recursively apply the DLS to explore the branch till the level with limit is reached.
     
  5. Repeat the above steps until a goal state is reached or all the states till that level is traversed.

Example

Let’s see the steps of DLS in the following example.

steps of dls
  1. Start from the Initial State, i.e. A and expand its neighbours B and C.
     
  2. Perform DFS and visit neighbour B. This is Level Number 1, and since our Depth Limit is 2, we can continue to visit the neighbour of B, i.e. D and G.
     
  3. Expand the neighbour D, and Since the Depth limit is reached, backtrack to node B.
     
  4. Expand the other neighbour, G. Since G is equal to the goal state, stop the search and return the path.
     

Hence, the resultant path is A -> B -> D -> G.
 

Let’s see the complexities of the above algorithm.

Time Complexity: The worst-case time complexity of DLS is O(bd), where b is the branching factor of the search tree, and d is the depth limit.

Space Complexity: The space complexity of DLS is also O(bd) since only the nodes within the depth limit are visited.

Iterative Deepening Depth First Search

Iterative Deepening Depth First Search ( IDDFS ) is a combination of two algorithms: DFS and DLS. It is performed in a similar way as DLS but after increasing the depth limits after every iteration. 

Iterative Deepening Depth First Search

This starts with setting the depth limit as 0 and performing the DLS to explore all the nodes at each level. If the goal state is not reached, we increase the depth limit and perform the search again up to the new depth limit.

Let’s see the algorithm to perform IDDFS.

Algorithm

  1. Set the depth limit as 0, which means the search will be performed only up to the 0th level.
     
  2. Start from the initial state and perform the DLS with a current depth limit of 0.
     
  3. If the goal state is found, return it.
     
  4. Else, increase the depth limit by 1 and repeat the above steps.
     
  5. Repeat until the goal state is reached or all the nodes are explored.

Example

Let’s see the steps of IDDFS in the following example.

steps of IDDFS
  1. Set the depth limit as 0 and start the search from the initial state, i.e. A.
     
  2. Since A is not equal to Goal Node, and there are no unexplored nodes left till level 0, Increment the limit by 1.
     
  3. Again start from the initial state, A and perform DLS till level 1. Following is the explored path: A -> B -> C.
     
  4. Again, the Goal Node is not found; increment the limit by 1. Now depth limit is equal to 2.
     
  5. Now, the explored path is A -> B -> D -> G. Since the Goal state is found, we will stop the search.

     

Let’s see the complexities of the above algorithm.

Time Complexity: The worst-case time complexity of IDDFS is O(b^d), where b is the branching factor of the search tree, and d is the depth of the goal node.

Space Complexity: The space complexity of IDDFS is O(bd) since only the nodes till the current depth limit are stored.

Features of Uninformed Search Algorithms

Following are some of the features of Uninformed Search Algorithms:

  • These algorithms do not possess any prior information about the states or actions associated with the problem domain.
     
  • These algorithms explore the problem space systematically until they find a solution or exhaust all possibilities.
     
  • Uninformed search algorithms rely solely on the problem's definition and some predefined rules.
     
  • These algorithms guarantee a solution if a possible solution exists for that problem.
     
  • These algorithms are easy to implement as they do not require any additional domain knowledge.

Frequently Asked Questions

What is uninformed search algorithm in AI?

An uninformed search algorithm in AI refers to a search method that operates without any prior knowledge about the problem domain. It explores the search space blindly, without utilizing any heuristic information or domain-specific insights.

What are search algorithms in AI?

Search algorithms in AI are techniques used to find solutions within a problem space. These algorithms systematically explore different states or configurations of a problem to reach a desired goal state. They can range from uninformed methods like breadth-first search to informed methods like A* search.

What is breadth-first search algorithm in artificial intelligence?

Breadth-first search algorithm in artificial intelligence is a systematic search strategy that explores all neighbor nodes at the present depth level before moving on to deeper levels. It starts from the root node and explores all the nodes at the present depth level before moving to the next level.

How many types of uninformed search are there?

Uninformed search algorithms in AI typically include two main types: breadth-first search and depth-first search. Breadth-first search explores all neighbor nodes at the present depth level before moving to the next level, while depth-first search explores as far as possible along each branch before backtracking. These methods don't use domain-specific knowledge to guide the search process.

Conclusion

In this article, we discussed the Uninformed Search Algorithms in Artificial Intelligence, its features and its various types. Don’t forget to try out some examples of all the Algorithms and try to code them on your own.

You can read these articles to learn more about Search Algorithms and Artificial Intelligence.

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problemsinterview experiences, and interview bundles.

We wish you Good Luck! 

Happy Learning!

Previous article
Adversarial Search in Artificial Intelligence
Next article
Forward and Backward Chaining in AI
Live masterclass