最佳的优先搜索是否最佳且完整? [英] Is best first search optimal and complete?

问题描述

我对最佳的优先搜索算法有一些疑问.我拥有的伪代码如下: 最佳首次搜索伪代码

I have some doubts regarding best first search algorithm. The pseudocode that I have is the following: best first search pseudocode

第一个疑问:它完成了吗?我已经读过它不是因为它可以进入死胡同，但是我不知道什么时候会发生，因为如果算法选择的节点没有更多的邻居，它不会卡在其中，因为该节点已被删除从打开列表开始，在下一次迭代中，将处理打开列表的以下节点，并继续搜索.

First doubt: is it complete? I have read that it is not because it can enter in a dead end, but I don't know when can happen, because if the algorithm chooses a node that has not more neighbours it does not get stucked in it because this node is remove from the open list and in the next iteration the following node of the open list is treated and the search continues.

第二个疑问:这是最优的吗?我以为，如果沿着搜索过程访问距离目标更近的节点，那么解决方案将是最短的，但事实并非如此，我也不知道其原因，因此也无法确定其原因.算法不是最佳的.

Second doubt: is it optimal? I thought that if it is visiting the nodes closer to the goal along the search process, then the solution would be the shortest, but it is not in that way and I do not know the reason for that and therefore, the reason that makes this algorithm not optimal.

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

The heuristic I was using is the straight line distance between two points.

感谢您的帮助！

推荐答案

当然，如果启发式功能低估了成本，那么最佳的优先搜索并不是最佳的.实际上，即使您的启发式功能完全正确，也绝不能保证最佳的优先搜索是最佳的.这是一个反例.请看下图:

Of course, if heuristic function underestimates the costs, best first search is not optimal. In fact, even if your heuristic function is exactly right, best first search is never guaranteed to be optimal. Here is a counter example. Consider the following graph:

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

The green numbers are the actual costs and the red numbers are the exact heuristic function. Let's try to find a path from node S to node G. Best first search would give you S->A->G following the heuristic function. However, if you look at the graph closer, you would see that the path S->B->C->G has lower cost of 5 instead of 6. Thus, this is an example of best first search performing suboptimal under perfect heuristic function.

这篇关于最佳的优先搜索是否最佳且完整?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！