Informed and Heuristic Search Questions and Answers

Q: What single question decides between the search families?

If a heuristic is available, informed search should be used; if the path is not needed, local search should be considered; if optimality must be proved, the systematic methods are required. Prior experience and hardware inform the choice but do not decide it, and language features are irrelevant. Asking what information exists and what guarantee is needed, before considering any algorithm, is the same discipline the agent framework applies to design as a whole.

Q: What does adversarial search add to the framework?

In a game the successor states are chosen alternately by two agents with opposed objectives, so the value of a state depends on assuming the opponent plays well, which gives minimax rather than simple minimisation. Uncertainty, constraints and deadlines are the additions that produce other specialisations. Identifying exactly what each specialisation adds to the basic framework makes the whole family comprehensible as variations on one theme.

Q: What does constraint satisfaction add to the framework?

A constraint problem uses a factored representation, so the algorithm can reason about which assignments are inconsistent and prune enormous regions without enumerating them. That is precisely the advantage a factored representation buys. Opponents, costs and path length belong to other variants. Noticing that the gain comes from the representation rather than from the algorithm connects this specialisation back to the discussion of atomic and factored states.

Q: Why can constraint satisfaction algorithms outperform general search?

Because states are described by variables, an algorithm can detect that a partial assignment is already inconsistent and prune every completion of it at once, which an atomic representation cannot express. Heuristics such as most constrained variable are a further benefit of the same structure. The space is the same, and exact solutions are returned. The lesson that representation determines what can be exploited, established early in the subject, pays off concretely here.

101.

What single question decides between the search families?

A.Which algorithm has performed best on similar problems before
B.How much computing power is available for the search
C.Whether the implementation language supports recursion
D.What is known about the problem and what must be guaranteed

Answer: D

If a heuristic is available, informed search should be used; if the path is not needed, local search should be considered; if optimality must be proved, the systematic methods are required. Prior experience and hardware inform the choice but do not decide it, and language features are irrelevant. Asking what information exists and what guarantee is needed, before considering any algorithm, is the same discipline the agent framework applies to design as a whole.

Discuss in Forum

102.

Why is the study of search foundational to the wider subject?

A.Planning, games and constraint problems are all search problems
B.Every artificial intelligence system contains a search algorithm
C.Search is the only technique that can be analysed formally
D.Search problems are the only ones with provable solutions

Answer: A

Adversarial games, constraint satisfaction, classical planning and much of automated reasoning are formulated as search over a space of states or of partial solutions, so the vocabulary and the analysis transfer directly. Not every system searches, other techniques are equally analysable, and provability is not confined to search. A framework that recurs across several apparently distinct subfields is worth mastering once rather than relearning in each disguise.

Discuss in Forum

103.

What does adversarial search add to the framework?

A.A requirement that the solution be found in real time
B.An opponent choosing actions to minimise the agent's score
C.A probability distribution over the outcomes of actions
D.A constraint that every action must satisfy to be legal

Answer: B

In a game the successor states are chosen alternately by two agents with opposed objectives, so the value of a state depends on assuming the opponent plays well, which gives minimax rather than simple minimisation. Uncertainty, constraints and deadlines are the additions that produce other specialisations. Identifying exactly what each specialisation adds to the basic framework makes the whole family comprehensible as variations on one theme.

Discuss in Forum

104.

What does constraint satisfaction add to the framework?

A.Costs attached to each action taken during the search
B.A requirement that the solution path be as short as possible
C.States described by variables that must satisfy stated constraints
D.An opponent acting against the interests of the searcher

Answer: C

A constraint problem uses a factored representation, so the algorithm can reason about which assignments are inconsistent and prune enormous regions without enumerating them. That is precisely the advantage a factored representation buys. Opponents, costs and path length belong to other variants. Noticing that the gain comes from the representation rather than from the algorithm connects this specialisation back to the discussion of atomic and factored states.

Discuss in Forum

105.

Why can constraint satisfaction algorithms outperform general search?

A.They use better heuristics than general search algorithms
B.They search a smaller state space than the general formulation
C.They are permitted to return approximate solutions
D.They exploit the structure of the variable representation

Answer: D

Because states are described by variables, an algorithm can detect that a partial assignment is already inconsistent and prune every completion of it at once, which an atomic representation cannot express. Heuristics such as most constrained variable are a further benefit of the same structure. The space is the same, and exact solutions are returned. The lesson that representation determines what can be exploited, established early in the subject, pays off concretely here.

Discuss in Forum

Informed and Heuristic Search Questions and Answers

Topics

Other Subjects

About Us

Informed and Heuristic Search Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications