Uninformed Search Algorithms in AI

Posted by admin on 2025-09-17 19:27:35 | Last Updated by tintin_2003 on 2025-10-16 04:50:42

Share: Facebook | Twitter | Whatsapp | Linkedin Visits: 25

Uninformed Search Algorithms in AI

Last Updated : 23 Jul, 2025

Uninformed search algorithms, also referred to as blind search algorithms, represent a category of search algorithms that operate without utilizing any domain-specific knowledge regarding the problem being addressed.

Uninformed search algorithms depend on the information supplied in the problem specification, including the initial state, available actions in each state, and the target state. These are termed "blind" because they lack a heuristic function to direct the search toward the target; instead, they explore the search space in a systematic manner. Uninformed search algorithms offer fundamental search strategies for exploring problem spaces where no additional knowledge is available beyond the problem specification. These algorithms are crucial for addressing a broad range of problems in AI, including pathfinding, puzzle resolution, and state-space exploration. While these algorithms may not always be the most effective, they establish a foundation for understanding and solving complex problems in AI.

Categories of Uninformed Search Algorithms

1. Breadth-First Search (BFS)

Breadth-First Search examines all nodes at the current depth level before proceeding to the next level. It employs a queue (FIFO) to maintain track of nodes, ensuring that the shortest path is discovered in an unweighted graph.

Key Characteristics:

• Ensures the shortest path when the cost is uniform.
• Consumes more memory as it stores all child nodes.

Code Implementation:

Here,

• The bfs() function determines the shortest path in a 2D maze utilizing the Breadth-First Search (BFS) algorithm.
• It begins from a specified position and examines neighbors (up, down, left, right).
• A queue maintains positions along with the path taken.
• A visited set prevents revisiting positions.
• If the target is reached, the function returns the complete path; otherwise, it returns None.
• The visualize_maze() function displays the maze and the discovered path using Matplotlib.
• Different colors represent open paths, obstacles, start, target, and the solution path.
• imshow() displays the maze, and scatter() marks key positions.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from collections import deque

def bfs(maze, start, goal):
    queue = deque([(start, [])])
    visited = set()
    
    while queue:
        current, path = queue.popleft()
        x, y = current
        
        if current == goal:
            return path + [current]
        
        if current in visited:
            continue
        
        visited.add(current)
        
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] != 1:
                queue.append(((nx, ny), path + [current]))
    
    return None

def visualize_maze(maze, start, goal, path=None):
    cmap = ListedColormap(['white', 'black', 'red', 'blue', 'green'])
    bounds = [0, 0.5, 1.5, 2.5, 3.5, 4.5]
    norm = plt.Normalize(bounds[0], bounds[-1])
    
    fig, ax = plt.subplots()
    ax.imshow(maze, cmap=cmap, norm=norm)
    
    ax.scatter(start[1], start[0], color='yellow', marker='o', label='Start')
    ax.scatter(goal[1], goal[0], color='purple', marker='o', label='Goal')
    
    if path:
        for node in path[1:-1]:
            ax.scatter(node[1], node[0], color='green', marker='o')
    
    ax.legend()
    plt.show()

# Example maze
maze = np.array([
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
])

start = (0, 0)
goal = (4, 4)

path = bfs(maze, start, goal)

visualize_maze(maze, start, goal, path)

Output:

download-(3) Graphical Representation of the maze grid with start position represented by yellow circle and target position represented by purple circle.

2. Depth-First Search (DFS)

Depth-First Search (DFS) explores as deeply as possible along each path before backtracking. It utilizes a stack (LIFO) and is more memory-efficient than Breadth-First Search (BFS) but does not ensure the shortest path.

Key Characteristics:

• Effective for deep exploration.
• May become trapped in infinite loops if cycles exist.

Code Implementation:

Here,

• The dfs() function discovers a path in a 2D maze utilizing the Depth-First Search (DFS) algorithm.
• It begins from a specified position and examines neighbors (up, down, left, right).
• A stack maintains positions along with the path taken.
• A visited set prevents revisiting positions.
• If the target is reached, the function returns the complete path; otherwise, it returns None.
• The visualize_maze() function displays the maze and the discovered path using Matplotlib.
• Different colors represent open paths, obstacles, start, target, and the solution path.
• imshow() displays the maze, and scatter() marks key positions.

def visualize_maze(maze, start, goal, path=None):
    cmap = ListedColormap(['white', 'black', 'red', 'blue', 'green'])
    bounds = [0, 0.5, 1.5, 2.5, 3.5, 4.5]
    norm = plt.Normalize(bounds[0], bounds[-1])
    
    fig, ax = plt.subplots()
    ax.imshow(maze, cmap=cmap, norm=norm)
    
    ax.scatter(start[1], start[0], color='yellow', marker='o', label='Start')
    ax.scatter(goal[1], goal[0], color='purple', marker='o', label='Goal')
    
    if path:
        for node in path[1:-1]:
            ax.scatter(node[1], node[0], color='green', marker='o')
    
    ax.legend()
    plt.show()

