Description

Search algorithms help AI systems explore a problem space to find solutions. Four essential ones are:

• Breadth-First Search (BFS): Explores nodes level by level. Guarantees the shortest path in unweighted graphs.
• Depth-First Search (DFS): Explores deep into one branch before backtracking. Memory-efficient but may get stuck.
• Uniform Cost Search (UCS): Expands the least-cost node first. Best for weighted graphs with no heuristic.
• A*: Combines actual cost from the start (g) and estimated cost to the goal (h) using f(n) = g(n) + h(n).

Examples (Code)

Below is a simple example

#BFS Example in Python
from collections import deque

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 = list(path)
                new_path.append(neighbor)
                queue.append(new_path)

    return None

#DFS Example in Python
def dfs(graph, start, goal, path=None, visited=None):
    if path is None:
        path = [start]
    if visited is None:
        visited = set()

    visited.add(start)

    if start == goal:
        return path

    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            new_path = dfs(graph, neighbor, goal, path + [neighbor], visited)
            if new_path:
                return new_path

    return None

#Uniform Cost Search (UCS) Example
import heapq

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

    while queue:
        cost, path = heapq.heappop(queue)
        node = path[-1]

        if node == goal:
            return path, cost

        if node not in visited:
            visited.add(node)
            for neighbor, weight in graph.get(node, []):
                heapq.heappush(queue, (cost + weight, path + [neighbor]))

    return None, float('inf')

#A* Search Example
import heapq

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

    while queue:
        est_total, cost, path = heapq.heappop(queue)
        node = path[-1]

        if node == goal:
            return path, cost

        if node not in visited:
            visited.add(node)
            for neighbor, weight in graph.get(node, []):
                new_cost = cost + weight
                est = new_cost + heuristic.get(neighbor, 0)
                heapq.heappush(queue, (est, new_cost, path + [neighbor]))

    return None, float('inf')

Real-World Applications

Where AI Is Applied

Resources

Interview Questions with Answers