Uninformed Search Strategies Questions and Answers

Answer: C

Completeness is a guarantee about existence: if there is a solution the algorithm will find it, though possibly slowly. Exploring everything is one way to be complete but not the definition, returning the cheapest is optimality, and bounded time is a complexity claim. Keeping the four criteria separate matters because an algorithm may satisfy any subset of them, and a comparison table is only useful if each column means one thing.

Answer: D

Optimality concerns the quality of the solution returned, not the efficiency of the search, so an algorithm can be optimal and extremely slow, or fast and suboptimal. Efficiency in nodes expanded is sometimes called optimal efficiency, which is a different property and a frequent source of confusion. Distinguishing the quality of the answer from the cost of obtaining it is essential when reading any claim of optimality.

Answer: A

Both breadth first and iterative deepening find the shallowest goal, which with equal step costs is the cheapest, and uniform cost is optimal for any non-negative costs. Depth first and depth limited return whatever goal they stumble upon, which may be far from the best. Bidirectional inherits the properties of the strategies used in each direction. A table of which guarantees each strategy provides is worth constructing once and remembering. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

Answer: B

In a space where breadth first would exhaust memory in seconds, depth first needs only the current path, which is often the difference between an impossible search and a slow one. Backtracking search over constraint problems relies on it entirely. It is not optimal, ease of implementation is comparable, and it is incomplete in infinite spaces. When memory is the binding constraint, an algorithm's memory profile outweighs every other property it has. The quantity that varies and the quantity that does not are worth naming before any substitution is attempted.

Answer: C

Generating successors one at a time, and modifying the state in place rather than copying it, reduces the memory to a single state description plus the path, which is the standard implementation for constraint satisfaction. Undoing actions is how the state is restored rather than the definition, abandoned paths are not stored, and it is not bidirectional. Reducing memory from the branching factor times depth to depth alone is a further saving on an already frugal algorithm.

Answer: D

Each iteration is a depth first search, so the memory is the branching factor times the current limit, which is linear, and that is what makes the algorithm the default choice for large spaces. Its time complexity remains exponential like every uninformed strategy. The explored set of a graph search version would spoil it. Obtaining breadth first's guarantees at depth first's memory cost, for an eleven per cent time penalty, is close to a free lunch. Working one numerical case through both cases side by side fixes the distinction better than any rule of thumb.

Answer: A

Its combination of completeness, optimality with unit costs and linear memory suits exactly the case where the space is too large for breadth first and the depth is not known in advance. Varying costs call for uniform cost search, a small space admits anything, and a heuristic should be used if one exists, which moves the problem into informed search. Matching the algorithm to what is known about the problem is the practical content of the comparison table.

Answer: B

Uninformed strategies are defined by having no information beyond the problem definition, so a heuristic simply has no place in them. Introducing one moves the discussion to best first, greedy and A star search, which are the informed strategies. The question is worth asking because the distinction between the two families is exactly the availability of problem specific guidance, and it is the organising division of the whole search literature. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Answer: C

For many problems no useful heuristic is known, and the uninformed strategies then define what is achievable and provide the baseline against which any heuristic is measured. They also form the skeleton on which informed strategies are built, since A star is uniform cost with an added term. Speed, guarantees and code size are secondary. Understanding the case with no information is what allows the value of information to be quantified.

Answer: D

Both order the frontier by a cost, and A star uses the path cost so far plus an estimate of the cost remaining, so uniform cost is the special case where that estimate is always zero. Recognising the relationship shows why A star inherits uniform cost's optimality when the heuristic is admissible. Bidirectionality and inadmissibility are separate variations, and the two are not identical for unit costs. Seeing one algorithm as a special case of another organises the whole family.