关于AI（A*）中启发式函数定义于搜索节点而非状态的技术问询

Great question—this is one of those subtle details in heuristic search that’s easy to gloss over but really reveals how A* and similar algorithms work under the hood. Let’s break this down step by step.

First, let’s clarify the key distinction that’s critical to understanding the problem:

• A state is a snapshot of the problem world (e.g., a specific 8-puzzle board layout, a position in a maze). It represents "where you are" in the problem space, with no context about how you got there.
• A search node is a wrapper around a state that includes extra metadata from the search process: things like the path taken to reach the state, the total cost of that path, the depth of the node in the search tree, or even the parent node.

Why would a heuristic be defined on nodes instead of states? #

The short answer: to leverage metadata stored in the node that the state itself doesn’t contain. Here’s a concrete example to make this tangible:

Suppose you’re solving a grid-based pathfinding problem where moving uphill costs 3x more than moving on flat ground. Now, imagine two different search nodes that represent the same grid position (state):

• Node 1 was reached via a path that only went uphill, with a total path cost of 20.
• Node 2 was reached via a path that mostly went downhill, with a total path cost of 8.

If you wanted your heuristic to prioritize nodes that arrived via cheaper paths (to avoid wasting time exploring high-cost branches early), you could define h(n) as:

h(n) = manhattan_distance(n.state, goal) + (15 - n.path_cost)

Here, n.path_cost is a property of the search node, not the state. The heuristic adjusts its value based on how expensive the path to the current node was—something the state alone can’t tell you.

Another example: in iterative deepening A* (IDA*), you might tweak the heuristic based on the current depth of the node to prune deeper branches earlier, even if their state is identical to a shallower node.

Why is this extra generality rarely useful? #

This is the more interesting part, and it boils down to three core constraints of effective heuristic search:

1. Heuristics need to be admissible/consistent for optimality #

For A* to guarantee finding the shortest (lowest-cost) path, the heuristic must be admissible (never overestimates the true cost to the goal) and ideally consistent (for every node n and its successor n', h(n) ≤ cost(n→n') + h(n')).

If you tie the heuristic to node-specific metadata (like path cost or depth), it’s extremely easy to break these properties. For example, in the pathfinding example above, if (15 - n.path_cost) is positive, you might end up overestimating the true remaining cost, making the heuristic inadmissible—and A* loses its optimality guarantee.

2. Most problems don’t need node-specific heuristics #

The vast majority of practical search problems have the property that the minimal cost to reach the goal depends only on the current state, not on how you got there. For example:

• In 8-puzzle, the number of misplaced tiles (a classic heuristic) only depends on the current board state, not the sequence of moves that led to it.
• In maze pathfinding, the Manhattan distance to the exit only depends on your current position, not the turns you made to get there.

Adding node-specific logic to the heuristic complicates the algorithm without providing meaningful benefits. It also makes the heuristic harder to design, test, and prove correct.

3. It can lead to redundant work #

If two nodes represent the same state but have different heuristic values, A* might waste time exploring both even though one is clearly worse. In standard state-based heuristics, we can use a closed set to skip reprocessing the same state—but with node-based heuristics, this becomes trickier, since the same state might have "better" or "worse" heuristic values depending on the node’s metadata.

Wrap-up #

Defining heuristics on nodes gives you more flexibility, but that flexibility almost always comes at the cost of losing optimality guarantees, adding unnecessary complexity, and providing little practical gain. For nearly all real-world use cases, state-based heuristics are sufficient, simpler, and easier to verify.

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