Greedy最佳優先搜索與Best-first搜索不同嗎？

一個術語問題 - 是貪婪的最佳優先搜索與最佳優先搜索不同嗎？Greedy最佳優先搜索與Best-first搜索不同嗎？

wiki page有一個關於貪婪BFS的單獨的段落，但它有點不清楚。

我的理解是，貪婪的BFS只是BFS，其中維基百科算法中「OPEN的最佳節點」是一個爲節點計算的啓發函數。因此，實施這個：

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

與作爲一個啓發函數估計節點如何接近目標「從OPEN最好的節點」，實際上是貪婪BFS。我對嗎？

編輯：評點Anonymouse的回答是：

所以基本上貪婪BFS並不需要一個「開放列表」，應立足僅在當前節點上的決定？這是算法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.

來源

2011-12-04 Alex

「最佳第一」可能允許修改的決定，而在貪婪算法，該決定是終局的，而不是修改。

例如，A * -search是最佳優先搜索，但它不是貪婪。

瞭解，但是，這些術語並不總是與相同的定義一起使用。「貪婪」通常意味着決策從不修改，最終接受不理想的解決方案，從而改善運行時間。然而，我敢打賭，你會發現「貪婪」被用於「最優先+深度優先」組合的情況，如「嘗試展開最佳下一步直到我們遇到死衚衕，然後返回前一步並繼續與那裏的下一個最好「（我將稱之爲」優先深度優先「）。

另外它取決於你正在談論的抽象級別。 A *在「建造路徑」中並不貪心。保持大量開放路徑是很好的。然而，「擴大搜索空間」朝着真正的最短路線是貪婪的。

來源

2011-12-04 09:30:35

你會如何改變上面的算法來反映這一點？ – Alex

這不適用於所有問題。例如在路徑發現中，真正的貪婪算法通常會因失敗而失敗。「優先深度優先」會找到一條好路徑，但當初始選擇不好時可能會錯過最好的路徑。 A *是最佳優先搜索，只有在確定沒有更好的路徑時纔會終止。 –

你能評論我的問題中的編輯嗎？ – Alex

這是我的理解，最佳優先搜索只是您使用啓發式評估函數h（n）的特定搜索技術的集體名稱。所以A *和貪婪最佳優先搜索也屬於這一類。

如果我錯了，請糾正我！

來源

2011-12-14 17:41:43

BFS是其中一個節點是基於一個評價函數f(n)選擇用於擴展樹搜索和圖搜索算法的一個實例。

傳統上，選擇評估最低的節點進行擴展，因爲評估會測量到目標的距離。

BFS使用優先級隊列。

貪婪的BFS試圖擴展最接近目標的節點，因爲這導致解決方案很快。因此，它僅通過使用啓發式功能f(n) = h(n)來評估節點。

來源

2012-06-07 13:47:20

總結：BFS使用f = g + h，如果h是可容許的啓發式，貪婪BFS使用f = h，並且A *是BFS。 – Ali

Greedy最佳優先搜索與Best-first搜索不同嗎？

回答

相關問題