Informed and Heuristic Search Questions and Answers

Q: What is the weakness shared by iterative deepening A star and recursive best first search?

Both use linear memory and therefore forget almost everything, so a node may be regenerated many times over. Algorithms that use whatever memory is available, such as the bounded memory variants, sit between the extremes. Both are optimal with an admissible heuristic, both use far less memory than A star, and cycles are handled by ordinary means. The tension between remembering to avoid rework and forgetting to save memory is the organising theme of the whole family.

Q: What does a memory bounded A star variant do when memory is exhausted?

Simplified memory bounded A star discards the frontier node with the worst f but records that value in its parent, so the subtree can be regenerated if it later becomes the best option. It uses all available memory and degrades gracefully as it becomes scarce. Restarting, failing and switching strategy are cruder responses. An algorithm that adapts to whatever memory exists, rather than assuming a fixed profile, is what a general purpose implementation needs.

Q: What is beam search?

Beam search bounds the frontier to a fixed width, discarding everything else, which makes memory constant and the search fast but sacrifices both completeness and optimality. It is widely used in speech recognition and machine translation where an approximate answer quickly is worth more than a guaranteed one slowly. The other options describe no standard algorithm. Trading guarantees for a fixed resource budget is often the right decision when the budget is hard and the guarantee is soft.

Q: What is the risk of a narrow beam width?

Pruning to a fixed width may discard the only node leading to the goal, and once discarded it is never reconsidered, so the search can fail on a problem that has a solution. Widening the beam trades memory for reliability, and stochastic variants keep some diversity. Memory falls rather than rises, admissibility is a property of the heuristic, and termination is unaffected. An approximation whose failure mode is silent deserves particular care in deployment.

Q: What distinguishes local search from the search methods discussed so far?

Local search moves from one complete state to a neighbour, keeping no path and no frontier, which suits problems where the goal state itself is the answer and the route to it is irrelevant. Timetabling and layout problems are typical. Memory is constant regardless of the space's size. Heuristics, graphs and direction are shared with other methods. Discarding the path when the path is not wanted is what buys the enormous memory saving.

Q: For which problems is local search appropriate?

In scheduling, layout and configuration problems the answer is the final arrangement rather than the sequence of edits that produced it, so nothing is lost by forgetting the path. Small spaces admit anything, provable optimality is exactly what local search sacrifices, and irreversibility is unrelated. Asking whether the path is part of the answer is the first test of whether local search applies, and it is a question about the problem rather than about the algorithm.

Q: What is hill climbing?

Hill climbing examines the neighbours of the current state and moves to the best one, stopping when no neighbour is better. It is simple, uses constant memory and is trapped by local maxima, ridges and plateaux. Abstraction hierarchies, frontier ordering and depth increase describe other algorithms. The greedy local move is the simplest possible search rule, which makes its characteristic failures the clearest illustration of why more elaborate methods exist.

Q: What is a local maximum in local search?

A local maximum traps hill climbing, since every move looks worse and the algorithm stops with a suboptimal answer. Random restarts, sideways moves and simulated annealing are the standard escapes. A flat region of equal neighbours is a plateau, and the best state overall is the global maximum. Naming each failure mode separately matters because each has its own remedy, and applying the wrong one wastes effort.

Q: What is a plateau in a local search landscape?

On a plateau no neighbour is better and none is worse, so a strict hill climber halts while allowing sideways moves may let it cross to higher ground. The risk is an infinite sideways walk, so a limit on consecutive sideways moves is imposed. Steep regions, clustered maxima and basin boundaries are different features. A landscape whose flat regions are as troublesome as its peaks is a reminder that the difficulty lies in the shape of the space rather than in the algorithm.

Q: Which landscape feature defeats an axis aligned hill climber?

A ridge ascends diagonally while the available moves are axis aligned, so every single move goes downhill and the climber halts although higher ground lies just off the axis. Larger neighbourhoods or compound moves escape it. Drops, direct paths and plateau sequences describe other features. A failure caused by the mismatch between the shape of the landscape and the set of available moves points at redesigning the moves rather than the algorithm.

21.

What is the weakness shared by iterative deepening A star and recursive best first search?

A.They regenerate nodes many times because they remember too little
B.They cannot guarantee optimality even with an admissible heuristic
C.They require more memory than A star on most problems
D.They cannot be applied to problems with cycles in the state space

Answer: A

Both use linear memory and therefore forget almost everything, so a node may be regenerated many times over. Algorithms that use whatever memory is available, such as the bounded memory variants, sit between the extremes. Both are optimal with an admissible heuristic, both use far less memory than A star, and cycles are handled by ordinary means. The tension between remembering to avoid rework and forgetting to save memory is the organising theme of the whole family.

Discuss in Forum

22.

What does a memory bounded A star variant do when memory is exhausted?

A.Switches to depth first search for the remainder of the problem
B.Drops the least promising node and remembers its value in the parent
C.Restarts the search from the beginning with a tighter threshold
D.Reports failure and requires the user to supply more memory

Answer: B

