artificial-intelligence - 最佳优先搜索是最优和完整的吗？

Question

我对最佳优先搜索算法有一些疑问。我的伪代码如下:
best first search pseudocode

第一个问题:是否完整？我读过这不是因为它可以进入死胡同，但我不知道什么时候会发生，因为如果算法选择一个没有更多邻居的节点，它不会卡在其中，因为这个节点被删除从开放列表中，在下一次迭代中，开放列表的下一个节点被处理并继续搜索。

第二个疑问:它是最优的吗？我认为如果它在搜索过程中访问更接近目标的节点，那么解决方案将是最短的，但事实并非如此，我不知道这样做的原因，因此，造成这种情况的原因算法不是最优的。

我使用的启发式方法是两点之间的直线距离。

谢谢你的帮助!!

Answer 1

当然，如果启发式函数低估了成本，则最佳优先搜索不是最优的。事实上，即使您的启发式函数完全正确，也不能保证最佳优先搜索是最优的。这是一个反例。考虑下图:


绿色数字是实际成本，红色数字是精确的启发式函数。让我们尝试找到从节点 S 到节点 G 的路径。
最好的第一次搜索将按照启发式函数为您提供 S->A->G。但是，如果您仔细查看该图，您会发现路径 S->B->C->G 的成本较低，为 5 而不是 6。因此，这是在完美启发式下执行次优的最佳优先搜索的示例功能。