Heuristic Search Admissibility and Consistency Quiz

Reviewed by Editorial Team
The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.
Learn about Our Editorial Process
| By Thames
T
Thames
Community Contributor
Quizzes Created: 6575 | Total Attempts: 67,424
| Attempts: 11 | Questions: 15 | Updated: May 2, 2026
Please wait...
Question 1 / 16
🏆 Rank #--
0 %
0/100
Score 0/100

1. A heuristic h(n) is admissible if it never ______ the actual cost to reach the goal.

Explanation

An admissible heuristic is one that ensures optimality in search algorithms like A*. It must not overestimate the true cost of reaching the goal from any node, guaranteeing that the estimated cost is always less than or equal to the actual cost. This property helps in finding the shortest path efficiently without missing optimal solutions.

Submit
Please wait...
About This Quiz
Heuristic Search Admissibility and Consistency Quiz - Quiz

This quiz evaluates your understanding of heuristic search admissibility and consistency, two critical properties that ensure optimal pathfinding in AI. Learn how admissible heuristics never overestimate true costs and how consistency guarantees monotonic improvements in search efficiency. Perfect for computer science students mastering informed search algorithms. Key focus: Heuristic Search... see moreAdmissibility and Consistency Quiz. see less

2.

What first name or nickname would you like us to use?

You may optionally provide this to label your report, leaderboard, or certificate.

2. Which property ensures that A* search always finds the optimal path when using an admissible heuristic?

Explanation

Optimality ensures that A* search finds the best possible path to the goal when using an admissible heuristic. An admissible heuristic never overestimates the true cost to reach the goal, which allows the algorithm to explore paths efficiently while guaranteeing that the first solution found is the optimal one.

Submit

3. A heuristic is consistent if h(n) ≤ c(n,n') + h(n') for all successors n'. This ensures the heuristic is ______.

Explanation

A heuristic is considered monotonic if it maintains a non-decreasing estimate of the cost to reach the goal as the search progresses. The condition h(n) ≤ c(n, n') + h(n') ensures that the estimated cost from the current node to the goal does not exceed the cost of reaching a successor node plus its estimated cost to the goal.

Submit

4. In A* search with f(n) = g(n) + h(n), what does g(n) represent?

Explanation

In A* search, g(n) represents the actual cost incurred to reach node n from the start node. It quantifies the total distance or cost already traveled, providing a foundation for the algorithm to evaluate the most efficient path to the goal by combining it with the heuristic estimate, h(n).

Submit

5. Which statement about admissible heuristics is true?

Explanation

A consistent heuristic guarantees that the estimated cost to reach a goal is always less than or equal to the actual cost, ensuring it never overestimates. Since admissibility requires that a heuristic never overestimates the cost to reach the goal, all consistent heuristics inherently satisfy the admissibility condition, making them admissible.

Submit

6. A consistent heuristic guarantees that f(n) values along any path are ______.

Explanation

A consistent heuristic ensures that the estimated cost to reach the goal from a node does not decrease as one moves along a path. This means that the total estimated cost, represented by f(n) values, will either stay the same or increase, reflecting the principle that additional steps cannot reduce the estimated cost.

Submit

7. In the 8-puzzle, the Manhattan distance heuristic is both admissible and consistent. Why is it admissible?

Explanation

The Manhattan distance heuristic is admissible because it calculates the total distance each tile is from its goal position by summing the horizontal and vertical distances. This ensures that the heuristic value will never be greater than the actual minimum number of moves required to solve the puzzle, making it a reliable guide for optimal solutions.

Submit

8. If h₁(n) and h₂(n) are both admissible heuristics, then h(n) = max(h₁(n), h₂(n)) is also ______.

Explanation

An admissible heuristic is one that never overestimates the true cost to reach the goal. Since both h₁(n) and h₂(n) are admissible, they each provide estimates that are less than or equal to the actual cost. Therefore, taking the maximum of these two estimates will also not exceed the true cost, ensuring that h(n) remains admissible.

Submit

9. Which of the following best describes the relationship between admissible heuristics and A* optimality?

Explanation

Admissibility ensures that a heuristic never overestimates the cost to reach the goal, which allows A* to find the least-cost path to the goal. While consistency (also known as monotonicity) strengthens this property, admissibility alone is enough to guarantee that A* will produce an optimal solution.

Submit

10. A monotone restriction (consistency constraint) allows A* to avoid ______ already-expanded nodes.

Explanation

A monotone restriction ensures that the cost of reaching a node does not increase along a path. This property allows the A* algorithm to avoid re-expanding nodes that have already been evaluated, as the optimal path to these nodes has already been determined, thus improving efficiency and reducing unnecessary computations.

Submit

11. In Euclidean distance heuristic for pathfinding, why is it admissible for grid-based movement with diagonal moves allowed?

Explanation

In grid-based movement with diagonal moves allowed, the Euclidean distance heuristic is admissible because it always provides a lower bound on the actual distance to the goal. Since diagonal moves can cover more ground than straight moves, the heuristic will not overestimate the number of moves required, ensuring it remains a valid estimate for pathfinding.

Submit

12. Consistency implies ______, but admissibility does not necessarily imply consistency.

Explanation

Consistency implies that the set of beliefs or propositions does not contain contradictions, while admissibility refers to the acceptance of certain beliefs without guaranteeing their coherence. Thus, a set can be admissible without being consistent, as it may allow for contradictory beliefs to coexist.

Submit

13. Which scenario would benefit most from using a consistent heuristic over merely an admissible one?

Submit

14. The zero heuristic h(n) = 0 is both admissible and consistent. This reduces A* to ______.

Submit

15. True or False: An inadmissible heuristic can still produce optimal solutions in A* search.

Submit
×
Saved
Thank you for your feedback!
View My Results
Cancel
  • All
    All (15)
  • Unanswered
    Unanswered ()
  • Answered
    Answered ()
A heuristic h(n) is admissible if it never ______ the actual cost to...
Which property ensures that A* search always finds the optimal path...
A heuristic is consistent if h(n) ≤ c(n,n') + h(n') for all...
In A* search with f(n) = g(n) + h(n), what does g(n) represent?
Which statement about admissible heuristics is true?
A consistent heuristic guarantees that f(n) values along any path are...
In the 8-puzzle, the Manhattan distance heuristic is both admissible...
If h₁(n) and h₂(n) are both admissible heuristics, then h(n) =...
Which of the following best describes the relationship between...
A monotone restriction (consistency constraint) allows A* to avoid...
In Euclidean distance heuristic for pathfinding, why is it admissible...
Consistency implies ______, but admissibility does not necessarily...
Which scenario would benefit most from using a consistent heuristic...
The zero heuristic h(n) = 0 is both admissible and consistent. This...
True or False: An inadmissible heuristic can still produce optimal...
play-Mute sad happy unanswered_answer up-hover down-hover success oval cancel Check box square blue
Alert!