Simplified memory bounded A star discards the frontier node with the worst f but records that value in its parent, so the subtree can be regenerated if it later becomes the best option. It uses all available memory and degrades gracefully as it becomes scarce. Restarting, failing and switching strategy are cruder responses. An algorithm that adapts to whatever memory exists, rather than assuming a fixed profile, is what a general purpose implementation needs.

Discuss in Forum

23.

What is beam search?

A.A search using a beam shaped region of the state space
B.A search that widens its frontier as the goal is approached
C.Best first search keeping only the best k nodes at each level
D.A search that follows a single beam of nodes to the goal

Answer: C

Beam search bounds the frontier to a fixed width, discarding everything else, which makes memory constant and the search fast but sacrifices both completeness and optimality. It is widely used in speech recognition and machine translation where an approximate answer quickly is worth more than a guaranteed one slowly. The other options describe no standard algorithm. Trading guarantees for a fixed resource budget is often the right decision when the budget is hard and the guarantee is soft.

Discuss in Forum

24.

What is the risk of a narrow beam width?

A.The search consumes more memory than a full best first search
B.The heuristic ceases to be admissible during the search
C.The algorithm cannot terminate once the beam is full
D.The path to the goal may be discarded early

Answer: D

Pruning to a fixed width may discard the only node leading to the goal, and once discarded it is never reconsidered, so the search can fail on a problem that has a solution. Widening the beam trades memory for reliability, and stochastic variants keep some diversity. Memory falls rather than rises, admissibility is a property of the heuristic, and termination is unaffected. An approximation whose failure mode is silent deserves particular care in deployment.

Discuss in Forum

25.

What distinguishes local search from the search methods discussed so far?

A.It keeps only the current state and does not record paths
B.It uses a heuristic rather than an exhaustive enumeration
C.It operates on graphs rather than on trees of states
D.It searches backwards from the goal rather than forwards

Answer: A

Local search moves from one complete state to a neighbour, keeping no path and no frontier, which suits problems where the goal state itself is the answer and the route to it is irrelevant. Timetabling and layout problems are typical. Memory is constant regardless of the space's size. Heuristics, graphs and direction are shared with other methods. Discarding the path when the path is not wanted is what buys the enormous memory saving.

Discuss in Forum

26.

For which problems is local search appropriate?

A.Those in which actions are irreversible once taken
B.Those where the goal state matters and the path does not
C.Those with very small state spaces that can be enumerated
D.Those requiring a provably optimal solution to be returned

Answer: B

In scheduling, layout and configuration problems the answer is the final arrangement rather than the sequence of edits that produced it, so nothing is lost by forgetting the path. Small spaces admit anything, provable optimality is exactly what local search sacrifices, and irreversibility is unrelated. Asking whether the path is part of the answer is the first test of whether local search applies, and it is a question about the problem rather than about the algorithm.

Discuss in Forum

27.

What is hill climbing?

A.Expanding nodes in order of increasing heuristic value
B.Increasing the search depth until a solution is found
C.Repeatedly moving to the best neighbouring state
D.Searching upward through a hierarchy of abstractions

Answer: C

Hill climbing examines the neighbours of the current state and moves to the best one, stopping when no neighbour is better. It is simple, uses constant memory and is trapped by local maxima, ridges and plateaux. Abstraction hierarchies, frontier ordering and depth increase describe other algorithms. The greedy local move is the simplest possible search rule, which makes its characteristic failures the clearest illustration of why more elaborate methods exist.

Discuss in Forum

28.

What is a local maximum in local search?

A.The highest point the algorithm reaches before terminating
B.A state from which every neighbour has the same value
C.The best state in the entire space of the problem
D.A state better than all its neighbours but not the best overall

Answer: D

A local maximum traps hill climbing, since every move looks worse and the algorithm stops with a suboptimal answer. Random restarts, sideways moves and simulated annealing are the standard escapes. A flat region of equal neighbours is a plateau, and the best state overall is the global maximum. Naming each failure mode separately matters because each has its own remedy, and applying the wrong one wastes effort.

Discuss in Forum

29.

What is a plateau in a local search landscape?

A.A flat region where neighbouring states have equal value
B.A steep region where the value changes very rapidly
C.A region containing several local maxima close together
D.The boundary between two basins of attraction

Answer: A

On a plateau no neighbour is better and none is worse, so a strict hill climber halts while allowing sideways moves may let it cross to higher ground. The risk is an infinite sideways walk, so a limit on consecutive sideways moves is imposed. Steep regions, clustered maxima and basin boundaries are different features. A landscape whose flat regions are as troublesome as its peaks is a reminder that the difficulty lies in the shape of the space rather than in the algorithm.

Discuss in Forum

30.

Which landscape feature defeats an axis aligned hill climber?

A.A sequence of plateaux separated by small steps
B.A rising region whose slope is not along any available move
C.A sharp drop between two otherwise similar states
D.A path that leads directly from the start to the goal

Answer: B

A ridge ascends diagonally while the available moves are axis aligned, so every single move goes downhill and the climber halts although higher ground lies just off the axis. Larger neighbourhoods or compound moves escape it. Drops, direct paths and plateau sequences describe other features. A failure caused by the mismatch between the shape of the landscape and the set of available moves points at redesigning the moves rather than the algorithm.

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