贪婪的 最佳第一搜索算法是否与最佳第一搜索算法不同?
该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.
“最佳第一”可以允许 修改 决策,而在贪婪算法中,决策应该是最终决策,而不是修改决策。
例如,A *搜索是最佳优先搜索,但并非贪婪。
但是,请注意,这些术语并不总是与相同的定义一起使用。“贪婪”通常表示该决策永远不会修改,最终会因为运行时间的缩短而接受次优的解决方案。但是,我敢打赌,您会发现以下情况:“贪婪”用于“最佳第一+深度优先”的组合,如“尝试扩展最佳下一步直到遇到死胡同,然后返回上一步并继续”最好的”(我将其称为“优先深度优先”)。
另外,它取决于您所讨论的抽象级别。A *在“构建路径”中并不贪婪。保持大量开放路径很好。但是,它在向真正的最短路径“扩展搜索空间”方面很贪婪。