比較不同的搜索算法

Question

DFS和Best-first搜索在哪些方面類似？ BFS和Best-first如何相似？對我來說，爲了更好地描述DFS和BestFS是如何相似的，可以更容易地指出差異，這就是在BestFS中，我們選擇下一個來擴展與使用heuristi函數的目標最接近的目標。在幾乎所有其他方面，最好的和DFS都是相似的。

但是我覺得很難找到BFS和BestFS

Answer 1

之間的相似性好的想象你有一棵樹。你知道它有一個葉子和你想要的數據假設你想通過遍歷樹的各個分支來找到葉子，直到找到它。

隨着Depth First search，如果您在一個分支來了，你會採取分支，然後拿另一支和其它一個又一個，直到你到一個葉。

隨着Breadth first search（請注意，我沒有說「最好先」在這裏），當你遇到一個新的分支將其添加到隊列回來以後，直到找到目前的水平所有分支。通常當人們說「BFS」時，他們的意思是寬度首先搜索，而不是最好的第一。

那麼Best first search，你問過嗎？那麼，假設你正在進行深度優先搜索，並且你遇到了兩個分支。使用DFS時，您只需每次選擇第一個，稍後您將回來選擇另一個。

隨着最佳你選擇具有最高啓發價值的一個分支，根據你使用，以幫助想最好的路徑啓發式優先搜索。因此，Best First搜索是深度優先搜索的類型。

維基百科是very helpful這些類型的問題，順便說一句。

Answer 2

Best First Search是一種知情搜索，適用於您正在搜索的狀態空間的某些信息已知的場景。通過熟悉狀態空間或您正在工作的系統，可以幫助開發一種啓發式方法，在每個搜索步驟中確定最佳節點。簡而言之，Best First Search使用貪婪模式來實現目標，即您的搜索目標。

深度第一搜索和廣度優先搜索是不知情的搜索方法，當您對所處理的系統一無所知時，它們非常方便。他們在記憶和保證方面有自己的權衡（相互之間）以找到解決方案（如果存在的話）。您可以在Wiki查看詳情。

除了有助於解決搜索問題之外，我沒有在非知情搜索方法和知情搜索方法之間看到很多相似之處。可以爭論相似性的另一個方面是搜索是否完成（搜索方法在其存在時返回解決方案時稱爲完整）和最優（當搜索方法返回最小成本路徑解決方案時解決方案存在）。

廣度優先搜索 - 完整和優化（如果所有的邊緣有單位成本）

深度優先搜索 - 完整（爲有限搜索樹），而不是最佳

最佳優先搜索 - 完整和優化

關鍵是要知道在哪種情況下使用哪一個。

我希望這會有所幫助。

歡呼聲