标签: best-first-search

贪心最佳优先搜索算法是否与最佳优先搜索算法不同？

该wiki页面大约有贪婪的BFS一个单独的段落,但它是一个有点不清楚.

我的理解是,Greedy BFS只是BFS,其中维基百科算法中的"OPEN最佳节点"是一个为节点计算的启发式函数.所以实现这个:

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
   a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
   b. Otherwise: change …

这两种方法都有一个数据结构,可以保持节点(及其成本)的扩展.两种方法首先以最高成本扩展节点.那么,它们之间有什么区别？

有人告诉我,统一成本搜索是一种盲目的方法,最好先搜索不是,这让我更加困惑(两者都有关于节点成本的信息？).

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

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

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

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

谢谢你的帮助！！