當啓發式算法總是低估時，A *算法的最優性證明

Question

我明白爲什麼A *算法總是會在啓發式算法總是低估時給出目標狀態的最佳路徑，但我無法爲其創建正式證明。

據我所知，對於每一條被認爲越深越深的路徑而言，f(n)的準確性會提高，直到目標狀態達到100％的準確度。此外，不會忽略不正確的路徑，因爲估計值低於實際成本;從而導致最佳路徑。但我應該如何爲它創建一個證明？

Answer 1

該證明的主要思想是，當A *找到一條路徑時，找到一條路徑的估計值低於其他可能路徑的估計值。由於估計是樂觀的，其他路徑可以安全地忽略。

此外，A *是唯一的最佳的，如果兩個條件都滿足：

1. 啓發式是受理，因爲它永遠不會高估成本。

2. 啓發式是單調，即，如果H（N _我）< H（N _{i + 1的}），然後實際成本（正_我）<實（n _{i + 1}）。

---

可以證明最優是假設相反，擴大影響正確的。

假設由A *給出的路徑是而不是最優是具有可接受的單調啓發式，並且考慮含義的含義（您很快就會發現自己達到矛盾），因此，您的原來的假設被簡化爲荒謬。

由此可以得出結論：您的原始假設是錯誤的，即A *在上述條件下是最優的。證明完畢

Answer 2

考慮最後一步，即完成最佳路徑的那一步。

爲什麼必須選擇那條路徑？換句話說，爲什麼A *必須避免選擇達到目標的次優道路？

提示：這是啓發式必須受理的原因。請注意，只要沒有完成路徑（爲什麼？），選擇一條次優路徑就可以了。

這應該給你一些關於如何形成證明的想法。