A*（A星）寻路算法属于什么样的算法范式/算法设计范式？

Question

我不确定A*寻路算法是哪种设计范例。根据Anany Levitin所著《算法设计与分析入门》一书的主题，我认为设计范例是贪心技术，因为该算法是Dijkstra算法和贪心最佳优先级的组合，而这些都是贪心技术。但我不确定这是否是一个好的推理。

编辑：根据Emma的评论，她给了我一个维基百科链接，其中写道“ Dijkstra和A*是动态规划的特殊案例。 A*本身是分支限界方法的一种特殊情况。”链接。但在另一个维基百科链接中则说：“Dijkstra算法和相关的A*搜索算法是用于图搜索和最短路径查找的可验证最优贪心算法。”

- Juliorogerscg

---

@ggorlen 其实这有点不可比较。A*算法确实不是贪心算法。而且在一般领域中，朴素的爬山算法并不是最优解。但是存在一些问题，贪心算法是最优解的。这个类被称为拟阵。拟阵的一个例子是最小生成树问题。凸域上的最大搜索是另一个例子。 - Gene

@ggorlen 感谢您的欢迎。在寻找“什么是设计范式？”的答案时，我发现了这个[链接]（https://en.wikipedia.org/wiki/Algorithmic_paradigm#:~:text=An%20algorithmic%20paradigm%20or%20algorithm,higher%20than%20a%20computer%20program.），我认为它解释得很好。而且，由于那个页面，我在这个[页面]（https://en.wikipedia.org/wiki/Greedy_algorithm#Examples）中找到了一种答案。但我不确定，因为在其他维基百科链接中（例如@Emma的答案），有另一个答案。 - Juliorogerscg

是的，我现在明白了。我听说过“算法范式”，但我没听说过“设计范式”，这听起来更像软件工程。请忽略我的原始回答。我现在相信A*可以被认为是贪心算法，或者至少表现出了它的特征，尽管我觉得这是一种有点不直观的分类方式。这是一个教育性的讨论。 - ggorlen

Answer 1

你的问题很好！

贪心算法已解决！！！

我猜这可能取决于问题评论中"那有点类似苹果和橘子"的说法，我同意。

关于您具体问题的答案可能在这里或这里。

根据一些维基百科页面，它被认为是贪心算法或动态规划（DP）。

然而，templatetypedef 在评论中也提出了一个好观点："考虑到每个点都做出了局部最优决策，我会将其归为贪心算法"。

---

贪心算法

Dijkstra算法和相关的A*搜索算法是用于图搜索和最短路径查找的可验证最优贪心算法。

---

动态规划

把已经走过的距离 g(n) 考虑进去，这就是A*算法和贪婪最佳优先搜索算法的区别。

一些Dijkstra算法的常见变体可以看作是A*的特例，其中所有节点的启发式函数 h(n) = 0；而 Dijkstra和 A*都是动态规划的特例。A*本身是分支限界法的一种特殊情况。

参考资料

• A*搜索算法

• 算法范型

- Emma

---

哦，我本来会认为它是贪心的，因为它在每个点上都做出了局部最优的决策。 - templatetypedef

谢谢！但是现在我找到了另一个维基百科链接，其中说它是贪心技巧的一个例子链接。 - Juliorogerscg

Answer 2

我认为A*算法的主要范式是穷举搜索(或者分支定界(b&b)，许多人认为穷举搜索和b&b是两种不同的范式，但我认为b&b只是一种实现和改进穷举搜索的技术)，像其他穷举搜索一样，A*将探索整个解空间(排除比最优解差的解)。贪婪法只是一种额外的技术，用于在最有前途的方向上导航搜索。

- dangxuanvuong98

Answer 3

这不是贪心算法。

根据维基百科，贪心算法“是指在对问题进行求解时，在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法”。但这种算法不适用于A*算法（在我看来，在那个维基百科页面的示例部分列出A*是错误的）。

为什么？

我理解上述定义的含义是，“在每个阶段做出本地最优选择”意味着我们忽略了该状态下可能存在的其他选择 - 在贪心策略中，我们永远不会重新考虑之前做出的选择。

但对于A*算法来说并非如此。如果先前在该阶段做出的选择不再看起来“最有前途”，A*将最终探索所有已做出的选择。当然，A*将从本地最优选择开始其详尽的探索。

我的论证基于直观的映射，即定义中的“阶段”和“选择”映射到A*算法中的“图节点”和“图边”。但是，如果您想将“阶段”映射到“子图探索”，那么A*确实符合贪心算法的条件 - 但是对于这种非直观的映射，即使广度优先搜索也会变得贪心。

- Ralf Kleberhoff