貪婪最好的第一次搜索和深度優先搜索

Question

貪婪最佳優先搜索可能在任何情況下的深度優先搜索行爲？

我看到這兩種算法的最壞情況是相似的O（b^m）。這是否意味着他們的行爲方式相同？

Answer 1

Greedy Best First Search在任何情況下的行爲都可能與Depth First Search類似嗎？

不，如果是的話，它會是深度優先搜索。

我看到這兩種算法的最壞情況是類似的O（b^m）。這是否意味着他們的行爲方式相同？

號

Answer 2

「最佳第一」只是意味着它完全依靠一些啓發式該分數可能的選項，並首先擴展的最佳選擇。深度優先搜索不使用這種啓發式。

想一想，它的一個方法是Djiksta將返回圖中具有非負邊的最短路徑。當您添加最佳優先搜索的評分機制時，您會得到A *。帶走Djikstra，你會再次回到最佳狀態。