小编典典

贪婪的最佳第一搜索算法是否与最佳第一搜索算法不同?

algorithm

贪婪的 最佳第一搜索算法是否与最佳第一搜索算法不同?

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

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

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

“贪婪的BFS”实际上是“贪婪的BFS”,其中“ OPEN中的最佳节点”是一种启发式函数,用于估计节点与目标的距离。我对吗?

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

因此,贪婪的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.

阅读 267

收藏
2020-07-28

共1个答案

小编典典

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

例如,A *搜索是最佳优先搜索,但并非贪婪。

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

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

2020-07-28