Uninformed Search Strategies Questions and Answers

Answer: C

A space with n states has two to the n subsets, so the belief space is exponentially larger even before probabilities are introduced. Compact representations and approximations are used in practice. Probabilities appear only in the probabilistic version, successor counts are comparable, and the goal test simply requires every state in the belief to be a goal. An exponential increase in the size of the space is the price of removing an assumption, and it is worth knowing before the assumption is removed.

Answer: D

The goal test is applied to a state and answers yes or no, and it may check a specific configuration or an abstract property such as checkmate. Node selection is the frontier discipline, cost accumulation is the path cost function and successor generation is the transition model. Keeping the five components of a problem distinct is what allows the same algorithm to be applied to problems that look nothing alike.

Answer: A

The initial state is where the agent actually is, and it becomes the root of the search tree. It coincides with the first node expanded but is a property of the problem rather than of the algorithm. Convenience of reaching the goal and empty states are not the definition. Distinguishing components of the problem from steps of the algorithm is a habit that keeps discussions of search precise.

Answer: B

Expansion applies the transition model to produce every successor, creates a node for each and places them on the frontier, and the count of expansions is the usual measure of search effort. Goal testing and cost computation accompany it, and simple removal would discard the node's information. Measuring effort by expansions rather than by wall clock time makes comparisons between algorithms independent of the machine.

Answer: C

Counting expansions gives a measure that does not change with processor speed, programming language or coding style, so published comparisons remain meaningful. Wall clock time still matters in practice and both are usually reported. Generation, testing and frontier management are also performed, and memory follows the frontier rather than the expansions. Choosing a machine independent measure is what allows results from different laboratories and decades to be compared at all.

Answer: D

A node is generated when it is created as a successor and expanded when its own successors are produced, and many generated nodes are never expanded because the search finishes first. The distinction matters for complexity analysis, since generation counts are larger. Ownership, goal testing and cost are separate concerns. Precise vocabulary for two closely related operations is worth maintaining because complexity claims depend on which is being counted.

Answer: A

Since every path of the same length costs the same, the first time a goal is generated it is already at minimum depth and therefore minimum cost, so testing early saves an entire level of expansion. Uniform cost cannot do this because a cheaper route may still be on the frontier. Cost ordering, the explored set and frontier arrangement are not the reason. A saving available only under a stated condition must carry that condition with it. The shared properties explain why these belong to one family, and the differences explain why more than one exists.

Answer: B

Finding the goal as soon as it is generated avoids expanding the remainder of its level, which in an exponential tree is most of the work done so far. It is safe for breadth first with equal costs and unsafe for uniform cost search. Completeness, memory and expansion order are unaffected. A constant factor saving of roughly the branching factor is worth having, provided the condition under which it is sound is respected.

Answer: C

Given the nodes generated and the solution depth, the effective branching factor is the value that would produce that many nodes in a uniform tree of that depth, and it is the standard way of comparing heuristics. A value near one indicates an excellent heuristic. The average legal action count is the raw branching factor, and the other options describe extremes and graph search effects. Summarising a search's efficiency in a single interpretable number is what makes the measure useful.

Answer: D

An effective branching factor near one means the search expanded almost a straight line to the goal, which is what a near perfect heuristic achieves. A value equal to the raw branching factor means no guidance at all, and a value above it would indicate the search was actively misled. Depth is a separate quantity. A measure whose ideal value is one and whose unguided value is the raw branching factor is easy to interpret at a glance, which is precisely what a summary statistic should be.