What is Uninformed Search Algorithm in AI?

Uninformed searches, also known as blind searches, are search algorithms that explore a problem space without using any specific knowledge or heuristics about the problem domain. They operate in a brute force, meaning they try out every part of search space blindly.

Examples of uninformed search algorithms

Uninformed searches rely solely on the given problem definition and operate systematically to find a solution. Examples of uninformed search algorithms include breadth-first search (BFS), depth-first search (DFS),uniform-cost search (UCS), depth-limited search , and iterative deepening depth-first search. Although all these examples work in a brute force way, they differ in the way they traverse the nodes.

Breadth-first search

The breadth-first search (BFS) algorithm is commonly used for traversing trees or graphs, where it explores the neighboring nodes in a breadth-first manner, visiting the nodes at the same level before moving to the next level. The breadth-first search approach uses a queueA queue is a data structure that follows the First-In-First-Out (FIFO) principle, where elements are added at the back and removed from the front of the queue. to facilitate its implementation.

Approach

You can see more in-depth details about the algorithmic approach here.

Here is a simulation of a breadth-first search, where S represents the starting node, and G represents the goal node. The search will terminate once we reach goal node G.

from collections import deque
def bfs(graph, start, goal):
    visited = set()   # Set to keep track of visited nodes
    queue = deque([[start]])  # Queue for BFS, starting with the initial node
    
    if start == goal:
        return "Start and goal nodes are the same"
    
    while queue:
        path = queue.popleft()  # Get the first path from the queue
        
        node = path[-1]  # Get the last node from the path
        
        if node not in visited:
            neighbors = graph[node]  # Get neighbors of the current node
            
            for neighbor in neighbors:
                new_path = list(path)  # Copy the current path
                new_path.append(neighbor)  # Add the neighbor to the path
                queue.append(new_path)  # Add the new path to the queue
                
                if neighbor == goal:
                    return new_path  # If neighbor is the goal, return the path
                
            visited.add(node)  # Mark the node as explored
            
    return "No path found between start and goal"
# Example graph represented as an adjacency list
graph = {
    'S' : ['A','H'],
    'A': ['B', 'C'],
    'B': ['D', 'E', 'E'],
    'C': ['F', 'G'],
    'H': ['I'],
    'I': ['J']
}
start_node = 'S'
End_node = 'G'
print("BFS Path:", bfs(graph, start_node, End_node))

Depth-first search

Depth-first search (DFS) is an uninformed search algorithm that helps traverse a tree or graph using the concept of backtracking. Backtracking is an algorithmic technique that involves revisiting previous nodes to explore alternative paths until a solution is found. This algorithm traverses all nodes by advancing along a specific path and uses backtracking when it reaches the end of that path, allowing exploration of alternative paths. The DFS approach uses a stack A stack is a data structure that follows the Last-In-First-Out (LIFO) principle, where elements are added and removed from the top of the stack. to facilitate its implementation.

Approach

You can find in-depth details about the algorithmic approach at here.

Here is a depiction of a depth-first search simulation, where S represents the starting node, and G represents the goal node. The search will terminate once we reach goal node G.

def dfs(graph, start, goal, path=None):
    if path is None:
        path = [start]  # Initialize the path
    
    if start == goal:
        return path  # If start is goal, return the path
    
    if start not in graph:
        return None  # If start is not in graph, return None
    
    for node in graph[start]:
        if node not in path:  # Avoid cycles
            new_path = path + [node]  # Append node to the path
            result = dfs(graph, node, goal, new_path)  # Recursive call
            
            if result is not None:
                return result  # If a path is found, return it
    
    return None  # If no path is found, return None
# Example graph represented as an adjacency list
graph = {
    'S' : ['A','H'],
    'A': ['B', 'C'],
    'B': ['D', 'E', 'E'],
    'C': ['F', 'G'],
    'H': ['I'],
    'I': ['J']
}
start_node = 'S'
End_node = 'G'
print("DFS Path:", dfs(graph, start_node, End_node))

Uniform-cost search

Uniform-cost search (UCS) is an uninformed search algorithm that explores nodes in a graph based on the lowest cumulative cost, aiming to find the most cost-efficient path from the source to the destination. It starts from the root node and expands nodes in order of their minimum cumulative cost. The UCS approach uses a priority queue A priority queue is a data structure that maintains elements with associated priorities, allowing for efficient retrieval of the element with the highest (or lowest) priority. to facilitate its implementation.

Approach

You can find in-depth details about the algorithmic approach here.

Here is a simulation of a uniform-cost search, with S representing the starting node and G representing the goal node. The search will conclude upon reaching goal node G. The path with the lowest cost is S -> A -> C -> G, which has a total cost of 9.

Depth-limited search

The depth-limited search (DLS) algorithm works like a depth-first search but with a predefined limit. It resolves the issue of infinite paths in depth-first search by imposing a depth restriction. It is generally helpful when a graph has a very large number of nodes. Nodes at the depth limit are considered as having no further successors in this process, and the search terminates.

Approach

You can find in-depth details about the algorithmic approach here.

Here is a depth-limited search simulation with a depth level of 2, with S representing the starting node and G representing the goal node. Once the search reaches Level 2, it will halt, preventing us from discovering the goal node.

Iterative deepening depth-first search

Iterative Deepening Search (IDS) is an uninformed searching strategy that combines the completeness of breadth-first search with the memory efficiency of depth-first search by using a depth limit.

This approach ensures completeness by avoiding infinite or lengthy branches and explores each branch of a node from left to right until the desired depth is reached. IDS then returns to the root node and explores a different branch, resembling the behavior of DFS.

Approach

You can find in-depth details about the algorithmic approach at here.

Time complexity

To determine the time complexities of different types of uninformed searches, we can consider the total number of nodes (V) in the case of a tree, and the number of nodes (V) and edges (E) in the case of a graph.

For the scenarios where the level is significant, such as in depth-limited search and iterative deepening depth-first search, we can specify the maximum level (L), branching factorThe branching factor represents the average number of child nodes for each node in a tree or graph.(b), and depth represents the depth of the shallowest goal node in the search space(d) at which the search algorithm will operate.

The time complexities for each search algorithm are as follows.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Uninformed search algorithm	Tree	Graph
Breadth-first search	O ( V )	O( V+E )
Depth-first search	O( V )	O( V+E )
Uniform-cost search	O( (V + E) log V )	O( (V + E) log V )
Depth-limited search	O( b^L)	O( b^L)
Iterative deepening depth-first search	O( b^d)	O( b^d)

What is Uninformed Search Algorithm in AI?

Examples of uninformed search algorithms

Breadth-first search

Approach

Code

Depth-first search

Approach

Code

Uniform-cost search

Approach

Depth-limited search

Approach

Iterative deepening depth-first search

Approach

Time complexity

Conclusion