我对最佳搜索算法有一些疑问。我拥有的伪代码如下：best first search pseudocode
首先怀疑：它完成了吗？我已经读过它并不是因为它可以进入死胡同，但我不知道什么时候会发生，因为如果算法选择一个没有更多邻居的节点，它就不会被卡在其中因为这个节点被删除了从打开列表开始，在下一次迭代中，处理打开列表的以下节点并继续搜索。
第二个疑问：它是最优的吗？我认为如果它在搜索过程中访问更接近目标的节点，那么解决方案将是最短的，但它不是那样的，我不知道原因，因此，这使得这个算法不是最优的。
我使用的启发式是两点之间的直线距离。
谢谢你的帮助！！
在一般情况下，最好的第一搜索算法是完整的，因为在最坏的情况下它将搜索整个空间（最差的选项）。现在，它应该也是最优的 - 假设启发式函数是可接受的 - 这意味着它不会高估从任何节点到目标的路径的成本。 （它也需要保持一致 - 这意味着它坚持三角不等式，如果不是那么算法就不会完整 - 因为它可能进入一个循环）
检查算法我没看到如何计算启发式函数。此外，我没有看到计算到达特定节点的路径的成本。因此，它需要计算到达特定节点的路径的实际成本，然后需要添加从节点到目标的路径成本的启发式估计。
公式为f(n)=g(n)+h(n)，其中g（n）是到达节点的路径的成本，h（n）是估计从n到目标的最便宜路径的成本的启发式算法。
检查A* algorithm的实现，这是路径规划中最佳第一次搜索的示例。
TLDR在最佳第一次搜索中，您需要计算节点的成本，作为到达该节点的路径的成本和估计从该节点到目标的路径成本的启发式函数的总和。如果启发式函数是可接受的且一致的，则算法将是最佳且完整的。
当然，如果启发式功能低估了成本，那么最好的首次搜索不是最优的。实际上，即使您的启发式功能完全正确，也绝不能保证最佳的首次搜索是最佳的。这是一个反例。请考虑以下图表：
绿色数字是实际成本，红色数字是确切的启发式功能。让我们尝试找到从节点S到节点G的路径。最佳的第一次搜索会在启发式函数之后给出S-> A-> G.但是，如果仔细观察图形，您会看到路径S-> B-> C-> G的成本较低而不是6。因此，这是在完美启发式下执行次优的最佳首次搜索的示例功能。