- 2071 Bhadra · 3+4 marks
Well defined problem, state-space search
Short answer
A problem is well defined when it has initial state, operators/successor function, goal test, and path cost; these define the state space. Example: 8-puzzle, with state as tile positions, operators moving blank, goal test matching goal board, path cost 1 per move.
What makes a problem "Well Defined"? Explain with a sample example of a state-space search framework.
What makes a problem well defined?
A problem is well defined when it is specified precisely enough for a program to solve it. It needs four components (Russell and Norvig):
- Initial state: where the agent starts.
- Operators / successor function: the actions available and the states they lead to.
- Goal test: a way to check whether a state is a goal (explicit set of states or an abstract property).
- Path cost: a numeric cost for each path (e.g. sum of step costs). A solution is a path from the initial state to a goal state; the best solution has the lowest path cost.
The initial state and operators together define the state space, the set of all states reachable from the start, which forms a graph (nodes = states, edges = actions).
State-space search example: the 8-puzzle
A 3 x 3 board has tiles 1-8 and one blank. Tiles next to the blank can slide into it.
| Component | 8-puzzle |
|---|---|
| State | Location of each tile and the blank (9!/2 = 181,440 reachable states) |
| Initial state | Any given arrangement, e.g. below left |
| Operators | Move blank Up, Down, Left, Right (if legal) |
| Goal test | Board equals the goal arrangement |
| Path cost | 1 per move; total cost = number of moves |
Initial Goal
2 8 3 1 2 3
1 6 4 --> 8 _ 4
7 _ 5 7 6 5
Search framework: start at the root (initial state), generate successors using the operators, put them on a frontier, pick a node using a strategy (BFS, DFS, A*), test the goal, and repeat. The sequence of moves along the path to the goal is the solution.
[2 8 3 / 1 6 4 / 7 _ 5]
/ | \
blank up blank left blank right ...
[2 8 3/1 _ 4/ ...] [... ] [... ]
Another well-defined problem is route finding: states = cities, operators = roads, goal = destination, cost = distance.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Problem space; BASE+BALL=GAMES · Artificial Intelligence, chapter 2
- Sample space, event, outcome definitions · Probability and Statistics, chapter 1
- Pattern vs framework; GRASP patterns · Object Oriented Analysis and Design, chapter 3
- Gel/space ratio and strength (550 gm cement) · Concrete Technology and Masonry Structure, chapter 4 · asked 3×
- Gel/space ratio and strength (600 gm cement) · Concrete Technology and Masonry Structure, chapter 4 · asked 3×