Informed and Heuristic Search Questions and Answers

Q: A star has expanded a node with \( g = 7 \) and \( h = 5 \). What is its f value?

The evaluation function is the sum of the two terms:\[ f = 7 + 5 = 12 \]giving 12, an estimate of the total cost of the best solution through that node. Nodes are expanded in increasing order of f, so this one waits behind everything cheaper. Keeping the accumulated and the estimated terms clearly separate is what makes the behaviour of A star predictable, since setting either to zero recovers a simpler algorithm.

Q: What happens to A star if the heuristic is identically zero?

With h equal to zero the evaluation function reduces to the path cost alone, which is exactly uniform cost search, and the algorithm remains complete and optimal but loses all guidance. Setting g to zero instead gives greedy search. Breadth first requires equal step costs, and termination is unaffected. Recovering simpler algorithms as special cases by zeroing a term is the clearest way to see what each term contributes.

Q: What happens if the heuristic equals the true remaining cost exactly?

A perfect heuristic makes f constant along an optimal path and larger everywhere else, so the search walks straight to the goal. It is admissible, since equality satisfies the inequality, and it represents the unattainable ideal against which real heuristics are measured. The other options invert the behaviour. Identifying the two extremes, no information and perfect information, places every real heuristic on a scale between them.

Q: Why is a more accurate heuristic not always the better choice?

A heuristic that halves the nodes expanded but takes ten times as long to evaluate is a poor bargain, so the comparison must be on total time rather than on node counts. Pattern databases resolve this by precomputing, trading memory for both. Accuracy does not imply inadmissibility, closeness to the truth is desirable, and storage varies. Comparing algorithms on the quantity actually wanted, rather than on a convenient proxy, is a discipline the node count measure quietly undermines.

Q: What is the trade in choosing a heuristic?

Every heuristic sits somewhere between the free but useless zero function and the perfect but unobtainable exact cost, and the practical question is how much computation buys how much pruning. Admissibility and consistency are conditions rather than opposing ends of a trade, and optimality is preserved by admissibility regardless of memory. Recognising which two quantities are actually in tension is the first step in making the choice deliberately rather than by habit.

Q: Consider the following statements about A star search. 1. An admissible heuristic guarantees optimality in tree search 2. A consistent heuristic guarantees optimality in graph search 3. A star uses memory linear in the depth of the solution Which of the statements given above is or are correct?

The first two are the standard results. A star stores every generated node, so its memory is exponential and that is its principal practical weakness, which is exactly why the memory bounded variants exist. Confusing A star's memory profile with that of its linear space descendants inverts the reason those descendants were invented, so the distinction is worth holding firmly.

Q: Consider the following pairings in heuristic search. Admissible - never overestimates the remaining cost Consistent - satisfies the triangle inequality Dominant - at least as large everywhere and still admissible Greedy best first - optimal with an admissible heuristic How many of the pairs given above are correctly matched?

The first three are correct. Greedy best first ignores the cost already incurred, so it is not optimal however good the heuristic is. It is A star that inherits optimality from admissibility. The pairing is worth checking carefully because the two algorithms differ by a single term and their properties differ completely, which is a good illustration of how much one term in an evaluation function can matter.

51.

A heuristic returns 4 where the true remaining cost is 6. Is it admissible at that state?

A.No, since an admissible heuristic must be exact
B.Yes, since it does not exceed the true cost
C.No, since it differs from the true cost
D.Yes, but only if it is exact at the goal state

Answer: B

Admissibility requires only that the estimate not exceed the truth:

\[ h = 4 \le 6 = h^{*} \]

so the heuristic is admissible at that state, though a tighter estimate would prune more. Exactness would make the search follow the optimal path directly and is never available in practice. A one sided condition is easy to satisfy and easy to check, which is why admissibility rather than accuracy is the property demanded.

Discuss in Forum

52.

Two admissible heuristics give 5 and 8 at a state. What value should be used?

A.6.5
B.13
C.8
D.5

Answer: C

The maximum of admissible heuristics is admissible and dominates both:

\[ h = \max(5, 8) = 8 \]

so 8 is the right choice. The sum of 13 might exceed the true cost and destroy the guarantee unless the two are additive over disjoint subproblems, and the average discards information. Taking the maximum costs only the extra evaluation and never loses, which makes it the default whenever several estimates are available.

Discuss in Forum

53.

A star has expanded a node with \( g = 7 \) and \( h = 5 \). What is its f value?

A.35
B.2
C.7
D.12

Answer: D

The evaluation function is the sum of the two terms:

\[ f = 7 + 5 = 12 \]

giving 12, an estimate of the total cost of the best solution through that node. Nodes are expanded in increasing order of f, so this one waits behind everything cheaper. Keeping the accumulated and the estimated terms clearly separate is what makes the behaviour of A star predictable, since setting either to zero recovers a simpler algorithm.

