2 Search fundamentals

This chapter introduces planning and searching as core behaviors of intelligent systems: we form plans, then adapt them as reality changes, using search to choose and revise the next best steps toward our goals. Search is framed as evaluating possible future states to reach a target efficiently, with an emphasis on why “smart” algorithms matter: computational cost grows quickly with naive exploration, so understanding Big O complexity and avoiding brute force is essential. The text also clarifies what kinds of problems fit search—any task requiring a sequence of decisions—illustrated with maze pathfinding, and stresses that good algorithms aim for optimal or at least high-quality solutions under real-world constraints.

A major focus is representing problem spaces so computers can process them consistently and efficiently. The chapter distinguishes data (raw facts) from information (interpreted, contextualized facts), then surveys data structures that enable effective search. Graphs model states (nodes) and transitions (edges, possibly weighted), and can be encoded in several concrete forms (edge lists, matrices, adjacency lists) to support different performance needs. Trees—connected, acyclic structures—capture solution paths with concepts like root, parent/child, depth, height, leaves, and path cost. Rather than constructing the full tree of possibilities upfront, search algorithms generate and traverse these structures incrementally to keep computation tractable.

Two uninformed (“blind”) search strategies are developed. Breadth-first search uses a FIFO queue to expand all nodes at a given depth before moving deeper; on unweighted graphs it guarantees the shortest path but can be memory intensive. Depth-first search uses a LIFO stack to dive along one branch before backtracking; it is memory efficient but not guaranteed to find the shortest route. Both rely on tracking visited states to avoid cycles. The chapter closes with practical applications—network routing, web crawling, and social connectivity—and a brief tour of graph categories (directed/undirected, acyclic, complete, weighted) and representations, reinforcing how the choice of model and algorithm shapes efficiency and solution quality.