Informed and Heuristic Search Questions and Answers

Q: Why do random restarts sometimes fail even after many attempts?

If the global optimum is reached from only a tiny fraction of starting points, the expected number of restarts becomes impractically large however cheap each one is. Methods that cross between basins, such as annealing or crossover, are then needed. Starting points are random by construction, climbing reaches some optimum every time, and the objective is fixed. Estimating the probability of success per attempt is what turns a hopeful strategy into a calculable one.

Q: What is a rugged landscape?

Ruggedness means the objective varies sharply with small changes of state, so local optima are numerous and each basin is small, which defeats simple hill climbing and often restarts as well. A flat landscape is the opposite extreme and is equally unhelpful. Evaluation noise and boundary optima are different difficulties. Characterising the landscape before choosing a method, even roughly by sampling, is far more informative than choosing by reputation.

Q: How can the ruggedness of a landscape be reduced?

Ruggedness is a property of the objective together with the move set, so connecting more states by each move, or encoding the problem so that related configurations are neighbours, smooths it. Restarts cope with ruggedness rather than reducing it. Evaluation accuracy and space size are separate matters. Recognising that the landscape is created jointly by the problem and by the designer's choices is what makes it something that can be improved rather than merely endured.

Q: What is the most important decision in applying local search?

The representation and the moves together define the landscape, and a well shaped landscape makes almost any method work while a badly shaped one defeats all of them. Choosing among the algorithms matters far less. Iteration counts and starting points are parameters within a given formulation. Spending effort on the formulation rather than on the choice of algorithm is the consistent advice of practitioners and it follows directly from what determines the landscape.

Q: What is the overall structure of the search chapter of the subject?

The progression runs from search with no information, through search guided by a heuristic, to search that abandons paths entirely in exchange for constant memory. Each step trades a guarantee for a resource saving, and knowing which guarantee has been given up is what allows the right method to be chosen. Adversarial search and constraint satisfaction follow as specialisations. A sequence organised by what is surrendered at each stage is easier to hold than one organised by algorithm names.

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.

91.

Why do random restarts sometimes fail even after many attempts?

A.Hill climbing cannot reach any optimum in a rugged landscape
B.The objective function changes between successive restarts
C.The basin of the global optimum may be extremely small
D.Restarts always begin from the same initial configuration

Answer: C

If the global optimum is reached from only a tiny fraction of starting points, the expected number of restarts becomes impractically large however cheap each one is. Methods that cross between basins, such as annealing or crossover, are then needed. Starting points are random by construction, climbing reaches some optimum every time, and the objective is fixed. Estimating the probability of success per attempt is what turns a hopeful strategy into a calculable one.

Discuss in Forum

92.

What is a rugged landscape?

A.One in which the objective cannot be evaluated exactly
B.One whose global optimum lies at the edge of the space
C.One in which every state has the same objective value
D.One with many local optima separated by deep valleys

Answer: D

Ruggedness means the objective varies sharply with small changes of state, so local optima are numerous and each basin is small, which defeats simple hill climbing and often restarts as well. A flat landscape is the opposite extreme and is equally unhelpful. Evaluation noise and boundary optima are different difficulties. Characterising the landscape before choosing a method, even roughly by sampling, is far more informative than choosing by reputation.

Discuss in Forum

93.

How can the ruggedness of a landscape be reduced?

A.By enlarging the neighbourhood or changing the representation
B.By evaluating the objective function more accurately
C.By increasing the number of random restarts performed
D.By reducing the size of the state space being searched

Answer: A

Ruggedness is a property of the objective together with the move set, so connecting more states by each move, or encoding the problem so that related configurations are neighbours, smooths it. Restarts cope with ruggedness rather than reducing it. Evaluation accuracy and space size are separate matters. Recognising that the landscape is created jointly by the problem and by the designer's choices is what makes it something that can be improved rather than merely endured.

Discuss in Forum

94.

What is the most important decision in applying local search?

A.The initial state from which the search begins
B.The choice of representation and move operator
C.The choice between annealing and genetic algorithms
D.The number of iterations allowed before termination

Answer: B

The representation and the moves together define the landscape, and a well shaped landscape makes almost any method work while a badly shaped one defeats all of them. Choosing among the algorithms matters far less. Iteration counts and starting points are parameters within a given formulation. Spending effort on the formulation rather than on the choice of algorithm is the consistent advice of practitioners and it follows directly from what determines the landscape.

Discuss in Forum

95.

What is the overall structure of the search chapter of the subject?

A.Optimisation, then satisfaction, then planning problems
B.Deterministic methods, then stochastic, then adversarial
C.Uninformed methods, then informed methods, then local methods
D.Local methods, then heuristics, then complete enumeration

Answer: C

The progression runs from search with no information, through search guided by a heuristic, to search that abandons paths entirely in exchange for constant memory. Each step trades a guarantee for a resource saving, and knowing which guarantee has been given up is what allows the right method to be chosen. Adversarial search and constraint satisfaction follow as specialisations. A sequence organised by what is surrendered at each stage is easier to hold than one organised by algorithm names.

Discuss in Forum

96.

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

97.

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

98.

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

99.

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

100.

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

Loading…

Topics

Other Subjects

Tags: Informed and Heuristic Search Questions and Answers || Informed and Heuristic Search MCQ Questions and Answers || Informed and Heuristic Search GK Questions and Answers || Informed and Heuristic Search GK MCQ Questions || Informed and Heuristic Search Multiple Choice Questions and Answers || Informed and Heuristic Search GK || GK on Informed and Heuristic Search || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Informed and Heuristic Search Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications