动态加权的 A* 搜索优势
我正在阅读 A* 搜索算法的变体，并遇到了动态加权。据我了解，权重应用于搜索方程，随着搜索越来越接近目标节点，权重会减小。我专门看这篇文章：http : //theory.stanford.edu/~amitp/GameProgramming/Variations.html
谁能告诉我这有什么好处？为什么你不在乎你一开始扩展了哪些节点？它是为了帮助不一定具有良好启发式的搜索吗？
谢谢
对于 TLDNR 人群：
动态加权牺牲了解决方案的最优性来加速搜索。权重越大，搜索越贪婪。
对于我的同行学者：
动机
来自维基百科A-star文章： A-star的可接纳性准则保证了最优解路径，但这也意味着A*必须检查所有同样有价值的路径才能找到最优路径。我们可以通过放宽可接纳性标准来获得近似解，以牺牲最优性为代价加快搜索速度。通常我们想要限制这种松弛，这样我们就可以保证解路径不比最优解路径差 (1 + ?) 倍。这种新的保证被称为 ?-admissible。
静态加权
在我们讨论动态加权之前，让我们将 A-star 与最简单的 ?-容许松弛进行比较：静态加权 A-star。
在静态加权的 A 星中，f(n) = g(n) + w·h(n)，对于某些 ?>0，w=(1+?)。为了说明对最优性和搜索速度的影响，请比较以下每个插图中扩展的节点数。空圆圈代表开集中的节点；实心圆在闭集内。
A 星（左）与 ?=4 的加权 A 星（右）
如您所见，加权 A-star 扩展的节点要少得多，并且完成速度大约是其 3 倍。然而，由于我们使用了 ?=4，加权 A-star 理论上可以返回 (1+?)=(1+4)=5x 倍于最优路径的解。
动态加权
动态加权是一种使启发式权重成为搜索状态的函数的技术，即 f(n) = g(n) + w(n)·h(n)，其中 w(n) = (1 + ? - ( ?*d(n))/N)，d(n) 是当前搜索的深度，N 是搜索深度的上限。
通过这种方式，动态权重 A-Star 最初的行为非常类似于 Greedy Best First 搜索，但是随着搜索深度（即图中的跳数）的增加，该算法采取了更保守的方法，表现得更像传统的A星算法。
使用动态加权，您假设在搜索开始时，快速到达（任何地方）更为重要；在搜索结束时，更重要的是达到目标。
他是对的，但我想说，对于动态加权，您假设在搜索开始时，遵循启发式方法更为重要；在搜索结束时，考虑路径的长度也同样重要。
其他材料和链接：
- 助理。Ira Pohl 教授 --启发式问题解决中的（相对）灾难的避免、启发式能力、真正的动态加权和计算问题
- Amit Patel 的 A* 变体的动态加权
- 维基百科——A* 搜索算法的有界松弛