维基百科A*伪代码是否默认启发函数满足可采纳性与一致性？

以下是维基百科的A*伪代码：

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.prepend(current)
    return total_path

// A* finds a path from start to goal.
// h is the heuristic function. h(n) estimates the cost to reach goal from node n.
function A_Star(start, goal, h)
    // The set of discovered nodes that may need to be (re-)expanded.
    // Initially, only the start node is known.
    // This is usually implemented as a min-heap or priority queue rather than a hash-set.
    openSet := {start}

    // For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from start
    // to n currently known.
    cameFrom := an empty map

    // For node n, gScore[n] is the cost of the cheapest path from start to n currently known.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to
    // how cheap a path could be from start to finish if it goes through n.
    fScore := map with default value of Infinity
    fScore[start] := h(start)

    while openSet is not empty
        // This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        openSet.Remove(current)
        for each neighbor of current
            // d(current,neighbor) is the weight of the edge from current to neighbor
            // tentative_gScore is the distance from start to the neighbor through current
            tentative_gScore := gScore[current] + d(current, neighbor)
            if tentative_gScore < gScore[neighbor]
                // This path to neighbor is better than any previous one. Record it!
                cameFrom[neighbor] := current
                gScore[neighbor] := tentative_gScore
                fScore[neighbor] := tentative_gScore + h(neighbor)
                if neighbor not in openSet
                    openSet.add(neighbor)

    // Open set is empty but goal was never reached
    return failure

我想确认该算法是否默认启发函数满足可采纳性（不会高估到达目标的实际代价）和一致性（h(x) ≤ d(x, y) + h(y)）？

因为我找到了另一段更复杂的A*伪代码：

function A*(start,goal)
 closedset := the empty set                 % The set of nodes already evaluated.     
 openset := set containing the initial node % The set of tentative nodes to be evaluated.
 g_score[start] := 0                        % Distance from start along optimal path.
 came_from := the empty map                 % The map of navigated nodes.
 h_score[start] := heuristic_estimate_of_distance(start, goal)
 f_score[start] := h_score[start]           % Estimated total distance from start to goal through y.
 while openset is not empty
     x := the node in openset having the lowest f_score[] value
     if x = goal
         return reconstruct_path(came_from,goal)
     remove x from openset
     add x to closedset
     foreach y in neighbor_nodes(x)
         if y in closedset
             continue
         tentative_g_score := g_score[x] + dist_between(x,y)
         
         if y not in openset
             add y to openset
            
             tentative_is_better := true
         elseif tentative_g_score < g_score[y]
             tentative_is_better := true
         else
             tentative_is_better := false
         if tentative_is_better = true
             came_from[y] := x
             g_score[y] := tentative_g_score
             h_score[y] := heuristic_estimate_of_distance(y, goal)
             f_score[y] := g_score[y] + h_score[y]
 return failure

 function reconstruct_path(came_from,current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from,came_from[current_node])
         return (p + current_node)
     else
         return the empty path

两者在以欧氏距离为边权的无向图中使用欧氏启发函数时均能正常工作，但第二段伪代码是否更具通用性？第一段是否默认启发函数满足可采纳性与一致性？

解答 #

1. 第一段伪代码与启发函数特性的关系
   第一段维基百科的A伪代码并没有默认要求启发函数必须满足可采纳性或一致性，这两个特性是A能保证找到最优路径的关键前提，但并非伪代码本身的强制约束：

• 若启发函数满足可采纳性，A*一定能找到最优路径；
• 若启发函数不满足一致性但满足可采纳性，A*仍能找到最优路径，但可能需要重复扩展节点，效率降低；
• 若启发函数不满足可采纳性，A*可能找到非最优路径，但依然能输出一条可行路径（如果存在）。

2. 两段伪代码的通用性对比
   第二段伪代码的通用性弱于第一段，核心差异在于是否维护closedSet：

• 第一段伪代码没有closedSet，当发现节点的更优路径时，会直接将节点重新加入openSet，即使该节点之前已经被处理过。这种设计允许它兼容启发函数不满足一致性的场景，不会错过更优路径。
• 第二段伪代码维护了closedSet，节点一旦被移出openSet就会被标记为已评估，后续遇到该节点时直接跳过。这种实现默认依赖启发函数的一致性——在一致性条件下，节点第一次被扩展时就已经找到了最优路径，无需后续处理。如果启发函数不满足一致性，这种实现可能会跳过更优路径的探索，导致最终结果非最优。

简言之，第一段伪代码的适用范围更广，能处理更多类型的启发函数；第二段伪代码的效率可能更高，但仅在启发函数满足一致性的场景下能保证最优性。

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