Informed and Heuristic Search Questions and Answers

Q: What is the state of a local search algorithm at any moment?

Local search holds one complete configuration and moves to a neighbouring one, so its memory is a single state whatever the size of the space. That is quite unlike the systematic methods, which build partial paths and remember frontiers. The contrast between searching among partial solutions and among complete ones is the deepest division in this subject and it determines both the memory profile and the guarantees available.

Q: What is a neighbour in local search?

The neighbourhood is defined by the move operator, such as changing one variable or swapping two elements, and choosing it well is as important as choosing the algorithm. A larger neighbourhood escapes more local optima but costs more to evaluate. Similar values, graph adjacency in the systematic sense and visited states are different notions. The move set defines the landscape, so redesigning it is often the most effective response to a search that gets stuck.

Q: How does the choice of neighbourhood affect a local search?

Enlarging the move set flattens the landscape by connecting states that were previously far apart, so fewer configurations are locally optimal, but every step requires more evaluations. Compound moves and variable neighbourhood search exploit the trade deliberately. Smaller neighbourhoods are cheaper rather than better, the effect is large rather than absent, and termination depends on the acceptance rule. Reshaping the landscape by changing the moves is a lever unavailable in systematic search.

Q: What is the objective function in a local search problem?

Local search evaluates each complete state by an objective and moves towards better values, so the objective plays the role that both the path cost and the heuristic play in systematic search. Constraint counts are one common choice of objective in satisfaction problems. Path cost is meaningless when no path is kept. Recognising that the objective does all the work, and that its shape is the landscape, focuses attention where the difficulty actually lies.

Q: What is tabu search?

Keeping a short list of recently visited configurations and refusing to return to them forces the search out of a local optimum and prevents immediate cycling. The list length controls how far it is driven. Constraint violation, branch pruning and restricted spaces describe other techniques. Using a memory of where the search has been, in a method that otherwise keeps no history, is a modest addition that addresses the characteristic failure directly.

Q: Why does a tabu list prevent cycling?

Once hill climbing is forced downhill out of a local optimum, the natural next move is straight back up, and forbidding the recently visited states blocks exactly that. Only a short window need be remembered, which keeps the memory constant. Storing everything would be expensive, worsening moves are precisely what is being permitted, and no region is fixed. A small bounded memory that addresses one specific failure is a better answer than an unbounded one that addresses it incidentally.

Q: What is the aspiration criterion in tabu search?

Forbidding a move that would reach the best configuration found so far is plainly counterproductive, so the tabu status is overridden in that case. It is a small exception that prevents the memory from doing harm. Target values, move ranking and list clearing are different mechanisms. A rule that suspends a general restriction when the restriction would obviously be wrong is a pattern worth recognising, since blanket prohibitions usually need one.

Q: What is the general lesson of local search methods?

By keeping one complete state rather than a frontier, local search operates in spaces far too large for any systematic method, and pays for it by abandoning completeness and optimality. It applies only where the path is irrelevant. The objective and the neighbourhood matter more than the choice among the algorithms, which is the opposite of the last option. Knowing what each family can and cannot do, rather than preferring one, is what allows the right one to be selected.

Q: When should systematic search be preferred to local search?

If the sequence of actions is what the user needs, or a provably best answer is required, only a systematic method will do. Large spaces, expensive objectives and rugged landscapes all argue for local search instead. The decision follows from what the problem requires rather than from any property of the algorithms, which is why it should be made when the problem is formulated rather than when the code is written.

81.

Which algorithm minimises the sum of both cost terms?

A.Greedy best first search
B.Depth first search
C.Uniform cost search
D.A star search

Answer: D

A star adds the cost so far to the estimate of the cost remaining, so it minimises an estimate of the total rather than either half, and that is what gives it optimality with an admissible heuristic. Greedy uses h alone, uniform cost g alone, and depth first neither. The family is completely described by which terms each member uses, which is the most compact way of holding it in mind.

Discuss in Forum

82.

What is the state of a local search algorithm at any moment?

A.A single complete candidate solution
B.A partial path from the start towards the goal
C.A frontier of nodes awaiting expansion
D.A tree of every state visited so far

Answer: A

Local search holds one complete configuration and moves to a neighbouring one, so its memory is a single state whatever the size of the space. That is quite unlike the systematic methods, which build partial paths and remember frontiers. The contrast between searching among partial solutions and among complete ones is the deepest division in this subject and it determines both the memory profile and the guarantees available.

Discuss in Forum

83.

What is a neighbour in local search?

A.A state that has already been visited by the search
B.A state reachable by one small modification of the current one
C.A state adjacent to the current one in the state space graph
D.A state with a similar value of the objective function

