Uninformed Search Strategies

Graph BFS — finds shallowest solution

from collections import deque

def bfs(problem):
    node = Node(problem.initial)
    if problem.goal_test(node.state): return node
    frontier = deque([node])        # FIFO queue
    explored = set()
    while frontier:
        node = frontier.popleft()   # expand shallowest
        explored.add(node.state)
        for action in problem.actions(node.state):
            child = node.expand(problem, action)
            if child.state not in explored and child not in frontier:
                if problem.goal_test(child.state):
                    return child    # early goal test
                frontier.append(child)
    return None  # failure

Path cost g(n) — the sum of action costs along the path from start to node n.

Total nodes generated by IDDFS to reach depth d. For b=10, d=5: IDDFS generates only ~11% more nodes than BFS — a negligible overhead for the massive space savings.

Bidirectional complexity advantage. For b=10, d=10: BFS explores 10^10 nodes; bidirectional explores 2×10^5 — a 50,000× reduction.

1. What is the time and space complexity of BFS and when does space become the limiting factor? (Answer: BFS: time O(b^d), space O(b^d) where b = branching factor, d = depth of solution. Space stores all frontier nodes. Example: b=10, d=10: 10^10 = 10 billion nodes in memory — ~80GB. Space is almost always the limiting factor before time. Solution: IDDFS (Iterative Deepening DFS) achieves BFS optimality with DFS's O(bd) space — uses O(d) memory instead of O(b^d).)
2. What is the difference between BFS and uniform cost search? (Answer: BFS: expands nodes in order of path length (number of steps). Optimal only when all edges have equal cost. Uniform Cost Search (Dijkstra's): expands nodes in order of path COST (not steps). Optimal for any non-negative edge costs. BFS is a special case of UCS where all edges have cost 1. When edge costs vary (different route distances, different action costs), UCS finds the optimal cost solution; BFS finds the minimum-step solution (which may be expensive).)
3. What is the completeness property of DFS and under what conditions does DFS fail? (Answer: DFS is NOT complete in general: can enter infinite loops in graphs with cycles or infinite depth. DFS is complete for: finite graphs with cycle detection (visited set). DFS is complete for: finite trees. DFS is NOT complete for: infinite depth spaces (e.g., successor of state n is n+1 — DFS goes to infinity). Complete alternatives: BFS (always complete if solution exists), IDDFS (complete, memory-efficient).)
4. What is the difference between graph search and tree search in uninformed search algorithms? (Answer: Tree search: does not track visited nodes — may revisit states, potentially infinite loops in cyclic graphs. Space: O(bd). Suitable only for tree-structured problems or when revisiting is rare. Graph search: maintains a 'closed' set of visited nodes — never revisits. Guaranteed to terminate on finite graphs. Space: O(b^d) for BFS (frontier + closed set). Required for problems with cycles (route planning, grid worlds).)
5. What is bidirectional search and when does it provide a significant speedup? (Answer: Bidirectional search: run two simultaneous searches — one forward from start, one backward from goal. Stop when frontiers meet. Complexity: O(b^{d/2}) instead of O(b^d) — square root of unidirectional cost. For b=10, d=10: unidirectional needs 10^10 nodes; bidirectional needs 2×10^5 ≈ 200,000. Enormous speedup. Limitation: requires knowing the goal state and being able to compute predecessor states (backward operators). Works well for: route planning, word ladders, bidirectional A*.)