def dfs(maze, start, goal):
    stack = [(start, [])]
    visited = set()
    
    while stack:
        current, path = stack.pop()
        x, y = current
        
        if current == goal:
            return path + [current]
        
        if current in visited:
            continue
        
        visited.add(current)
        
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]) and maze[nx][ny] != 1:
                stack.append(((nx, ny), path + [current]))
    
    return None

# Example maze
maze = np.array([
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
])

start = (0, 0)
goal = (4, 4)

path = dfs(maze, start, goal)

visualize_maze(maze, start, goal, path)

Output:

download-(4) The output represents the maze grid with start position represented by yellow circle and target position represented by purple circle.

3. Depth-Limited Search (DLS)

Depth Limited Search (DLS) is a variant of Depth First Search (DFS) that restricts the depth of exploration to prevent infinite loops in large or infinite search spaces.

Key Characteristics:

• Beneficial when the target depth is known.
• Cannot discover solutions beyond the depth limit.

4. Iterative Deepening Depth-First Search (IDDFS)

Iterative Deepening Depth-First Search (IDDFS) merges Breadth-First Search (BFS) and Depth First Search (DFS) by executing Depth First Search (DFS) with increasing depth limits until a solution is discovered.

Key Characteristics:

• Ensures completeness and optimality like Breadth-First Search (BFS).
• Utilizes less memory than Breadth-First Search (BFS).

5. Uniform-Cost Search (UCS)

Uniform-Cost Search (UCS) extends Breadth-First Search (BFS) by considering path costs, always expanding the least-cost node first. It ensures finding the optimal path when all costs are non-negative.

Key Characteristics:

• Discovers the least-cost path.
• Slower than Breadth-First Search (BFS) in uniform cost scenarios.

Code Implementation:

Here,

• The uniform_cost_search() function determines the least-cost path in a weighted graph.
• It employs a priority queue (heapq) to explore nodes with the lowest cost first.
• A frontier maintains nodes to be explored, and an explored set tracks visited nodes.
• If the target is reached, the function reconstructs and returns the optimal path.
• The reconstruct_path() function traces back from the target to reconstruct the discovered path.
• The visualize_graph() function displays the graph using NetworkX and Matplotlib.
• Nodes and edges are drawn, with weights labeled.
• If a path is discovered, its edges are highlighted in red.

import networkx as nx
import matplotlib.pyplot as plt
import heapq

class Node:
    def __init__(self, state, parent=None, action=None, path_cost=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost

    def __lt__(self, other):
        return self.path_cost < other.path_cost

def uniform_cost_search(graph, start, goal):
    frontier = []
    heapq.heappush(frontier, Node(start))
    explored = set()
    path = []
    
    while frontier:
        node = heapq.heappop(frontier)
        
        if node.state == goal:
            path = reconstruct_path(node)
            break
        
        explored.add(node.state)
        
        for (cost, result_state) in graph[node.state]:
            if result_state not in explored:
                child_cost = node.path_cost + cost
                child_node = Node(result_state, node, None, child_cost)
                if not any(frontier_node.state == result_state and 
                           frontier_node.path_cost <= child_cost for frontier_node in frontier):
                    heapq.heappush(frontier, child_node)
                    
    return path

def reconstruct_path(node):
    path = []
    while node:
        path.append(node.state)
        node = node.parent
    return path[::-1]

def visualize_graph(graph, path=None):
    G = nx.DiGraph()
    labels = {}
    for node, edges in graph.items():
        for cost, child_node in edges:
            G.add_edge(node, child_node, weight=cost)
            labels[(node, child_node)] = cost
    
    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
    
    if path:
        path_edges = list(zip(path[:-1], path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='r', width=2)
    
    plt.show()

# Define the graph
graph = {
    'A': [(1, 'B'), (3, 'C')],
    'B': [(2, 'D')],
    'C': [(5, 'D'), (2, 'B')],
    'D': []
}

start = 'A'
goal = 'D'
path = uniform_cost_search(graph, start, goal)

visualize_graph(graph, path)
print("Path from", start, "to", goal, ":", path)

Output:

Path from A to D : ['A', 'B', 'D']

download-(5) The graph represents the optimal path determined by the UCS algorithm

Applications of Uninformed Search Algorithms

• Pathfinding: Employed in navigation systems and robotics to discover the shortest route between locations. BFS and DFS explore the map to determine the optimal path.
• Puzzle Resolution: Applied in problems like the Eight Puzzle or Fifteen Puzzle to determine a sequence of moves leading to a solution.
• Game AI: Assists in exploring game trees to discover winning strategies. BFS and DFS are often combined with minimax or alpha-beta pruning for efficiency.
• Robot Navigation: Helps robots in path planning by exploring environments and identifying the best route while avoiding obstacles.
• Web Crawling: BFS is extensively used in web crawlers to systematically visit and index web pages by following links.

Uninformed search algorithms each have their own strengths and weaknesses, and the selection of algorithm depends on the specific problem at hand. By understanding these algorithms, AI practitioners can apply them effectively to a wide range of problems, from pathfinding in games to route planning in logistics.