Informed and Heuristic Search Questions and Answers

Q: Where do admissible heuristics usually come from?

Dropping a constraint gives a relaxed problem whose optimal solution can never cost more than the original's, so its exact cost is an admissible heuristic for the real problem. Straight line distance and the misplaced tile count both arise this way. Empirical measurements may give useful but not provably admissible estimates. Deriving a guarantee from the structure of a relaxation, rather than hoping for one, is what makes the technique so widely applicable.

Q: Why is the number of misplaced tiles an admissible heuristic for the eight puzzle?

Each tile out of place requires at least one move, so the count is a lower bound on the solution length, and it corresponds exactly to relaxing the rules so that a tile may move anywhere. Being smaller than another heuristic does not establish admissibility, the count is of tiles rather than moves, and no measurement is involved. Tracing a heuristic back to the relaxation that produces it both proves admissibility and suggests how to improve it.

Q: Why does Manhattan distance dominate the misplaced tile heuristic?

Summing the horizontal and vertical distances of each tile counts at least as many moves as counting displaced tiles, and usually many more, while remaining a lower bound. It corresponds to relaxing only the rule that a tile must move into the blank. Overestimation would destroy admissibility, and computation cost is not what confers quality. A relaxation that drops fewer constraints yields a tighter and therefore better heuristic, which is a general recipe.

Q: What is a pattern database?

Solving a simplified problem involving only some of the tiles exhaustively, and storing the exact cost of every configuration, gives a very strong admissible heuristic obtainable by a table lookup. Disjoint pattern databases may even be added together. Search histories, pattern matching and learned estimates are different techniques. Spending memory in advance to buy accuracy during search is a trade that modern hardware makes attractive.

Q: When may the values from two pattern databases be added?

Addition preserves admissibility only if no move is counted in both databases, which requires the subproblems to partition the moves rather than merely the tiles. Otherwise the sum may exceed the true cost. Shared goals, individual admissibility and equal size are not sufficient. A condition that permits addition rather than merely maximisation is valuable because sums are far larger than maxima, and it is worth the care needed to establish it.

Q: What is the effective branching factor of a heuristic search?

Given the nodes generated and the solution depth, the effective branching factor is the value b that satisfies the node count for a uniform tree of that depth, and it is the standard empirical measure of heuristic quality. A value near one indicates a nearly perfect heuristic. The raw successor count, the expansion ratio and the relaxation's structure are different quantities. Summarising a search's efficiency in one interpretable number is what allows heuristics to be compared across problems.

Q: What is the principal drawback of A star in practice?

A star keeps every node it generates, so on a large problem it runs out of memory long before it runs out of time, which is why the memory bounded variants exist. Its optimality holds regardless of size given an admissible heuristic, the heuristic is by definition an estimate, and varying step costs are exactly what it handles. Recognising that an algorithm's practical limit differs from its theoretical weakness is what directs attention to the right family of improvements.

Q: What is iterative deepening A star?

IDA star performs a depth first search that prunes any node whose f exceeds a threshold, then raises the threshold to the smallest f that was pruned and repeats, giving A star's optimality with linear memory. Its weakness is repeating work when many distinct f values exist. Memory limits, successor ordering and bidirectionality describe other variants. Replacing a depth cutoff by a cost cutoff is a small change that transfers the whole iterative deepening argument to the informed setting.

Q: When does iterative deepening A star perform badly?

If step costs are real valued, almost every node has a distinct f and each iteration raises the threshold by a tiny amount, so the number of iterations approaches the number of nodes. Rounding thresholds or using recursive best first search are the usual responses. Consistency, branching factor and shallow goals do not cause the problem. An algorithm whose efficiency depends on the granularity of the cost function is one whose applicability must be checked against the problem's costs.

Q: What is recursive best first search?

RBFS explores depth first but remembers the f value of the best alternative path at each level, and unwinds when the current path exceeds it, replacing each node's f with the best value found beneath it. It uses linear memory and is optimal with an admissible heuristic, at the cost of regenerating nodes repeatedly. Implementation style, decomposition and restarting are different ideas. Carrying just enough information to know when to abandon a path is what makes linear memory possible.

11.

Where do admissible heuristics usually come from?

A.Random sampling of paths through the state space
B.The average path cost observed during earlier searches
C.The exact cost of a relaxed version of the problem
D.Measurements taken from previously solved instances

Answer: C

Dropping a constraint gives a relaxed problem whose optimal solution can never cost more than the original's, so its exact cost is an admissible heuristic for the real problem. Straight line distance and the misplaced tile count both arise this way. Empirical measurements may give useful but not provably admissible estimates. Deriving a guarantee from the structure of a relaxation, rather than hoping for one, is what makes the technique so widely applicable.

Discuss in Forum

12.

Why is the number of misplaced tiles an admissible heuristic for the eight puzzle?

A.It is always smaller than the Manhattan distance heuristic
B.It counts moves rather than tiles and so cannot overestimate
C.It was measured empirically on many solved instances
D.Every misplaced tile must move at least once

Answer: D

Each tile out of place requires at least one move, so the count is a lower bound on the solution length, and it corresponds exactly to relaxing the rules so that a tile may move anywhere. Being smaller than another heuristic does not establish admissibility, the count is of tiles rather than moves, and no measurement is involved. Tracing a heuristic back to the relaxation that produces it both proves admissibility and suggests how to improve it.

