統一費用搜索算法

Question

我剛剛在一本書和維基百科上閱讀了它，但仍然沒有100％的理解它。

我真的很感激，如果有人可以用一個或兩個例子來解釋它。

謝謝

Answer 1

我假設你在看this Wikipedia page。這意味着給定操作（添加兩個數字，比較兩個數字，從內存中檢索數據等）所需的時間與所涉及變量的大小無關。換句話說，8位比較與32位比較需要相同的時間。通過這種假設，您可以簡化效率分析並比較算法，而不會陷入實施細節中。

Answer 2

說我在看地圖，在城市附近尋找我的街區附近的比薩餅店。我可以使用幾種不同的策略：

• 廣度優先搜索（BFS）：查看我的街區周圍的同心圓塊，向外和向外直到我找到一個披薩店。這會給我一個與烏鴉飛得最近的比薩餅店。
• 深度優先搜索（DFS）：沿着一條路走，直到我遇到死路，然後回溯。最終所有可能的分支都會被搜索到，所以如果某處有一家披薩店，那麼我會找到它，但它可能不會很接近我的區塊。
• 統一費用搜索（UCS）：說一些街道上的流量不好，我真的很熟悉這個城市。對於任何給定的位置，我可以說我需要多久才能從我的街區到達那裏。所以，看看地圖，首先搜索所有需要1分鐘或更短時間才能完成的模塊。如果我還沒有找到一家披薩店，我會搜索所有需要1到2分鐘才能到達的街區。我重複這個過程，直到我找到一個披薩店。這會給我一個比我的街區最近的比薩餅店。就像BFS看起來像同心圓一樣，UFS看起來像a contour map。

通常情況下，您將使用優先級隊列實現UCS，以最低成本的順序搜索節點。