Informed and Heuristic Search Questions and Answers

Q: What is anytime weighted A star?

Running with a large weight first gives a quick solution, and the weight is then reduced and the search resumed, so a usable answer exists at every moment and improves with time. That suits an agent under a deadline it may not know in advance. Start points, fixed running times and temporal weighting are different notions. Making the quality of an answer a function of the time available, rather than requiring completion, is exactly what a real time system needs.

Q: What is the practical reason for preferring an anytime algorithm?

An agent that may be interrupted at an unpredictable moment needs an answer available throughout, and one that improves monotonically lets it use whatever time it turns out to have. Memory profiles vary, improvement is by construction rather than a separate guarantee, and a heuristic is still needed. Designing for an unknown deadline, rather than assuming one, is what distinguishes an algorithm intended for an agent from one intended for a batch computation.

Q: What does the letter h conventionally denote in search?

By convention g is the cost so far, h is the estimate of the cost remaining and f is their sum. Keeping the three letters straight is essential to reading any description of A star or its variants. Tree height, frontier size and accumulated cost are denoted differently. Notation that is consistent across the literature is worth learning exactly, since a misread symbol inverts the meaning of an algorithm.

Q: Which search uses only the h term?

Greedy best first orders the frontier by the estimated remaining cost alone, ignoring what has already been spent, which makes it fast and suboptimal. Uniform cost uses g alone, A star uses both, and breadth first uses depth. Placing each algorithm by which terms of the evaluation function it uses turns a list of methods into a single family with a two dimensional structure, which is much easier to remember.

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.

71.

What is anytime weighted A star?

A.A search whose running time is independent of the problem
B.A search that weights nodes by the time spent reaching them
C.A search that returns a solution quickly then improves it
D.A search that may be started at any point in the state space

Answer: C

Running with a large weight first gives a quick solution, and the weight is then reduced and the search resumed, so a usable answer exists at every moment and improves with time. That suits an agent under a deadline it may not know in advance. Start points, fixed running times and temporal weighting are different notions. Making the quality of an answer a function of the time available, rather than requiring completion, is exactly what a real time system needs.

Discuss in Forum

72.

What is the practical reason for preferring an anytime algorithm?

A.Anytime algorithms use less memory than ordinary ones
B.They are guaranteed to find better solutions eventually
C.They require no heuristic function to operate correctly
D.The deadline may not be known when the search begins

Answer: D

An agent that may be interrupted at an unpredictable moment needs an answer available throughout, and one that improves monotonically lets it use whatever time it turns out to have. Memory profiles vary, improvement is by construction rather than a separate guarantee, and a heuristic is still needed. Designing for an unknown deadline, rather than assuming one, is what distinguishes an algorithm intended for an agent from one intended for a batch computation.

Discuss in Forum

73.

What does the letter h conventionally denote in search?

A.The estimated cost from a state to the goal
B.The height of the search tree at that point
C.The number of nodes remaining in the frontier
D.The cost of the path from the start to the state

Answer: A

By convention g is the cost so far, h is the estimate of the cost remaining and f is their sum. Keeping the three letters straight is essential to reading any description of A star or its variants. Tree height, frontier size and accumulated cost are denoted differently. Notation that is consistent across the literature is worth learning exactly, since a misread symbol inverts the meaning of an algorithm.

Discuss in Forum

74.

In the standard notation, what quantity is written as g?

A.The estimated cost from the node to the goal
B.The cost of the path from the start to a node
C.The goal state the search is trying to reach
D.The number of goals the problem contains

Answer: B

g is the exact cost accumulated from the initial state to the node in question, known rather than estimated, and it is what uniform cost search orders on. The estimate of the remainder is h and the goal itself is not usually given a letter. Distinguishing an exact quantity from an estimated one in the notation is what makes the properties of the algorithms provable, since the guarantees rest on which of the two may be wrong.

Discuss in Forum

75.

Which search uses only the h term?

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

Answer: C

Greedy best first orders the frontier by the estimated remaining cost alone, ignoring what has already been spent, which makes it fast and suboptimal. Uniform cost uses g alone, A star uses both, and breadth first uses depth. Placing each algorithm by which terms of the evaluation function it uses turns a list of methods into a single family with a two dimensional structure, which is much easier to remember.

Discuss in Forum

76.

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

77.

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

78.

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

79.

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

80.

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

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