AiIntermediate15 min readUpdated March 2025

AI Problem Solving & Search

Search algorithms are the backbone of classical AI problem-solving. This article covers BFS, DFS, and A* with heuristics - the algorithms that power everything from game AI to route planning.

Problem Solving as Search

In classical AI, many problems are modeled as a search through a state space:

- State: A snapshot of the problem at a given point (e.g., position on a map). - Initial State: Where the agent starts. - Goal State: The desired outcome. - Actions: Transitions between states. - Path Cost: The cost of reaching a state.

The agent's job is to find a sequence of actions (a path) from the initial state to the goal state - ideally the optimal one.

Uninformed Search: BFS and DFS

Uninformed (blind) search algorithms explore the state space without any domain-specific knowledge.

Breadth-First Search (BFS): - Explores all nodes at depth d before depth d+1. - Guaranteed to find the shortest path (in terms of number of steps). - Memory-intensive: stores all frontier nodes.

Depth-First Search (DFS): - Explores as deep as possible before backtracking. - Memory-efficient: only stores the current path. - Not guaranteed to find the shortest path; can get stuck in infinite loops.

python

from collections import deque

# Graph represented as adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# Breadth-First Search (BFS)
def bfs(graph, start, goal):
    queue = deque([[start]])
    visited = set()
    
    while queue:
        path = queue.popleft()
        node = path[-1]
        
        if node == goal:
            return path
        
        if node not in visited:
            visited.add(node)
            for neighbor in graph.get(node, []):
                new_path = path + [neighbor]
                queue.append(new_path)
    
    return None

# Depth-First Search (DFS)
def dfs(graph, start, goal, visited=None, path=None):
    if visited is None:
        visited = set()
    if path is None:
        path = [start]
    
    if start == goal:
        return path
    
    visited.add(start)
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            result = dfs(graph, neighbor, goal, visited, path + [neighbor])
            if result:
                return result
    return None

print("BFS path A->F:", bfs(graph, 'A', 'F'))
# Output: BFS path A->F: ['A', 'C', 'F']

print("DFS path A->F:", dfs(graph, 'A', 'F'))
# Output: DFS path A->F: ['A', 'B', 'E', 'F']

Informed Search: A* Algorithm

A* (A-star) is the most widely used informed search algorithm. It combines:

- g(n): The actual cost from the start node to node n. - h(n): A heuristic estimate of the cost from n to the goal. - f(n) = g(n) + h(n): The estimated total cost through n.

A* always expands the node with the lowest f(n). If the heuristic h(n) is admissible (never overestimates the true cost), A* is guaranteed to find the optimal path.

Common heuristics: - Manhattan distance (grid movement without diagonals) - Euclidean distance (straight-line distance)

python

import heapq

def a_star(graph, start, goal, heuristic):
    """
    graph: dict of {node: [(neighbor, cost), ...]}
    heuristic: dict of {node: estimated_cost_to_goal}
    """
    # Priority queue: (f_cost, g_cost, node, path)
    open_set = [(heuristic[start], 0, start, [start])]
    visited = set()
    
    while open_set:
        f, g, node, path = heapq.heappop(open_set)
        
        if node == goal:
            return path, g  # Return path and total cost
        
        if node in visited:
            continue
        visited.add(node)
        
        for neighbor, cost in graph.get(node, []):
            if neighbor not in visited:
                new_g = g + cost
                new_f = new_g + heuristic.get(neighbor, 0)
                heapq.heappush(open_set, (new_f, new_g, neighbor, path + [neighbor]))
    
    return None, float('inf')

# Example: Simple grid-like graph
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

# Heuristic: estimated distance to goal 'D'
heuristic = {'A': 6, 'B': 4, 'C': 2, 'D': 0}

path, cost = a_star(graph, 'A', 'D', heuristic)
print(f"A* path: {path}, Total cost: {cost}")
# Output: A* path: ['A', 'B', 'C', 'D'], Total cost: 4

Comparing Search Algorithms

Here is a summary of key properties:

BFS - Complete: Yes | Optimal: Yes (unit cost) | Time: O(b^d) | Space: O(b^d)
DFS - Complete: No (infinite spaces) | Optimal: No | Time: O(b^m) | Space: O(bm)
A* - Complete: Yes | Optimal: Yes (admissible h) | Time: O(b^d) | Space: O(b^d)
Greedy Best-First - Complete: No | Optimal: No | Fast but not guaranteed optimal

Real-World Applications

Search algorithms power many real-world AI systems:

Google Maps / GPS navigation - A* and Dijkstra for shortest routes.
Chess and board games - Minimax with alpha-beta pruning.
Robot path planning - A* in grid or continuous spaces.
Puzzle solving - BFS/DFS for 8-puzzle, Rubik's cube.
Network routing - Dijkstra's algorithm in routers.

Key Takeaways

AI problems are modeled as state-space search: initial state -> goal state via actions.
BFS finds the shortest path but uses more memory; DFS uses less memory but is not optimal.
A* combines actual cost g(n) and heuristic h(n) to find optimal paths efficiently.
A heuristic must be admissible (never overestimates) for A* to guarantee optimality.
Search algorithms power GPS navigation, game AI, and robot path planning.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com