A* 图搜索
A* Graph search
给定启发式值h(A)=5，h(B)=1，使用A*图搜索，将A和B放在f(A)=2+5=7的边界上， f(B)=4+1=5，则selectB进行扩容，然后将G放在f(G)=4+4=8的边界上，则selectA进行扩容，但不会做任何事情，因为 S 和 B 都已经扩展并且不在边界上，因此它将 select G 接下来和 return 一个非最佳解决方案。
我的论点正确吗？
您在边界上维护一个有序的对象优先级队列。然后，您选择最佳候选者，向所有可用方向扩展，并将新节点放入优先级队列中。因此，即使实际上最佳路径经过它，A 也有可能被推到队列的后面。 A 也有可能被通过 sub-optimal 路径到达的邻居包围，在这种情况下，大多数算法不会像您所说的那样尝试扩展它。
star只是寻找合理路径的一种方式，并不是寻找全局最优路径。
这里有两个启发式概念：
Admissible heuristic：当对于图中的每个节点n，h(n ) 永远不会高估实现目标的成本。
Consistent heuristic：当对于图中的每个节点n和每个节点m 个后继者，h(n) <= h(m) + c(n,m)，其中 c(n,m) 是从 n 到 m 的弧的成本。
您的启发式函数是可以接受的，但不一致，因为正如您所展示的：
h(A) > h(B) + c(A,B), 5 > 2。
如果启发式是一致的，那么部分解决方案的估计最终成本将始终沿着路径增长，即 f(n) <= f(m) 并且作为我们可以再次看到：
f(A) = g(A) + h(A) = 7 > f(B) = g(B) + h(B) = 5,
这个启发式函数不满足这个属性。
关于A*：
- A* 使用可接受的启发式保证找到从开始到目标的最短路径。
- A*使用一致的启发式算法，除了寻找最短路径外，还保证一旦探索了一个节点我们就已经找到了到该节点的最短路径，因此没有节点需要重新探索.
因此，回答您的问题，必须实施 A* 算法以在找到到节点的较短路径时重新打开节点（同时更新新路径成本），并且这条新路径将被添加到开放集中或边界，因此您的论点不正确，因为 B 必须再次添加到边界（现在路径为 S->A->B，成本为 3）.
如果您可以将 A* 限制为仅与一致的启发式函数一起使用，那么是的，您可以丢弃指向已经探索过的节点的路径。
给定启发式值h(A)=5，h(B)=1，使用A*图搜索，将A和B放在f(A)=2+5=7的边界上， f(B)=4+1=5，则selectB进行扩容，然后将G放在f(G)=4+4=8的边界上，则selectA进行扩容，但不会做任何事情，因为 S 和 B 都已经扩展并且不在边界上，因此它将 select G 接下来和 return 一个非最佳解决方案。
我的论点正确吗？
您在边界上维护一个有序的对象优先级队列。然后，您选择最佳候选者，向所有可用方向扩展，并将新节点放入优先级队列中。因此，即使实际上最佳路径经过它，A 也有可能被推到队列的后面。 A 也有可能被通过 sub-optimal 路径到达的邻居包围，在这种情况下，大多数算法不会像您所说的那样尝试扩展它。
star只是寻找合理路径的一种方式，并不是寻找全局最优路径。
这里有两个启发式概念：
Admissible heuristic：当对于图中的每个节点n，h(n ) 永远不会高估实现目标的成本。
Consistent heuristic：当对于图中的每个节点n和每个节点m 个后继者，h(n) <= h(m) + c(n,m)，其中 c(n,m) 是从 n 到 m 的弧的成本。
您的启发式函数是可以接受的，但不一致，因为正如您所展示的：
h(A) > h(B) + c(A,B), 5 > 2。
如果启发式是一致的，那么部分解决方案的估计最终成本将始终沿着路径增长，即 f(n) <= f(m) 并且作为我们可以再次看到：
f(A) = g(A) + h(A) = 7 > f(B) = g(B) + h(B) = 5,
这个启发式函数不满足这个属性。
关于A*：
- A* 使用可接受的启发式保证找到从开始到目标的最短路径。
- A*使用一致的启发式算法，除了寻找最短路径外，还保证一旦探索了一个节点我们就已经找到了到该节点的最短路径，因此没有节点需要重新探索.
因此，回答您的问题，必须实施 A* 算法以在找到到节点的较短路径时重新打开节点（同时更新新路径成本），并且这条新路径将被添加到开放集中或边界，因此您的论点不正确，因为 B 必须再次添加到边界（现在路径为 S->A->B，成本为 3）.
如果您可以将 A* 限制为仅与一致的启发式函数一起使用，那么是的，您可以丢弃指向已经探索过的节点的路径。