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

Question

我对最佳优先搜索算法有一些疑问。我拥有的伪代码如下： 最佳优先搜索伪代码

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

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

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

谢谢你的帮助！！

Answer 1

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

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

Answer 2

在一般情况下，最佳优先搜索算法是完整的，因为在最坏的情况下，它将搜索整个空间（最差的选择）。现在，它也应该是最优的 - 考虑到启发式函数是可接受的 - 这意味着它不会高估从任何节点到目标的路径成本。（它还需要一致 - 这意味着它遵循三角不等式，如果不是，那么算法将不完整 - 因为它可能进入循环）

检查你的算法我不明白启发式函数是如何计算的。我也没有看到计算到达特定节点的路径的成本。因此，它需要计算到达特定节点的路径的实际成本，然后需要添加从该节点到目标的路径成本的启发式估计。

公式为：f(n)=g(n)+h(n)其中 g(n) 是到达节点的路径成本，h(n) 是估计从 n 到目标的最便宜路径成本的启发法。

检查A* 算法的实现，这是路径规划中最佳优先搜索的示例。

TLDR在最佳优先搜索中，您需要将节点的成本计算为到达该节点的路径成本与估计从该节点到目标的路径成本的启发式函数的总和。如果启发式函数是可接受的且一致的，则算法将是最优且完整的。