Search Algorithms Explained with Python

Introduction to Search Algorithms

Search algorithms are foundational tools in artificial intelligence (AI) and computer science. They enable problem-solving agents to explore complex environments, discover solutions, and make decisions. A search algorithm systematically examines possible paths in a problem space to find a solution, such as reaching a goal state from a given start state.

Broadly, search algorithms are divided into two main categories:

• Uninformed Search Algorithms: These algorithms do not have any domain-specific knowledge beyond the problem definition. They explore the search space blindly, treating all nodes equally without estimating the direction of the goal. While often inefficient in large or complex environments, they are guaranteed to find a solution (if one exists) under certain conditions, and they form the conceptual foundation for more advanced techniques.

• Informed Search Algorithms: Also known as heuristic search algorithms, these methods use additional information (heuristics) to evaluate the desirability of different nodes. This allows the algorithm to prioritize certain paths and reach the goal more efficiently.

This document provides detailed explanations, complexity analysis, and Python implementations of both uninformed and informed search algorithms. Each section is supported by example use cases to enhance understanding.

1. Uninformed Search Algorithms

1.1 Breadth-First Search (BFS)

Principle: Explore all the nodes at the present depth before moving on to nodes at the next depth level. It uses a queue (FIFO).

Time Complexity: $O(b^d)$
Space Complexity: $O(b^d)$

Python Code:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            queue.extend(graph[node])

# Example usage:
graph = {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}
bfs(graph, 'A')

1.2 Depth-First Search (DFS)

Principle: Explore as far as possible along each branch before backtracking. It uses a stack (LIFO).

Time Complexity: $O(b^d)$
Space Complexity: O(bd)

Python Code:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Example usage:
dfs(graph, 'A')

1.3 Uniform Cost Search (UCS)

Principle: Like BFS but uses cost instead of depth. It always expands the lowest cost node.

Time Complexity: $O(b^(1+C*/ε))$ where C* is the cost of the optimal solution.
Space Complexity: $O(b^(1+C*/ε))$

Python Code:

import heapq

def ucs(graph, start, goal):
    queue = [(0, start)]
    visited = set()

    while queue:
        cost, node = heapq.heappop(queue)
        if node == goal:
            print(f"Reached {goal} with cost {cost}")
            return
        if node not in visited:
            visited.add(node)
            for neighbor, weight in graph[node]:
                heapq.heappush(queue, (cost + weight, neighbor))

# Example usage:
graph_cost = {
    'A': [('B', 1), ('C', 5)],
    'B': [('D', 3), ('E', 1)],
    'C': [('F', 2)],
    'D': [],
    'E': [('F', 1)],
    'F': []
}
ucs(graph_cost, 'A', 'F')

1.4 Depth-Limited Search (DLS)

Principle: DFS with a maximum depth limit to avoid going too deep.

Time Complexity: $O(b^l)$
Space Complexity: O(bl)

Python Code:

def dls(graph, node, goal, limit):
    if node == goal:
        print(f"Found {goal}")
        return True
    if limit <= 0:
        return False
    for neighbor in graph[node]:
        if dls(graph, neighbor, goal, limit - 1):
            return True
    return False

# Example usage:
dls(graph, 'A', 'F', 3)

1.5 Iterative Deepening Depth-First Search (IDDFS)

Principle: Repeatedly apply DLS with increasing limits.

Time Complexity: $O(b^d)$
Space Complexity: O(bd)

Python Code:

def iddfs(graph, start, goal, max_depth):
    for depth in range(max_depth):
        if dls(graph, start, goal, depth):
            return True
    return False

# Example usage:
iddfs(graph, 'A', 'F', 5)

2. Informed Search Algorithms

2.1 Greedy Best-First Search

Principle: Uses heuristic function h(n) to choose the node that appears to be closest to the goal.

Time Complexity: $O(b^m)$ (where m is maximum depth of the search tree)
Space Complexity: $O(b^m)$

Python Code:

def greedy_best_first(graph, start, goal, heuristic):
    queue = [(heuristic[start], start)]
    visited = set()

    while queue:
        _, node = heapq.heappop(queue)
        if node == goal:
            print(f"Reached {goal}")
            return
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                heapq.heappush(queue, (heuristic[neighbor], neighbor))

# Example usage:
heuristic = {'A': 5, 'B': 4, 'C': 2, 'D': 6, 'E': 1, 'F': 0}
graph_simple = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
greedy_best_first(graph_simple, 'A', 'F', heuristic)

2.2 A* Search

Principle: Combines UCS and Greedy Best-First by using f(n) = g(n) + h(n), where g(n) is cost so far and h(n) is estimated cost to goal.

Time Complexity: Depends on heuristic quality, worst case $O(b^d)$
Space Complexity: $O(b^d)$

Python Code:

def a_star(graph, start, goal, heuristic):
    queue = [(heuristic[start], 0, start)]
    visited = set()

    while queue:
        f, cost, node = heapq.heappop(queue)
        if node == goal:
            print(f"Reached {goal} with total cost {cost}")
            return
        if node not in visited:
            visited.add(node)
            for neighbor, weight in graph[node]:
                g = cost + weight
                h = heuristic[neighbor]
                heapq.heappush(queue, (g+h, g, neighbor))

# Example usage:
graph_weighted = {
    'A': [('B', 1), ('C', 5)],
    'B': [('D', 3), ('E', 1)],
    'C': [('F', 2)],
    'D': [],
    'E': [('F', 1)],
    'F': []
}
heuristic2 = {'A': 5, 'B': 4, 'C': 2, 'D': 6, 'E': 1, 'F': 0}
a_star(graph_weighted, 'A', 'F', heuristic2)

3. References

• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
• Wikipedia: Search algorithm.
• GeeksforGeeks Tutorials: Search Algorithms.