在加權A *搜索中使用完全g（n）與全h（n）有什麼優點/缺點？

Question

Weighted A* = (1 - weight) * g(n) + weight * h(n) 

從我的理解，做一個完整的搜索基於成本爲您提供了最佳的解決方案，而不是一個完整的啓發式搜索需要更長的時間，反之亦然？它是否正確？還有什麼其他重要的我應該知道嗎？

編輯：好的，我想我更現在明白。完全基於成本進行搜索可以使您找到更長的路徑。但仍然不確定充分的啓發式。

編輯2：使用試探只會讓你到一個節點，但可能已經使用了很長的路？

Answer 1

案例1（全G（N），又名盲目搜索）：

如果您使用的評價函數f(n)選擇下一個路徑只能基於g(n)到探索，你基本上使用的Dijkstra算法。換句話說，如果f(n) = g(n) + h(n)和h(n) = 0,f(n) = g(n)，並且您正在每次迭代中探索最小成本的路徑。這保證找到最佳路徑（圖中只有正向成本），但您可能會探索次優路徑。 例如，在下面的圖中，我們要找到s到t路徑：

 n1    node | h(node) 
    /\     s | 3 
    2/ \ 1    n1 | 1     
    / \    n2 | 4 
    s  t 
    \ /
    1 \ /4 
     \/
     n2 

和表給我們的啓發式評估每個節點（讓我假設我們有一個完美的啓發，即啓發式值總是對應於到目標的最短路徑）。因此，在第一次迭代中，s被擴展並且n1和n2被添加到OPEN列表中。 當執行盲搜索（或全g(n)），則：

• f(n1) = g(n1) = 2。

• f(n2) = g(n2) = 1。

和節點n2將被探討，因爲它在OPEN列表中具有最小g值。

然而，當我們使用A *和啓發值：

• f(n1) = g(n1) + h(n1) = 2 + 1 = 3。

• f(n2) = g(n2) + h(n2) = 1 + 4 = 5。

n1將探索和t之後，導致最佳的解決方案，並通過n2沿途沒有探索次優路徑。

因此，全g(n)意味着Dijkstra算法VS A *。如果你的啓發式算法是一個很好的估計（讓我們這樣簡化），A *將永遠是可取的。

案例2（全H（N））：

我們這裏有不同的情況，因爲我們沒有使用的路徑已經找到，我們只相信我們的函數的啓發式評估的成本。根據啓發式的質量，您可以最終探索圖中的所有節點或者僅探索最佳路徑，但是您失去了A *的美麗理論特性。