2 Search and Problem Solving Free Online FlashCards

What components define a search problem?

A state space, actions, transition model, action costs, a start state, and a goal test.

What is a plan in search?

A plan is a sequence of actions that takes the agent from the start state to a goal state.

What information should a search state retain?

A state must preserve enough information to determine possible actions and whether the goal is reached, while excluding irrelevant details.

How does a search tree differ from a state-space graph?

A state-space graph has states as nodes and actions as edges. A search tree represents candidate paths, so one state can appear more than once.

What is the frontier in a search algorithm?

The frontier holds discovered paths that have not yet been expanded. Graph search also tracks reached states to avoid repeatedly exploring cycles.

How does breadth-first search choose a path to expand?

BFS expands the shallowest path first, typically using a first-in, first-out queue. It finds a shortest-action solution when all actions have equal cost.

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

DFS expands the deepest path first, typically using a last-in, first-out stack. It can follow cycles or unbounded paths and does not guarantee the least-cost solution.

How does uniform-cost search select a path?

UCS expands the path with the lowest accumulated cost. It is useful when action costs vary and a least-cost solution is needed.

What does a heuristic estimate?

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

How does greedy best-first search choose a state?

Greedy best-first search expands the state with the smallest heuristic estimate, $h(n)$. It is not generally optimal.

What cost estimate does A* use to prioritize states?

A* expands the state with the smallest estimated total cost: $f(n) = g(n) + h(n)$, where $g(n)$ is cost so far and $h(n)$ estimates remaining cost.

What makes a heuristic admissible, and what else may A* require?

An admissible heuristic never overestimates the true remaining cost. For graph search, A*'s usual optimality guarantee also requires consistency or suitable handling of improved paths.