如何識別「A *」（A STAR）算法？

-2

我的直覺和假設是，只要我們不能使用貪婪，那麼A *就是要走的路，但我不是100％確定的。我需要更多關於如何識別和識別A *算法的示例和模式。如何識別「A *」（A STAR）算法？

有人可以給一些特殊的極端情況，當你第一次看到它，你知道這不會是貪婪或它必須是A *，甚至沒有嘗試。

2012-09-14 peter

什麼是你的貪婪算法？ A * *是貪婪算法。 –

如果不是貪心，那麼'A *'根本不正確。 'A *'用於估算方向，並將其應用於'DFS'。有很多問題不能/不應該用DFS解決，所以不能/不應該用'A *'解決。 – Shahbaz

@Shahbaz A *不像DFS，它使用優先級隊列，因此它更像是使用簡單隊列的BFS，而DFS使用堆棧。 –

通常使用術語greedy來描述不算backtrack的算法。這些算法通過最大化啓發式（通常是相當「本地」的）來做出選擇，然後永遠不會重新選擇這種選擇。把貪婪的算法想象成一個人挑選蛋糕然後馬上吃掉，而不是把它放在一邊，並調查另一個蛋糕是否會更好。

相比之下，A*是一種回溯算法：它可能在一定深度探索選擇，但隨後可以放棄這些選擇並嘗試其他可能性。

因此，如果您的問題存在「死路一條」（局部最大值），而解決方案無法取得進一步進展，那麼貪婪算法很可能不適用。但這並不一定意味着A *及其變體是您唯一的選擇。有跡象表明，使用不同的技術從死角逃脫許多其他類型的搜索算法：simulated annealing，Monte Carlo tree search，tabu search，particle swarm optimization ...

來源

2012-09-14 17:25:41

有趣的是，蒙特卡洛樹搜索（MCTS）與所謂的「陷阱狀態」具有完全相同的問題。雖然該算法確實在探索，但它可能會導致誤入歧途，並陷入次優狀態。在ICAPS 2011上有關於這種現象的一篇很好的論文。 –

一個貪婪算法失敗的經典案例是走向目標附近的走廊。如果您有距離目標的啓發式算法，那麼貪婪算法會沿着走廊走下去，因爲這些位置更接近目標。例如，

_ _ _ _ _ _ _ _ _ _ 
| . S . . . . | G | 
| . _ _ _ _ _ | . | 
| . . . . . . . . | 
| _ _ _ _ _ _ _ _ |

注意，代理必須走「遠離」的目標（G）去從一開始（S），這是不是貪心算法建議的目標。

來源

2012-09-14 17:06:29

A *是單源單目的最短路徑算法。

當您可以將問題呈現爲最短距離問題時，您可以使用它，並且您可以找到一個不會高估的啓發式方法（例如，使用歐幾里德距離）。

來源

2012-09-14 22:27:47 maniek

如何識別「A *」（A STAR）算法？

回答

相關問題