A *啓發式，高估/低估？

Question

我對高估/低估條款感到困惑。我完全瞭解A *算法的工作原理，但我不確定是否存在高估或低估的啓發式效應。

當你採取直接鳥瞰線的平方是高估？爲什麼它會使算法不正確？所有節點都使用相同的啓發式方法。

當你採取直接鳥瞰線的平方根時，低估了嗎？爲什麼算法仍然正確？

我無法找到一篇文章，它很好地解釋了它，所以我希望這裏有人有一個很好的描述。

Answer 1

你高估時啓發式的估計比實際的最終路徑成本較高。你低估了它什麼時候更低（你不必低估，你只是不要高估; 正確估計沒有問題）。如果圖的邊緣成本都是1，那麼你給出的例子會提供高估和低估，儘管平面座標距離在笛卡爾空間中也可以起作用。

高估並不能確切地使算法「不正確」;這意味着你不再有可接受的啓發式，這是A *保證產生最佳行爲的條件。使用不可接受的啓發式算法，該算法可能會花費大量的多餘工作檢查應該忽略的路徑，並且可能會因爲探索這些路徑而找到次優路徑。這是否真的發生取決於你的問題空間。發生這種情況的原因是路徑成本與估計成本「不成比例」，這實際上給算法帶來了有關哪條路徑比其他路徑更好的想法。

我不確定你是否會找到它，但你可能想看看Wikipedia A* article。我提到（和鏈接）主要是因爲它幾乎不可能。

Answer 2

據我所知，你通常低估，以便你仍然可以找到最短的路徑。您可以通過高估快速找到答案，但是您可能找不到最短路徑。因此，爲什麼高估是「不正確的」，而低估仍然可以提供最好的解決方案。

我很抱歉，我不能提供任何洞察力的鳥瞰線...

Answer 3

從Wikipedia A* article，算法描述的相關部分是：

該算法繼續進行，直到一個目標節點具有比在隊列中的任一節點的下˚F值（或者，直到隊列是空的）。

關鍵的想法是，一旦知道路徑的總成本將超過通往目標的已知路徑的成本，A *將只停止探索到目標的潛在路徑。由於路徑成本的估計總是小於或等於路徑的實際成本，因此只要估計成本超過已知路徑的總成本，A *就可以丟棄路徑。

由於過高估計，A *不知道何時可以停止探索潛在路徑，因爲可能存在實際成本較低但估計成本高於目標最佳路徑的路徑。