2 Problem Solving and Search Free Online FlashCards

What five elements define a search problem?

The initial state, actions, transition model, goal test, and path cost.

What is the state space?

The set of states reachable by applying actions from the initial state.

When does breadth-first search find a fewest-action solution?

BFS explores shallowest paths first, typically using a queue. When all actions have equal cost, it finds a solution with the fewest actions, but may use substantial memory.

What does a heuristic $h(n)$ estimate?

A heuristic, written as $h(n)$, estimates the remaining cost from state $n$ to a goal.

What does a transition model specify?

It specifies the state that results from taking an action in a given state.

What counts as a solution to a search problem?

A path from the initial state to any state that passes the goal test.

How do path cost and the objective affect which solution is best?

Path cost is the total cost of the actions taken. The best solution depends on the objective, such as minimizing actions or total cost.

What does the frontier contain?

The frontier contains discovered states that have not yet been explored.

Why does graph search track explored states?

Graph search tracks explored states to avoid repeated visits, which is useful when different paths reach the same state or the problem contains cycles.

What are branching factor and depth, and why do they matter?

The branching factor is the typical number of successors per state; depth is the number of actions from the start. A large branching factor can make paths grow rapidly with depth.

How does depth-first search explore, and what is one limitation?

DFS follows one path as far as it can before backtracking. It can use less memory than BFS, but generally does not find the shortest or least-cost solution.

How does uniform-cost search choose which path to expand?

UCS expands the frontier path with the lowest cost so far, typically using a priority queue. With positive step costs and suitable search conditions, it finds a least-cost solution.