Discuss in Forum

13.

Why does Manhattan distance dominate the misplaced tile heuristic?

A.It counts every step each tile must make rather than just one
B.It is computed from the goal state rather than the current one
C.It is always an overestimate and so prunes more aggressively
D.It requires more computation and therefore gives more information

Answer: A

Summing the horizontal and vertical distances of each tile counts at least as many moves as counting displaced tiles, and usually many more, while remaining a lower bound. It corresponds to relaxing only the rule that a tile must move into the blank. Overestimation would destroy admissibility, and computation cost is not what confers quality. A relaxation that drops fewer constraints yields a tighter and therefore better heuristic, which is a general recipe.

Discuss in Forum

14.

What is a pattern database?

A.A database of solved instances used to train a heuristic
B.Precomputed exact costs of solving a subproblem, stored for lookup
C.A record of every state encountered in previous searches
D.A collection of patterns matched against the current state

Answer: B

Solving a simplified problem involving only some of the tiles exhaustively, and storing the exact cost of every configuration, gives a very strong admissible heuristic obtainable by a table lookup. Disjoint pattern databases may even be added together. Search histories, pattern matching and learned estimates are different techniques. Spending memory in advance to buy accuracy during search is a trade that modern hardware makes attractive.

Discuss in Forum

15.

When may the values from two pattern databases be added?

A.When each database is admissible on its own
B.When the two subproblems have the same number of states
C.When the subproblems involve disjoint sets of moves
D.When both databases were built from the same goal state

Answer: C

Addition preserves admissibility only if no move is counted in both databases, which requires the subproblems to partition the moves rather than merely the tiles. Otherwise the sum may exceed the true cost. Shared goals, individual admissibility and equal size are not sufficient. A condition that permits addition rather than merely maximisation is valuable because sums are far larger than maxima, and it is worth the care needed to establish it.

Discuss in Forum

16.

What is the effective branching factor of a heuristic search?

A.The average number of successors each expanded node produced
B.The ratio of nodes expanded to nodes generated during the search
C.The branching factor of the relaxed problem the heuristic came from
D.The uniform branching factor that would generate the same node count

Answer: D

Given the nodes generated and the solution depth, the effective branching factor is the value b that satisfies the node count for a uniform tree of that depth, and it is the standard empirical measure of heuristic quality. A value near one indicates a nearly perfect heuristic. The raw successor count, the expansion ratio and the relaxation's structure are different quantities. Summarising a search's efficiency in one interpretable number is what allows heuristics to be compared across problems.

Discuss in Forum

17.

What is the principal drawback of A star in practice?

A.It stores every generated node and exhausts memory
B.It fails to find optimal solutions on large problems
C.It requires the heuristic to be computed exactly
D.It cannot be applied to problems with varying step costs

Answer: A

A star keeps every node it generates, so on a large problem it runs out of memory long before it runs out of time, which is why the memory bounded variants exist. Its optimality holds regardless of size given an admissible heuristic, the heuristic is by definition an estimate, and varying step costs are exactly what it handles. Recognising that an algorithm's practical limit differs from its theoretical weakness is what directs attention to the right family of improvements.

Discuss in Forum

18.

What is iterative deepening A star?

A.A star run in both directions until the searches meet
B.Depth first search with a cutoff on f rather than on depth
C.A star restarted repeatedly with increasing memory limits
D.Iterative deepening using a heuristic to order the successors

Answer: B

IDA star performs a depth first search that prunes any node whose f exceeds a threshold, then raises the threshold to the smallest f that was pruned and repeats, giving A star's optimality with linear memory. Its weakness is repeating work when many distinct f values exist. Memory limits, successor ordering and bidirectionality describe other variants. Replacing a depth cutoff by a cost cutoff is a small change that transfers the whole iterative deepening argument to the informed setting.

Discuss in Forum

19.

When does iterative deepening A star perform badly?

A.When the branching factor of the problem is very large
B.When the solution lies at a shallow depth in the tree
C.When many distinct f values cause very many iterations
D.When the heuristic is admissible but not consistent

Answer: C

If step costs are real valued, almost every node has a distinct f and each iteration raises the threshold by a tiny amount, so the number of iterations approaches the number of nodes. Rounding thresholds or using recursive best first search are the usual responses. Consistency, branching factor and shallow goals do not cause the problem. An algorithm whose efficiency depends on the granularity of the cost function is one whose applicability must be checked against the problem's costs.

Discuss in Forum

20.

What is recursive best first search?

A.A best first search implemented using recursion for efficiency
B.A search that recursively decomposes the problem into subproblems
C.A search that restarts from the best node found so far
D.A depth first search tracking the best alternative f value

Answer: D

RBFS explores depth first but remembers the f value of the best alternative path at each level, and unwinds when the current path exceeds it, replacing each node's f with the best value found beneath it. It uses linear memory and is optimal with an admissible heuristic, at the cost of regenerating nodes repeatedly. Implementation style, decomposition and restarting are different ideas. Carrying just enough information to know when to abandon a path is what makes linear memory possible.

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