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

Question

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

该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 recorded parent if this new path is better than previous one.
done

"OPEN的最佳节点"是一个启发式函数,用于估计节点与目标的接近程度,实际上是Greedy BFS.我对吗？

编辑:评论Anonymouse的答案:

所以基本上贪婪的BFS不需要"OPEN列表",而且应该只根据当前节点做出决定？这个算法是GBFS:

1. Set START as CURRENT node
2. Add CURRENT to Path [and optinally, to CLOSED?]
3. If CURRENT is GOAL, exit
4. Evaluate CURRENT's successors
5. Set BEST successor as CURRENT and go to 2.

Answer 1

"最佳第一"可以允许修改决策,而在贪婪算法中,决策应该是最终的,而不是修改.

例如,A*-search是最佳搜索,但并不贪心.

但请注意,这些术语并不总是使用相同的定义."贪婪"通常意味着决定永远不会被修改,最终接受次优解决方案,从而有利于改善运行时间.但是,我打赌你会发现"贪婪"用于"最佳第一+深度优先"的组合情况,如"尝试扩展最佳下一步直到我们达到死胡同,然后返回上一步并继续那里的下一个最好"(我称之为"优先深度优先").

此外,它取决于您所谈论的抽象级别.A*在"建立路径"中并不贪心.保持一大堆开放路径很好.然而,在"扩大搜索空间"方面走向真正的最短路径是贪婪的.

Answer 2

BFS 是树搜索和图搜索算法的一个实例，其中根据评估函数选择一个节点进行扩展f(n) = g(n) + h(n)，其中g(n) 是从根节点到目标节点的路径长度n，是从到目标节点的h(n)路径长度的估计。n。f(n)在BFS算法中，选择评价最低（即最低 ）的节点进行扩展。

贪心 BFS 使用以下评估函数f(n) = h(n)，即启发式函数h(n)，估计n与目标的接近程度。因此，贪婪的 BFS 尝试扩展被认为最接近目标的节点，而不考虑先前收集的知识（即g(n)）。

总而言之，这些（类似）搜索方法之间的主要区别在于评估函数。

附带说明一下，A* 算法是最佳优先搜索算法，其中启发式函数h是可接受的启发式（即，对于所有），h总是低估完美启发式函数）。A* 不是贪婪 BFS 算法，因为它的评估函数是。h*nf(n) = g(n) + h(n)

Answer 3

在我问这个问题十年后，我回过头来，终于明白了维基百科上那篇文章的意思。

贪婪 BFS 贪婪地扩展当前节点的潜在更好的后继节点。两种算法之间的区别在于处理后继者评估的循环。最佳优先搜索总是通过评估当前节点的后继节点来耗尽它们，并继续选择其中最好的节点：

    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 recorded parent if this new path is better than previous one.

如果贪心 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. For each successor do:
   a. If it is not in CLOSED: 
       i. Evaluate it, add it to OPEN, and record its parent
       ii. If it has a better heuristic than n: remove n from CLOSED, add n to OPEN 
           (after the current successor) and break from loop 3.
   b. Otherwise: change recorded parent if this new path is better than previous one.
done

我已经从上面的 BFS 代码中删除了该步骤3. Create n's successors.，因为 n 的某些后继者可能不会被评估，因此创建它们是没有用的。相反，每个后继者都应该在 中创建并立即评估3. For each successor do:。