A *動態加權的搜索優勢

Question

我正在閱讀有關A *搜索算法的變體，並且我遇到了動態加權。據我所知，搜索等式中應用了權重，搜索等式越接近目標節點越小。我是特意看這篇文章：http://theory.stanford.edu/~amitp/GameProgramming/Variations.html

誰能告訴我這將是什麼好處？爲什麼你不關心你在開始時擴展的節點？它是否有助於不一定具有良好啓發性的搜索？

由於

Answer 1

對於TLDNR-人羣：

動態加權犧牲溶液最優到加速搜索。重量越大，搜索越貪婪。

對於我的同胞學者：

動機

從維基百科的A級明星的文章： A級明星的受理標準保證了最佳的解決途徑，但它也意味着A *必須檢查所有同樣有功的路徑來找到最佳路徑。我們可以通過放寬可接受性標準來獲得一個近似的解決方案，以犧牲最優性爲代價來加速搜索。通常我們想限制這種鬆弛，這樣我們可以保證解路徑不會比（1 +ε）乘最佳解路徑差。這個新的保證被稱爲ε可容許的。

靜態稱重

我們談論動態加權之前，讓我們比較A-明星最簡單的ε-受理鬆弛：靜態加權A級明星。在靜態加權的A-星中，對於一些ε> 0，f（n）= g（n）+ w·h（n），w =（1 +ε）。爲了說明對最優性和搜索速度的影響，請比較以下每個示例中展開的節點數。空圈代表開放集中的節點;填滿的圓圈在封閉的集合。

A星（左）與加權A星與ε= 4（右）

正如你可以看到，加權A星擴大遠較少的節點，並完成速度約爲3倍。然而，由於我們使用ε= 4，所以加權的A-星理論上可以返回一個解（1 +ε）=（1 + 4）= 5x倍於最佳路徑。

動態加權

動態加權是一種技術，使得啓發式重量搜索狀態的一個函數，即，F（N）= G（N）+ W（N）·H（N），其中，w （n）=（1 +ε - （ε* d（n））/ N），d（n）是當前搜索的深度，N是搜索深度的上限。通過這種方式，動態權重的A-Star最初表現得非常像貪婪最佳搜索，但隨着搜索深度（即圖中跳躍的數量）的增加，算法採用更保守的方法，表現得更像傳統的A星算法。

Amit Patel's page說

使用動態加權，你認爲你的 搜索的開始，它得到（任何地方）快速更重要;在 的搜索結束時，達到目標更爲重要。

他是正確的，但我會用動態加權saythat，您認爲在您的搜索開始，就按照你的啓發是更重要的;在搜索結束時，考慮路徑的長度也同樣重要。

額外的材料和相關鏈接：

1. 助理。伊拉·波爾教授 - The Avoidance of (Relative) Catastrophe, Heuristic Competence, Genuine DYnamic Weighting and Computational Issues in Heuristic Problem Solving
2. Dynamic Weighting對A *
3. 維基百科的阿米特·帕特爾的變種 - Bounded Relaxation for the A* Search Algorithm