A*搜索动态加权的优势
A* Search Advantages of Dynamic Weighting
我在阅读 A* 搜索算法的变体时遇到了动态加权。据我了解，权重应用于搜索方程式，随着搜索越来越接近目标节点，权重会减小。我是专门看这篇文章的：http://theory.stanford.edu/~amitp/GameProgramming/Variations.html
谁能告诉我这样做的好处是什么？你为什么不关心你在开始时扩展了哪些节点？它是否有助于不一定具有良好启发式的搜索？
谢谢
对于 TLDNR 人群：
动态加权牺牲解决方案的最优性来加快搜索速度。权重越大，搜索越贪心
致各位学者：
动机
来自维基百科A星文章：
A-star的准入准则保证了一条最优解路径，但也意味着A*必须考察所有条同等有功的路径才能找到最优路径。我们可以通过放宽可接受性标准以获得近似解来以牺牲最优性为代价来加快搜索速度。很多时候我们想限制这种松弛，这样我们就可以保证解路径不差于最优解路径的 (1 + ε) 倍。这种新的保证被称为 ε-admissible。
静态权重
在讨论动态加权之前，让我们将 A-star 与最简单的 ε-可容许松弛进行比较：静态加权 A-star。
在静态加权A星中，f(n) = g(n) + w·h(n)，其中w=(1+ε)，其中ε>0。为了说明对最优性和搜索速度的影响，请比较以下各图中扩展的节点数。空心圆代表开放集中的节点；实心圆在 闭集 .
中
A 星（左）与 ε=4 的加权 A 星（右）
如您所见，加权 A-star 扩展的节点少得多，完成速度大约是原来的 3 倍。然而，由于我们使用 ε=4，加权 A-star 理论上可以 return 一个解决方案，即 (1+ε)=(1+4)=5 倍的最优路径。
动态加权
动态加权是一种使启发式权重成为搜索状态函数的技术，即 f(n) = g(n) + w(n)·h(n)，其中 w(n) = ( 1 + ε - (ε*d(n))/N)，d(n)是当前搜索的深度，N是搜索深度的上限。
通过这种方式，动态权重 A-Star 最初表现得非常像贪心最佳优先搜索，但随着搜索深度（即图中的跳数）增加，算法采用更保守的方法, 表现得更像传统的 A-star 算法。
With dynamic weighting, you assume that at the beginning of your
search, it’s more important to get (anywhere) quickly; at the end of
the search, it’s more important to get to the goal.
他是对的，但我要说的是动态加权，你假设在搜索开始时，遵循你的启发式更重要；在搜索结束时，考虑路径的长度也变得同样重要。
其他材料和链接：
- 助理。 Ira Pohl 教授 -- 回避（相对）
灾难、启发式能力、真正的动态加权和
启发式问题求解中的计算问题
- Dynamic Weighting 关于 Amit Patel 的 A*
变体
- 维基百科 -- Bounded Relaxation for the A* Search Algorithm
我在阅读 A* 搜索算法的变体时遇到了动态加权。据我了解，权重应用于搜索方程式，随着搜索越来越接近目标节点，权重会减小。我是专门看这篇文章的：http://theory.stanford.edu/~amitp/GameProgramming/Variations.html
谁能告诉我这样做的好处是什么？你为什么不关心你在开始时扩展了哪些节点？它是否有助于不一定具有良好启发式的搜索？
谢谢
对于 TLDNR 人群：
动态加权牺牲解决方案的最优性来加快搜索速度。权重越大，搜索越贪心
致各位学者：
动机
来自维基百科A星文章： A-star的准入准则保证了一条最优解路径，但也意味着A*必须考察所有条同等有功的路径才能找到最优路径。我们可以通过放宽可接受性标准以获得近似解来以牺牲最优性为代价来加快搜索速度。很多时候我们想限制这种松弛，这样我们就可以保证解路径不差于最优解路径的 (1 + ε) 倍。这种新的保证被称为 ε-admissible。
静态权重
在讨论动态加权之前，让我们将 A-star 与最简单的 ε-可容许松弛进行比较：静态加权 A-star。
在静态加权A星中，f(n) = g(n) + w·h(n)，其中w=(1+ε)，其中ε>0。为了说明对最优性和搜索速度的影响，请比较以下各图中扩展的节点数。空心圆代表开放集中的节点；实心圆在 闭集 .
中
A 星（左）与 ε=4 的加权 A 星（右）
如您所见，加权 A-star 扩展的节点少得多，完成速度大约是原来的 3 倍。然而，由于我们使用 ε=4，加权 A-star 理论上可以 return 一个解决方案，即 (1+ε)=(1+4)=5 倍的最优路径。
动态加权
动态加权是一种使启发式权重成为搜索状态函数的技术，即 f(n) = g(n) + w(n)·h(n)，其中 w(n) = ( 1 + ε - (ε*d(n))/N)，d(n)是当前搜索的深度，N是搜索深度的上限。
通过这种方式，动态权重 A-Star 最初表现得非常像贪心最佳优先搜索，但随着搜索深度（即图中的跳数）增加，算法采用更保守的方法, 表现得更像传统的 A-star 算法。
With dynamic weighting, you assume that at the beginning of your search, it’s more important to get (anywhere) quickly; at the end of the search, it’s more important to get to the goal.
他是对的，但我要说的是动态加权，你假设在搜索开始时，遵循你的启发式更重要；在搜索结束时，考虑路径的长度也变得同样重要。
其他材料和链接：
- 助理。 Ira Pohl 教授 -- 回避（相对） 灾难、启发式能力、真正的动态加权和 启发式问题求解中的计算问题
- Dynamic Weighting 关于 Amit Patel 的 A* 变体
- 维基百科 -- Bounded Relaxation for the A* Search Algorithm