Answer: B

The neighbourhood is defined by the move operator, such as changing one variable or swapping two elements, and choosing it well is as important as choosing the algorithm. A larger neighbourhood escapes more local optima but costs more to evaluate. Similar values, graph adjacency in the systematic sense and visited states are different notions. The move set defines the landscape, so redesigning it is often the most effective response to a search that gets stuck.

Discuss in Forum

84.

How does the choice of neighbourhood affect a local search?

A.The neighbourhood has no effect provided the objective is correct
B.Neighbourhood size determines whether the search terminates
C.A larger neighbourhood escapes more local optima but costs more
D.A smaller neighbourhood always produces better final solutions

Answer: C

Enlarging the move set flattens the landscape by connecting states that were previously far apart, so fewer configurations are locally optimal, but every step requires more evaluations. Compound moves and variable neighbourhood search exploit the trade deliberately. Smaller neighbourhoods are cheaper rather than better, the effect is large rather than absent, and termination depends on the acceptance rule. Reshaping the landscape by changing the moves is a lever unavailable in systematic search.

Discuss in Forum

85.

What is the objective function in a local search problem?

A.The path cost accumulated from the initial configuration
B.The heuristic estimate of the distance to the goal
C.The number of constraints the current state satisfies
D.The quantity being maximised or minimised over states

Answer: D

Local search evaluates each complete state by an objective and moves towards better values, so the objective plays the role that both the path cost and the heuristic play in systematic search. Constraint counts are one common choice of objective in satisfaction problems. Path cost is meaningless when no path is kept. Recognising that the objective does all the work, and that its shape is the landscape, focuses attention where the difficulty actually lies.

Discuss in Forum

86.

What is tabu search?

A.Local search forbidding recently visited states for a period
B.Local search that avoids states failing a hard constraint
C.A search that marks unpromising branches as forbidden
D.A search restricted to a permitted subset of the state space

Answer: A

Keeping a short list of recently visited configurations and refusing to return to them forces the search out of a local optimum and prevents immediate cycling. The list length controls how far it is driven. Constraint violation, branch pruning and restricted spaces describe other techniques. Using a memory of where the search has been, in a method that otherwise keeps no history, is a modest addition that addresses the characteristic failure directly.

Discuss in Forum

87.

Why does a tabu list prevent cycling?

A.It restricts the search to a fixed region of the space
B.A state just left cannot immediately be returned to
C.The list stores every state the search has ever visited
D.It forbids moves that would worsen the objective function

Answer: B

Once hill climbing is forced downhill out of a local optimum, the natural next move is straight back up, and forbidding the recently visited states blocks exactly that. Only a short window need be remembered, which keeps the memory constant. Storing everything would be expensive, worsening moves are precisely what is being permitted, and no region is fixed. A small bounded memory that addresses one specific failure is a better answer than an unbounded one that addresses it incidentally.

Discuss in Forum

88.

What is the aspiration criterion in tabu search?

A.Moves are ranked by how much they improve the objective
B.The tabu list is cleared whenever no move is permitted
C.A tabu move is allowed if it produces the best state yet seen
D.The search aspires to a target objective value before stopping

Answer: C

Forbidding a move that would reach the best configuration found so far is plainly counterproductive, so the tabu status is overridden in that case. It is a small exception that prevents the memory from doing harm. Target values, move ranking and list clearing are different mechanisms. A rule that suspends a general restriction when the restriction would obviously be wrong is a pattern worth recognising, since blanket prohibitions usually need one.

Discuss in Forum

89.

What is the general lesson of local search methods?

A.Local methods find optimal solutions more often than systematic ones
B.Local search applies to every problem that systematic search does
C.The objective function matters less than the algorithm chosen
D.Constant memory is achievable when the path is not needed

Answer: D

By keeping one complete state rather than a frontier, local search operates in spaces far too large for any systematic method, and pays for it by abandoning completeness and optimality. It applies only where the path is irrelevant. The objective and the neighbourhood matter more than the choice among the algorithms, which is the opposite of the last option. Knowing what each family can and cannot do, rather than preferring one, is what allows the right one to be selected.

Discuss in Forum

90.

When should systematic search be preferred to local search?

A.When the path is part of the answer or optimality is required
B.When the state space is very large and cannot be enumerated
C.When the objective function is expensive to evaluate
D.When the problem has many local optima in its landscape

Answer: A

If the sequence of actions is what the user needs, or a provably best answer is required, only a systematic method will do. Large spaces, expensive objectives and rugged landscapes all argue for local search instead. The decision follows from what the problem requires rather than from any property of the algorithms, which is why it should be made when the problem is formulated rather than when the code is written.

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