search - A*搜索动态加权的优势

Question

我在阅读 A* 搜索算法的变体时遇到了动态加权。据我了解，权重应用于搜索方程式，随着搜索越来越接近目标节点，权重会减小。我是专门看这篇文章的:http://theory.stanford.edu/~amitp/GameProgramming/Variations.html

谁能告诉我这样做的好处是什么？你为什么不关心你在开始时扩展了哪些节点？它是否有助于不一定具有良好启发式的搜索？

谢谢

Answer 1

对于 TLDNR 人群:

动态加权牺牲解决方案的最优性来加快搜索速度。权重越大，搜索越贪心。

致各位学者:

动机

来自维基百科 A-star 文章:A-star 的可采性标准保证了最优解路径，但这也意味着 A* 必须检查所有同等有值(value)的路径以找到最优路径。我们可以通过放宽可接受性标准以获得近似解来以牺牲最优性为代价来加快搜索速度。很多时候我们想限制这种松弛，这样我们就可以保证解路径不差于最优解路径的 (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)=5 倍。

动态加权

动态加权是一种使启发式权重成为搜索状态函数的技术，即 f(n) = g(n) + w(n)·h(n)，其中 w(n) = (1 + ε - (ε*d(n))/N)，d(n)为当前搜索深度，N为搜索深度上限。

通过这种方式，动态权重 A-Star 最初表现得非常像贪心最佳优先搜索，但随着搜索深度(即图中的跳数)增加，该算法采用更保守的方法，表现为更像传统的A星算法。

Amit Patel's page说

With dynamic weighting, you assume that at the beginning of yoursearch, it’s more important to get (anywhere) quickly; at the end ofthe search, it’s more important to get to the goal.

他是对的，但我要说的是，对于动态加权，您假设在搜索开始时，遵循您的启发式更为重要；在搜索结束时，考虑路径的长度也变得同样重要。

其他 Material 和链接:

1. 助理。 Ira Pohl 教授 -- The Avoidance of (Relative)Catastrophe, Heuristic Competence, Genuine DYnamic Weighting andComputational Issues in Heuristic Problem Solving
2. Dynamic Weighting关于 Amit Patel 的 A* 变体
3. 维基百科 -- Bounded Relaxation for the A* Search Algorithm