我不清楚A*（A星）寻路算法是一种什么样的设计范式。根据Anany Levitin所著的《算法设计&分析导论》一书的题目，我认为设计范式是一种贪婪的技术，因为这个算法是Dijktra的算法和贪婪的最佳优先的结合，这两种技术都是贪婪的技术。但我不知道这是不是一个好的推理。
编辑：根据Emma的评论，她给了我一个维基百科的链接，其中说" Dijkstra和A*是动态编程的特例。A*本身就是分支和约束的泛化的一个特例。" 链接.但在另一个维基百科上 联系 说："Dijkstra算法和相关的A*搜索算法是图搜索和最短路径寻找的可验证的最优贪婪算法。"
你的问题很好!
我想这要看情况，我同意 "这有点像苹果和橘子" 在问题的评论中。
它被认为是 贪婪 或 动态规划(DP)根据一些维基百科的页面。
然而， templatetypedef 评论中也有很好的观点。"我认为它是 贪婪 鉴于它在每个点上都在做一个局部最优的决策。"
Dijkstra算法和相关的A*搜索算法是用于图搜索和最短路径寻找的可验证的最优贪婪算法。
A*与贪婪的best-first搜索算法不同的是，它考虑到了已经走过的成本距离，g(n)。
一些常见的Dijkstra算法的变体可以被看作是A*的特殊情况，其中所有节点的启发式h(n)=0；因此，Dijkstra和A*都是动态编程的特殊情况，A*本身就是分支和边界的一般化的特殊情况。
我认为A*的主要范式是穷尽式搜索（或称分支和约束（b&b），很多人认为穷尽式搜索和b&b是两种不同的范式，但我认为b&b只是实现和改进穷尽式搜索的一种技术），和其他穷尽式搜索一样，A*会探索整个解空间（排除确定为比最优解更差的解）。Greedy只是一种额外的技术，用来引导搜索向最有希望的方向发展。
这不是贪婪。
根据维基百科，一个 贪婪算法 "是任何遵循在每个阶段做出局部最优选择的解决问题的启发式算法"，这并不适用于A*（IMHO在该维基百科页面的例子部分列出A*是个错误）。
为什么这么说呢？
我对上述定义的理解是，"在每个阶段做出局部最优选择 "意味着我们不考虑该状态下可能的其他选择--在贪婪策略中，我们从不重新考虑之前做出的选择。
而对于A*来说并不是这样，A*最终会探索在任何阶段做出的所有选择，如果之前在该阶段做出的选择看起来不再 "最有前途"。A*确实会从局部最优选择开始进行穷尽性探索。
我的论证是基于定义中的 "阶段 "和 "选择 "这两个词与A*算法中的 "图节点 "和 "图边缘 "的直接、直观的映射。但如果你想把 "阶段 "映射到 "所探索的子图"，那么A*的确有资格成为贪婪的--但有了这样一个非直观的映射，即使是breadth-first也变得贪婪了。