贪婪的最佳第一搜索算法是否与最佳第一搜索算法不同？ [英] Is the greedy best-first search algorithm different from the best-first search algorithm?

问题描述

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

维基页面中有关于贪婪BFS的单独段落，但还不清楚。

我的理解是，贪婪的BFS只是Wikipedia算法中 OPEN中的最佳节点是一个为节点计算的启发式函数的BFS。所以实现这个：

  OPEN = [初始状态] 
 CLOSED = [] 
而OPEN不是空
做
 1.从OPEN中删除最佳节点，将其命名为n，然后将其添加到CLOSED。 
 2.如果n是目标状态，则返回n的回溯路径（通过记录的父级）并返回路径。 
 3.创建n个继承者。 
 4.对于每个后继者：
 a。如果未处于关闭状态：请对其进行评估，将其添加到打开中并记录其父项。 
 b。否则：如果此新路径比上一条更好，请更改已记录的父项。 
完成了
  

其中 OPEN中的最佳节点是一种启发式函数，用于估计节点的接近程度是达到目标的，实际上是贪婪的BFS。我对吗？

编辑：评论匿名者的答案：

贪婪的BFS不需要 OPEN列表，它的决定应该仅基于当前节点吗？这个算法是GBFS吗？

  1。将START设置为CURRENT节点
 2.将CURRENT添加到路径中[[最后是关闭吗？] 
 3.如果CURRENT是GOAL，则退出
 4.评估CURRENT的后继者
 5。将最佳后继设置为当前，然后转到2。
  

解决方案

最佳第一可以允许修改决定，而在贪婪算法中，决定应该是最终决定，不得修改。

例如，A *搜索是最佳的优先搜索，但并不贪心。

但是，请注意，这些术语并不总是使用相同的定义。 贪婪通常意味着该决策永远不会修改，最终会因为运行时间的缩短而接受次优解决方案。但是，我敢打赌，您会发现以下情况：贪婪用于最佳第一+深度优先的组合，如尝试扩展最佳下一步直到遇到死胡同，然后返回上一步并继续

此外，还取决于您所讨论的抽象级别。 A *在构建路径中并不贪婪。保持大量开放路径很好。但是，在将搜索空间扩展到真正的最短路径方面却很贪婪。

Is the greedy best-first search algorithm different from the best-first search algorithm?

The wiki page has a separate paragraph about Greedy BFS but it's a little unclear.

My understanding is that Greedy BFS is just BFS where the "best node from OPEN" in wikipedia's algorithm is a heuristic function one calculates for a node. So implementing this:

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

with "best node from OPEN" being a heuristic function estimating how close the node is to the goal, is actually Greedy BFS. Am I right?

EDIT: Comment on Anonymouse's answer:

So essentially a greedy BFS doesn't need an "OPEN list" and should base its decisions only on the current node? Is this algorithm 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.

解决方案

"Best first" could allow revising the decision, whereas, in a greedy algorithm, the decisions should be final, and not revised.

For example, A*-search is a best-first-search, but it is not greedy.

However, note that these terms are not always used with the same definitions. "Greedy" usually means that the decision is never revised, eventually accepting suboptimal solutions at the benefit of improvements in running time. However, I bet you will find situations where "greedy" is used for the combination of "best first + depth first" as in "try to expand the best next step until we hit a dead end, then return to the previous step and continue with the next best there" (which I would call a "prioritized depth first").

Also, it depends on which level of abstraction you are talking about. A* is not greedy in "building a path". It's fine with keeping a large set of open paths around. It is however greedy in "expanding the search space" towards the true shortest path.

这篇关于贪婪的最佳第一搜索算法是否与最佳第一搜索算法不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！