Solving Problems by Searching Flashcards
(12 cards)
What is a problem-solving agent?
An agent that plans a sequence of actions to reach a goal state when the correct action isn’t immediately obvious.
Example: Finding a route from home to SDU (Slide 4).
What are the components of a search problem?
- Initial state
- Goal state
- Successor function
- Path cost
What is the state space?
The set of all states reachable from the initial state via the successor function — often visualized as a graph
What is an optimal solution?
A sequence of actions that leads to the goal with the lowest total path cost
What type of agent uses search?
A goal-based agent operating in an observable, deterministic, discrete, and known environment
What is the fringe in tree search?
The list of unexpanded nodes — the frontier of the search
What’s the difference between a node and a state?
A state represents a configuration in the problem, while a node is a data structure in the search tree that contains the state, path, and cost
What are the four evaluation metrics for search strategies?
- Completeness – Will it find a solution if one exists?
- Optimality – Will it find the best (least-cost) solution?
- Time complexity – How long does it take?
- Space complexity – How much memory does it use?
How does Breadth-First Search (BFS) work?
Expands the shallowest nodes first using a FIFO queue.
Properties: Complete, optimal if cost = 1, time/space = O(b^d)
How does Uniform-Cost Search (UCS) work?
Expands the least-cost node first using a priority queue ordered by path cost.
Properties: Complete, optimal, time/space = O(b^(1 + C*/ε))
How does Depth-First Search (DFS) work?
Expands the deepest node first using a LIFO stack.
Properties: Not complete (in infinite trees), not optimal, space = O(bm)
What is Iterative Deepening Search (IDS)?
Combines DFS with increasing depth limits to maintain completeness and low memory use.
Properties: Complete, optimal if cost = 1, time = O(b^d), space = O(bd)
