Hey there, let's break down these two A* questions with clear, practical reasoning:

1. Does admissibility still matter when the heuristic function in A* is consistently overestimating? #

First, let's recap: admissibility means the heuristic h(n) never overestimates the actual cost h*(n) to reach the goal from node n. This property is what guarantees A* finds the optimal path.

When your heuristic is consistently overestimating, A* loses its admissibility—and thus its guarantee of finding the optimal solution. But that doesn't mean admissibility itself becomes irrelevant:

• It acts as a baseline for understanding algorithm behavior. Knowing that admissibility is broken tells you immediately that you can't trust the result to be the cheapest path, which is critical for use cases where optimality is non-negotiable (like route planning for delivery trucks).
• Even with overestimation, the degree of overestimation ties back to admissibility. A slight overestimate might only sacrifice a tiny bit of optimality while speeding up search, but a severe overestimate can turn A* into something closer to a greedy search (which often gets stuck in local optima). Understanding admissibility helps you calibrate your heuristic to strike the right balance between speed and solution quality.
• Admissibility is also the foundation for proving other A* properties (like consistency). Even if you're using an overestimating heuristic, knowing how it deviates from admissible heuristics helps you debug why the algorithm is behaving unexpectedly.

2. When h(n) = h*(n) * 10^5 (a massive overestimate), why care if tests show no performance difference from standard A*? #

Great observation—your test results might be hiding the bigger picture because of the specific scenarios you're using. Here's why this case is still worth paying attention to:

• Reveals A's core tradeoff*: A* balances two terms in f(n) = g(n) + h(n): g(n) (cost so far) and h(n) (estimated remaining cost). When you multiply h(n) by 1e5, g(n) becomes negligible—so A* effectively turns into a greedy best-first search. Studying this extreme case makes it crystal clear how changing the weight of h shifts the algorithm's priority: from balancing cost and progress to prioritizing only progress toward the goal.
• Test case limitations: If your test cases have small state spaces or very obvious paths, greedy search might perform just as well as A*. But scale up to larger, more complex spaces (like navigating a maze with many dead ends, or planning a route through a city with thousands of intersections) and the greedy approach will start making poor choices—traversing long paths that look promising at first but lead nowhere, resulting in way more nodes being explored than a properly tuned A*. Your tests just haven't hit that edge case yet.
• Maintainability and predictability: Even if performance is the same now, knowing that your heuristic is scaled this way tells you the algorithm's behavior is fragile. If you later tweak the heuristic or expand the problem scope, you might suddenly see a huge drop in performance or correctness. Understanding this extreme scenario helps you make intentional choices about heuristic tuning, rather than relying on accidental test luck.
• Theoretical grounding: This case is a classic example used in AI courses to teach the spectrum of search algorithms. It bridges the gap between A*, Dijkstra's (when h(n)=0), and greedy search—helping you build a deeper intuition for how all these algorithms relate.

内容的提问来源于stack exchange，提问作者Aung Khant