Chapter 2 · Watch, then practise
Problem Solving
Turn an informal goal into a search problem with a precise state, valid actions, transition rules, costs and a goal test.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- State representation
- Initial state and goal test
- Actions and transition model
- State graphs versus search trees
Chapter playlists
Choose a playlist
Notes
Lec-4: What is State Space Search | Introduction to Problem Solving in Artificial Intelligence
Gate Smashers · 10:47
The state-space and problem-solving lecture supports defining states, actions, goals and route costs.
1. Formulate a route problem
What defines a least-distance route problem between two cities?
States are cities; actions select roads; transitions move between cities; costs are road lengths. Set the initial city and test for the destination. A solution is an action sequence whose total cost sums the selected road lengths.
Lec-4: What is State Space Search | Introduction to Problem Solving in Artificial Intelligence
Gate Smashers · 10:47
State-space modeling is the matching topic; apply it to the additional information needed by the route constraints.
2. Choose enough state
When is current location an insufficient state description?
If a route must visit several delivery stops, the future choices depend on which stops remain. Include location and the remaining-stop set. Two visits to the same location with different unfinished stops are different search states; merging them would discard information needed to solve the task.
Lec-4: What is State Space Search | Introduction to Problem Solving in Artificial Intelligence
Gate Smashers · 10:47 · Background lecture
Choose a video · 2 lectures
State-space search and BFS provide context for repeated states. The titles do not verify the exact search-tree versus state-graph comparison.
3. Graph versus tree
Why can a search tree contain the same state more than once?
Tree nodes represent paths, so different action sequences can reach an identical state. A state graph represents that state once. Detecting repeated states can avoid redundant expansion, while cost-sensitive algorithms must still handle a cheaper newly discovered path correctly.