A *搜索的最優效率證明

Question

在Norvig的人工智能中提到A *搜索是最優效率的。但是，我無法弄清楚爲什麼也沒有在網上找到證據。有人碰巧有證據嗎？

Answer 1

我希望我沒有做你的功課;）。我只在這裏草擬證明

你需要看到的第一件事是A *是最佳。那就是根據你的成本函數g返回最短路徑。我認爲這個證明是微不足道的，因爲啓發式h並沒有高估解決方案的成本。如果這不會保持最佳效率將是沒有意義的，因爲A*不會是最佳的。

最優效率：從同一個名字節點A *啓動所有最佳算法中被花費節點最少。

讓我們假設算法B不擴展節點n這就是A*擴展爲A*。根據此路徑的定義g(n)+h(n) <= f其中f是最短路徑的成本。考慮所有啓發式值與原始問題相同的第二個問題。但是，總成本更小的新目標有一條新路徑，即f。 假設算法B將擴大n因此永遠不會達到這個新目標。因此，B不會找到此最佳路徑。因此，我們原來的假設B是最優的違反。