贪婪最好的第一次搜索和深度优先搜索

Question

贪婪最佳优先搜索可能在任何情况下的深度优先搜索行为？

我看到这两种算法的最坏情况是相似的O（b^m）。这是否意味着他们的行为方式相同？

Answer 1

Greedy Best First Search在任何情况下的行为都可能与Depth First Search类似吗？

不，如果是的话，它会是深度优先搜索。

我看到这两种算法的最坏情况是类似的O（b^m）。这是否意味着他们的行为方式相同？

号

Answer 2

“最佳第一”只是意味着它完全依靠一些启发式该分数可能的选项，并首先扩展的最佳选择。深度优先搜索不使用这种启发式。

想一想，它的一个方法是Djiksta将返回图中具有非负边的最短路径。当您添加最佳优先搜索的评分机制时，您会得到A *。带走Djikstra，你会再次回到最佳状态。