在A中使用可接受的和一致的啓發式A *

Question

有人有一個簡單和/或直觀的解釋，爲什麼你必須在A *中使用可接受的啓發式，以及爲什麼「應該」使用一致的啓發式？

Answer 1

容許：

確保我們有多少認爲成本會去的目標不超過它實際上成本。

如果實際成本高於實際成本，我們實際上最終可能會走上更加昂貴的道路，因爲實際成本可能比我們認爲這條路徑花費多少便宜。

一致：

如果我們朝目標移動，我們不應該突然想它會需要更長的時間比我們剛剛做的目標。 ^[1]

如果我們接近目標，我們突然想到從這裏到達目標需要更長的時間，我們最終可能會在最終到達目標之前探索一大堆其他路徑目標，因爲我們可以認爲這些可能會更便宜。

[1]：我只是在談論我們認爲會花多長時間，而不是花了多長時間 - 因此，我們可能認爲這需要10分鐘，但在旅行5分鐘後，我們現在認爲我們還有7分鐘的時間 - 這很好，但如果我們認爲我們有超過10分鐘的時間，那並不好。

Answer 2

這只是爲了讓你說，找到的結果是「最優」的，你可以使用任何你想要的啓發式方法，只是難以證明找到的結果是最優的。

例如，當您高估到目標節點的距離時，實際距離可能小於估計的距離。因此，找到的結果可能被標記爲「最優」，而仍然存在更好的解決方案。