贪婪最佳优先搜索与最佳优先搜索有什么不同吗?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (153)

一个术语问题 - 是贪婪最佳优先搜索与最佳优先搜索不同吗?

我的理解是,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。

所以基本上贪婪的BFS不需要一个“OPEN list”,并且应该只在当前节点上做出决定?这个算法是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.
提问于
用户回答回答于

“最优先”可能允许修改决定,而在贪婪算法中,决策应该是最终的,而不是可修改的。

用户回答回答于

BFS是树搜索图搜索算法的一个实例,其中根据评估函数 选择节点进行扩展f(n)

传统上,选择具有最低评估的节点进行扩展,因为评估测量到目标的距离。

BFS使用优先级队列。

贪婪的BFS试图扩展最接近目标的节点,因为这导致解决方案很快。因此它仅通过使用启发式函数 来评估节点f(n) = h(n)

所属标签

可能回答问题的人

  • uncle_light

    5 粉丝518 提问6 回答
  • 优惠活动秘书

    0 粉丝2 提问6 回答
  • 最爱开车啦

    8 粉丝503 提问6 回答
  • 天使的炫翼

    17 粉丝531 提问5 回答

扫码关注云+社区

领取腾讯云代金券