Problem Solving and Search (part 1: 2.1–2.4)
Open in the Padhaiko app2.1 Formal problem definition: States, actions, transitions, well-defined problems
A problem-solving agent is a goal-based agent that decides what to do by finding a sequence of actions leading to a desirable state. Before searching, it must formulate the goal and the problem formally.
Well-Defined Search Problem (Five Components)
A well-defined problem is specified formally by five components:
- Initial state (): The state in which the agent starts.
- Actions (): The set of legal actions available to the agent in state .
- Transition model (): Returns the state produced by performing action in state . Together, the initial state, actions, and transition model implicitly define the state space (a directed graph whose nodes are states and edges are actions).
- Goal test (): Determines whether a given state satisfies the goal condition (either an explicit set of goal states or an abstract property such as checkmate).
- Path cost (): Assigns a non-negative numerical cost to each step . The cost of a path is the sum of its step costs, and an optimal solution is a solution with minimum path cost among all solutions.
- Abstraction: Removing irrelevant real-world detail from state descriptions and actions so the search space stays tractable. For example, in route-finding from Kathmandu to Pokhara, weather and radio volume are ignored; only the current city and highway connections matter.
- Toy vs. real-world problems: Toy problems (8-puzzle, -queens, vacuum world) concisely test search methods; real-world problems (route finding, VLSI layout, robot navigation) have huge state spaces and uncertain costs.
| Problem | Initial State | Actions | Transition Model | Goal Test | Path Cost |
|---|---|---|---|---|---|
| Route finding (map) | Drive to an adjacent city | Sum of road distances () | |||
| 8-Puzzle | Any tile configuration | Slide blank | Swap blank with adjacent tile | Tiles in target order | per move |
| 8-Queens | Empty board (or queens placed) | Place a queen in column with no conflict | Add queen to board | queens placed, none attacking | (any solution is valid) |
| 2-Square Vacuum World | Agent in or , squares clean/dirty | , , | Moves agent or cleans current square | Both squares clean | per action |
2.2 Constraint satisfaction problems: Node consistency, path consistency, backtracking
Standard search treats each state as an indivisible black box. A Constraint Satisfaction Problem (CSP) uses a factored representation—a set of variables and constraints—which lets the solver prune impossible values early rather than waiting until a full assignment fails.
Constraint Satisfaction Problem (CSP)
A CSP is a triple where:
- is a finite set of variables.
- is a set of domains, one non-empty set of allowed values for each variable .
- is a set of constraints, each specified as where scope is a tuple of variables and rel defines the combinations of values they may take simultaneously.
An assignment is consistent if it violates no constraints, complete if every variable is assigned, and a solution if it is both consistent and complete.
Types of Constraints and Consistency
- Unary constraint: restricts one variable (e.g., ).
- Binary constraint: relates two variables (e.g., ). Represented as a constraint graph where nodes are variables and edges are binary constraints.
- Global constraint: involves an arbitrary number of variables, e.g., .
Inference (constraint propagation) shrinks domains before or during search:
Node, Arc, and Path Consistency
- Node consistency (1-consistency): A variable is node-consistent if every value in its domain satisfies all unary constraints on .
- Arc consistency (2-consistency): A variable is arc-consistent with respect to another variable if for every value , there exists at least one value such that satisfies the binary constraint between and . Enforced by the AC-3 algorithm in time ( constraints, max domain size ).
- Path consistency (3-consistency): A two-variable pair is path-consistent with respect to a third variable if, for every consistent assignment , there exists an assignment that is consistent with both and .
| Consistency Level | Scope Checked | Removes Inconsistent | Complexity / Strength |
|---|---|---|---|
| Node consistency | Single variable | Values violating unary constraints | Linear ; weakest |
| Arc consistency (AC-3) | Directed pair | Values in with no support in | ; detects many failures early |
| Path consistency (PC-2) | Triples | Consistent pairs lacking a valid third value | Stronger; narrows binary relations |
Backtracking Search for CSPs
Because variable assignment order is commutative, CSP search fixes one unassigned variable at a time, giving at most leaves instead of .
function BACKTRACK(assignment, csp):
if assignment is complete: return assignment
var = SELECT-UNASSIGNED-VARIABLE(csp, assignment) // MRV + Degree heuristic
for each value in ORDER-DOMAIN-VALUES(var, assignment, csp): // LCV heuristic
if value is consistent with assignment:
add {var = value} to assignment
inferences = INFERENCE(csp, var, value) // Forward checking or MAC
if inferences != failure:
add inferences to csp
result = BACKTRACK(assignment, csp)
if result != failure: return result
remove {var = value} and inferences from assignment / csp
return failureFour standard speed-ups in backtracking CSPs:
- Minimum Remaining Values (MRV / fail-first): pick the variable with the fewest legal values left.
- Degree heuristic (tie-breaker): pick the variable involved in the most constraints with unassigned variables.
- Least Constraining Value (LCV): try the value that rules out the fewest choices for neighbouring variables.
- Forward checking / MAC: when is assigned, delete incompatible values from unassigned neighbours' domains; if any domain becomes empty, backtrack immediately.
2.3 Search algorithms, strategies and evaluations
A search tree is built on the fly from the initial state (root) by expanding nodes using the transition model. Notice the distinction between a state (a configuration in the world) and a search node (a data structure storing state, parent, action, path-cost , and depth).
Frontier, Tree Search, and Graph Search
- Frontier (open list): the queue of generated leaf nodes waiting to be expanded.
- FIFO queue: Breadth-First Search.
- LIFO stack: Depth-First Search.
- Priority queue: Uniform-Cost, Best-First, and search.
- Explored set (closed list): stores already-expanded states in graph search so repeated states and infinite loops are avoided (whereas tree search can revisit states).
Four Criteria for Evaluating Search Strategies
Search Evaluation Metrics
Every search algorithm is evaluated on four standard criteria, using branching factor (max successors per node), shallowest goal depth , and maximum path length (which may be ):
- Completeness: Is the algorithm guaranteed to find a solution if at least one exists?
- Optimality: Does it guarantee finding the lowest-cost solution?
- Time complexity: How many nodes are generated/expanded in the worst case (expressed in )?
- Space complexity: How many nodes must stay in memory at once (size of frontier and explored set)?
2.4 Uninformed: BFS, DFS, iterative deepening
Uninformed (blind) search strategies have only the problem definition and no domain-specific clue about which non-goal state is closer to the goal.
Breadth-First Search (BFS)
- Strategy: Expand the shallowest unexpanded node first using a FIFO queue.
- Properties: Complete (if is finite). Optimal only when all step costs are equal (finds the shallowest goal at depth ).
- Complexity: If the goal is tested when a node is generated (or expanded), worst-case nodes are (or if tested at expansion in standard graph/tree formulation). Both time and space are (exponential memory!).
Depth-First Search (DFS)
- Strategy: Always expand the deepest node in the frontier using a LIFO stack (or recursion).
- Properties: Not complete in infinite-depth spaces or graphs with loops (unless cycle checking is used). Not optimal (may find a deep, costly goal first).
- Complexity: Time (poor when ), but space is only —linear in the maximum depth!
Iterative Deepening Depth-First Search (IDDFS / IDS)
- Strategy: Runs Depth-Limited Search (DLS) repeatedly with increasing depth limits until a goal is found.
- Why it works: Most nodes in a tree of depth lie at the bottom level, so regenerating upper levels adds little overhead while preserving DFS's linear memory!
| Criterion | BFS | DFS | Iterative Deepening (IDS) |
|---|---|---|---|
| Data structure | FIFO Queue | LIFO Stack / Recursion | Repeated Depth-Limited Stack |
| Complete? | Yes (if finite) | No (can loop or go to ) | Yes (if finite) |
| Optimal? | Yes (if unit step cost) | No | Yes (if unit step cost) |
| Time complexity | |||
| Space complexity | (exponential) | (linear) | (linear) |
| Best use case | Shallow goal, small | Memory tight, many goals | Large space, unknown goal depth |
Worked Out Examples
2.1
Consider a CSP with variables , domains , , , and binary constraints , , . Enforce node and arc consistency using AC-3 and find the reduced domains.
Node consistency: There are no unary constraints, so all domains remain unchanged: , , .
Arc with constraint : Since , value has no supporting value in ( is false), while and are supported by . Remove from , giving .
Arc with constraint : Value has no support in , while is supported. Remove from , giving .
Re-checking arc after shrunk: Now . For , there is no value in with ; for , holds. Remove from , leaving .
Remaining arcs: Checking removes nothing further (, , ), so the queue empties and AC-3 solves the CSP without any backtracking!
Reduced domains: , , (unique consistent assignment).
2.2
For a uniform search tree with branching factor and goal depth (assuming nodes at depth are counted as root, or counting generated non-root nodes ), compare the number of non-root nodes generated by BFS and IDS, and compute the ratio .
BFS non-root nodes generated up to depth :
IDS non-root nodes generated across depth limits : Nodes at depth are regenerated times:
Overhead ratio:
BFS generates non-root nodes; IDS generates nodes, an overhead of only (ratio ) while using linear memory.
2.3
Consider a directed search graph with start node , goal , and alphabetical successor lists: , , , , , . Trace the order of expanded nodes for (a) Graph BFS and (b) Graph DFS (pushing right-to-left so alphabetical order is popped first), stopping as soon as is expanded.
Graph BFS (FIFO queue, goal tested on expansion):
- Start: Frontier . Pop , expand Frontier .
- Pop , expand Frontier .
- Pop , expand Frontier .
- Pop , expand Frontier .
- Pop (no new nodes) Frontier .
- Pop ( already in explored/frontier) Frontier .
- Pop (goal reached!). Expanded order: . Path: (depth ).
Graph DFS (LIFO stack, alphabetical pop priority):
- Start: Stack . Pop , push then Stack (top on right).
- Pop , push then Stack .
- Pop , push Stack .
- Pop (goal reached!). Expanded order: . Path: .
BFS expands (7 expansions, finds path ); DFS expands (4 expansions, finds path ).
Exercises
Exercise: Problem Formulation, CSPs, and Uninformed Search
Define the five components of a well-defined search problem and formulate the 8-puzzle problem formally using them.
Five components: (1) Initial state, (2) Actions available at each state, (3) Transition model , (4) Goal test, and (5) Step/path cost function.
8-puzzle formulation:
- States: Any arrangement of the numbered tiles and blank space in a grid.
- Initial state: The given starting tile configuration.
- Actions: Move the blank , , , or (when valid inside the grid).
- Transition model: Swaps the blank with the adjacent tile in the chosen direction.
- Goal test: Checks whether the grid matches the target arrangement (e.g., in order with the blank at the corner/end).
- Path cost: Each move costs , so total path cost equals the number of moves.
A well-defined problem has initial state, actions, transition model, goal test, and path cost. For the 8-puzzle, states are tile boards, actions slide the blank in four directions, transitions swap the blank with an adjacent tile, the goal test checks target tile order, and each step costs .
A uniform search tree has branching factor and a goal at depth . How many total nodes (including the root at depth ) exist up to depth ? Also compare non-root nodes generated by BFS vs. IDS up to depth .
Total nodes up to depth (including root):
Non-root nodes generated by BFS:
Non-root nodes generated by IDS ():
Total nodes (including root) . BFS generates non-root nodes; IDS generates non-root nodes (an overhead of ).
Differentiate between node consistency, arc consistency, and path consistency in CSPs, and explain the MRV and LCV heuristics in backtracking search.
Consistency levels: Node consistency removes domain values violating unary constraints on a single variable; arc consistency removes values in that have no valid partner in under binary constraints; path consistency ensures every consistent pair can be extended consistently to any third variable .
Heuristics: MRV (Minimum Remaining Values) selects the unassigned variable with the fewest legal values left (fail-first, shrinking the branching factor early). LCV (Least Constraining Value) orders values of the chosen variable to try first the value that eliminates the fewest choices from neighbouring variables (leaving maximum flexibility to succeed).
Node consistency enforces 1-variable unary constraints, arc consistency enforces binary support between pairs, and path consistency enforces 3-variable consistency on pairs. MRV chooses the most constrained variable first; LCV tries the value that restricts neighbours least.
Consider a CSP with variables having domains , , , and constraints and . Enforce arc consistency and determine whether a solution exists.
Check arc with : is supported by ; is supported by . So .
Check arc with : For , satisfies . For and , there is no with . Thus and are pruned from , leaving .
Propagate to with : Neither nor in satisfies . Hence becomes (empty!).
Arc consistency reduces to , proving immediately that no solution exists.
Compare Breadth-First Search, Depth-First Search, and Iterative Deepening Search on completeness, optimality, time complexity, and space complexity. Why is IDS preferred over BFS when memory is limited?
Comparison: BFS is complete and optimal (for unit step costs), with time and space. DFS is neither complete (in infinite/cyclic spaces without cycle checks) nor optimal, with time and space. IDS is complete and optimal (unit cost), with time and space.
Why IDS is preferred: BFS stores the entire frontier of size , which exhausts RAM quickly for moderate and . IDS keeps only the current path of nodes in memory while repeating upper levels at a small constant factor of extra time.
BFS takes time and space (complete, optimal for unit cost); DFS takes time and space (incomplete, non-optimal); IDS combines BFS's completeness and optimality with DFS's linear memory at time.