假设启发式值为h(A)=5，h(B)=1，在使用A*图搜索时，它将放置A和B在前沿，其中f(A)=2+5=7，f(B)=4+1=5，然后选择B进行扩展，然后将G放在前沿，f(G)=4+4=8，然后选择A进行扩展，但不会采取任何行动，因为S和B都已经被扩展且不在前沿，因此下一步将选择G并返回非最优解。
我的论点正确吗？
A*图搜索
3
- James
1
该启发式是可接受的，但不一致。h(A)是从A到G的估计成本，而不是从S到A，因此它不是一个高估值。在图搜索中，不应重新打开B，因为B已经在探索集合中被扩展过了？（它只应该打开前沿/未探索集合中的节点） - James
2个回答
2
这里有两个启发式概念：
1.可采纳的启发式：对于图中每个节点n，h(n)从不高估到达目标的成本。
2.一致的启发式：对于图中的每个节点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*算法：
1.A*使用可采纳的启发式保证找到从起点到目标的最短路径。
2.A*使用一致的启发式不仅可以找到最短路径，而且还保证一旦探索了一个节点，我们已经找到了到达该节点的最短路径，因此不需要重新探索任何节点。
回答你的问题，当发现到节点的更短路径时（同时更新新路径成本），必须重新打开节点并将新路径添加到开放集或前沿中。因此，你的论点是不正确的，因为B必须再次添加到前沿（现在是S->A->B路径和成本3）。
如果可以限制A*仅使用一致的启发式函数，则可以丢弃已经探索过的节点的路径。
1.可采纳的启发式：对于图中每个节点n，h(n)从不高估到达目标的成本。
2.一致的启发式：对于图中的每个节点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*算法：
1.A*使用可采纳的启发式保证找到从起点到目标的最短路径。
2.A*使用一致的启发式不仅可以找到最短路径，而且还保证一旦探索了一个节点，我们已经找到了到达该节点的最短路径，因此不需要重新探索任何节点。
回答你的问题，当发现到节点的更短路径时（同时更新新路径成本），必须重新打开节点并将新路径添加到开放集或前沿中。因此，你的论点是不正确的，因为B必须再次添加到前沿（现在是S->A->B路径和成本3）。
如果可以限制A*仅使用一致的启发式函数，则可以丢弃已经探索过的节点的路径。
- FrankS101
-1
你需要维护一个有序的优先队列，其中包含了前沿对象。然后你选择最佳候选者，在所有可用方向上进行扩展，并将新节点放入优先队列中。因此，即使实际上最优路径经过A，它也可能被推到队列的末尾。同时，A也可能被邻居所包围，这些邻居是通过次优路径到达的，大多数算法不会尝试扩展它。
A星算法只是一种寻找合理路径的方法，它并不能找到全局最优路径。
- Malcolm McLean
1
通常是错误的。当启发式函数是可接受的时，A*算法保证找到最短路径。 - FrankS101
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接