A*图搜索中，可采纳启发式为何无法保证最优路径？

Great question—this is a nuanced point that trips up many people learning A*! Let's break this down clearly, starting with key definitions and then walking through a concrete example where admissibility alone fails.

Key Definitions to Set the Stage #

First, let's align on critical terms:

• Admissible Heuristic: A heuristic h(n) is admissible if it never overestimates the actual minimal cost to reach the goal from node n—so h(n) ≤ h*(n), where h*(n) is the true shortest-path cost from n to the goal.
• Consistent (Monotonic) Heuristic: A stricter condition than admissibility: for every node n and its successor n' (connected by an edge with cost c(n,n')), h(n) ≤ c(n,n') + h(n'), plus h(goal) = 0. Consistency guarantees admissibility, but the reverse isn't true—you can have admissible heuristics that aren't consistent.
• Graph Search vs. Tree Search: Tree search doesn't track visited nodes, so it can revisit states repeatedly. Graph search uses a closed (visited) list to avoid redundant work, which is essential for large, cyclic graphs.

The Core Issue: Admissibility + Inconsistency + Closed Lists #

In tree search, an admissible heuristic guarantees A* will find the optimal path. But in graph search (with a closed list), admissibility alone isn't enough—unless your A* implementation allows re-opening nodes from the closed list when a cheaper path to them is found.

Here's why:
When a heuristic is admissible but inconsistent, it's possible for a node to be added to the closed list after being expanded via a suboptimal path. Later, A* might discover a cheaper path to that node, but since it's already marked as visited, the algorithm ignores this better route. This can block A* from finding the overall optimal path, as the cheaper path to the node could lead to a lower-cost route to the goal.

Concrete Example of the Problem #

Let's use a scenario where an admissible but inconsistent heuristic, paired with a non-reopening A* graph search, leads to a suboptimal result:

• Nodes: S (start), A, B, G (goal)
• Edge costs:
  • S → A: cost = 5
  • S → B: cost = 1
  • A → B: cost = 1
  • A → G: cost = 2
  • B → G: cost = 10
• Heuristic values (admissible but inconsistent):
  • h(S) = 3 (true shortest cost h*(S) = 1+1+2 = 4, so 3 ≤ 4—admissible)
  • h(A) = 2 (true cost h*(A) = 2, so 2 ≤ 2—admissible)
  • h(B) = 0 (true cost h*(B) = 1+2 = 3, so 0 ≤3—admissible)
  • h(G) = 0

This heuristic is inconsistent: For edge A → B, h(A) = 2 is greater than c(A→B) + h(B) = 1+0 =1, violating the consistency rule.

Now run the non-reopening A* graph search:

1. Start with open = [S (g=0, f=0+3=3)], closed = []
2. Pop S, expand to A (g=5, f=5+2=7) and B (g=1, f=1+0=1). Add both to open, move S to closed.
3. Pop B (lowest f-value), expand to G (g=1+10=11, f=11). Add G to open, move B to closed.
4. Now open has A (f=7) and G (f=11). Pop A, expand to B (already in closed—ignore) and G (g=5+2=7, f=7). Add this new G entry to open.
5. Pop G (g=7, f=7) from open. The algorithm returns the path S→A→G with total cost 7.

But the true optimal path is S→B→A→G with total cost 1+1+2=4! Because B was marked as visited (added to closed) in step 3, we can't re-open it to explore the cheaper path through A, so A* misses the optimal route.

How to Guarantee Optimal Paths #

To fix this, you have two reliable options for A* graph search:

1. Use a consistent heuristic: Consistency ensures that once a node is added to closed, you've already found the cheapest path to it—so no need to re-open it.
2. Modify your A* implementation to re-open nodes: If a cheaper path to a node in closed is discovered, move it back to the open list to re-evaluate its successors.

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