Discuss in Forum

54.

What happens to A star if the heuristic is identically zero?

A.It becomes uniform cost search
B.It becomes greedy best first search
C.It becomes breadth first search regardless of step costs
D.It fails to terminate because no guidance is available

Answer: A

With h equal to zero the evaluation function reduces to the path cost alone, which is exactly uniform cost search, and the algorithm remains complete and optimal but loses all guidance. Setting g to zero instead gives greedy search. Breadth first requires equal step costs, and termination is unaffected. Recovering simpler algorithms as special cases by zeroing a term is the clearest way to see what each term contributes.

Discuss in Forum

55.

What happens if the heuristic equals the true remaining cost exactly?

A.The heuristic ceases to be admissible and optimality is lost
B.A star follows an optimal path without expanding anything else
C.A star expands every node in the state space before finishing
D.A star becomes equivalent to depth first search in behaviour

Answer: B

A perfect heuristic makes f constant along an optimal path and larger everywhere else, so the search walks straight to the goal. It is admissible, since equality satisfies the inequality, and it represents the unattainable ideal against which real heuristics are measured. The other options invert the behaviour. Identifying the two extremes, no information and perfect information, places every real heuristic on a scale between them.

Discuss in Forum

56.

Why is a more accurate heuristic not always the better choice?

A.A star cannot use a heuristic that is too close to the truth
B.More accurate heuristics require more memory to store
C.Computing it may cost more than the search it saves
D.Accurate heuristics are usually inadmissible in practice

Answer: C

A heuristic that halves the nodes expanded but takes ten times as long to evaluate is a poor bargain, so the comparison must be on total time rather than on node counts. Pattern databases resolve this by precomputing, trading memory for both. Accuracy does not imply inadmissibility, closeness to the truth is desirable, and storage varies. Comparing algorithms on the quantity actually wanted, rather than on a convenient proxy, is a discipline the node count measure quietly undermines.

Discuss in Forum

57.

What is the trade in choosing a heuristic?

A.Admissibility against consistency of the estimates
B.Memory usage against the optimality of the solution
C.Completeness against the branching factor of the search
D.Accuracy against the cost of computing it

Answer: D

Every heuristic sits somewhere between the free but useless zero function and the perfect but unobtainable exact cost, and the practical question is how much computation buys how much pruning. Admissibility and consistency are conditions rather than opposing ends of a trade, and optimality is preserved by admissibility regardless of memory. Recognising which two quantities are actually in tension is the first step in making the choice deliberately rather than by habit.

Discuss in Forum

58.

Consider the following statements about A star search.

1. An admissible heuristic guarantees optimality in tree search

2. A consistent heuristic guarantees optimality in graph search

3. A star uses memory linear in the depth of the solution

Which of the statements given above is or are correct?

A.1 and 2 only
B.1 and 3 only
C.2 and 3 only
D.1, 2 and 3

Answer: A

The first two are the standard results. A star stores every generated node, so its memory is exponential and that is its principal practical weakness, which is exactly why the memory bounded variants exist. Confusing A star's memory profile with that of its linear space descendants inverts the reason those descendants were invented, so the distinction is worth holding firmly.

Discuss in Forum

59.

Match each algorithm with its distinguishing feature.

List I

A. Greedy best first

B. A star

C. Iterative deepening A star

D. Simulated annealing

List II

P. orders by estimated remaining cost alone

Q. orders by cost so far plus estimate

R. depth first with an f threshold

S. accepts worse moves with falling probability

Select the correct match.

A.A-P, B-R, C-Q, D-S
B.A-P, B-Q, C-R, D-S
C.A-Q, B-P, C-S, D-R
D.A-R, B-S, C-P, D-Q

Answer: B

The first three differ only in which terms they use and how they manage memory, while the fourth belongs to the local search family and keeps no frontier at all. Sorting algorithms by what they order the frontier on, and by how much they remember, organises the whole subject and makes an unfamiliar variant easy to place.

Discuss in Forum

60.

Consider the following pairings in heuristic search.

Admissible - never overestimates the remaining cost

Consistent - satisfies the triangle inequality

Dominant - at least as large everywhere and still admissible

Greedy best first - optimal with an admissible heuristic

How many of the pairs given above are correctly matched?

A.Only two
B.All four
C.Only three
D.Only one

Answer: C

The first three are correct. Greedy best first ignores the cost already incurred, so it is not optimal however good the heuristic is. It is A star that inherits optimality from admissibility. The pairing is worth checking carefully because the two algorithms differ by a single term and their properties differ completely, which is a good illustration of how much one term in an evaluation function can matter.

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