Search Problem Formulation
What you'll learn: How to translate a messy real-world problem into a formal search problem that AI algorithms can solve.
The Core Idea
Imagine you're planning a road trip. In your mind, you're thinking about cities, highways, time, and money. But to use a GPS algorithm, you need to express this problem in a precise, mathematical way. Search problem formulation is the art of taking an informal problem ("get from A to B cheaply") and defining it formally using four key ingredients:
- States – What are all the possible situations you could be in? (e.g., "I'm in Chicago")
- Actions – What moves are available from each state? (e.g., "Drive to Milwaukee")
- Costs – What does each action cost? (e.g., $15 in gas, 90 minutes)
- Goals – What are you trying to achieve? (e.g., "Reach Seattle")
Why It Matters
Without proper formulation, search algorithms can't help you. The state space defines your "universe of possibilities," actions define how you navigate it, costs let you optimize, and goals tell you when you're done. Together, these create the scaffolding that sits between a vague human request and a concrete algorithmic solution.
Example
Problem: Solve a Rubik's Cube.
- States: Each unique configuration of colored squares (43 quintillion possibilities!)
- Actions: Rotate any face clockwise/counterclockwise
- Cost: Number of moves (usually uniform: 1 per rotation)
- Goal: The solved configuration where each face is one solid color
Key Takeaway: Search problem formulation transforms real-world challenges into a formal structure of states, actions, costs, and goals—enabling systematic algorithmic exploration of solutions.