我不确定A *（星形）寻路算法是哪种设计范例。根据Anany Levitin所著的“算法设计与分析简介”一书的主题，我认为设计范例是一种贪婪的技术，因为该算法是Dijktra算法和贪婪最好的贪婪最佳算法的结合。但是我不确定这是否是一个很好的理由。
编辑：根据Emma的评论，她给我提供了Wikipedia的链接，其中说：“ Dijkstra和A *是动态编程的特例。A*本身是分支和绑定的一般化的特例。” link。但是在另一本维基百科中，link说“ Dijkstra算法和相关的A *搜索算法是可验证的最优贪婪算法，用于图搜索和最短路径查找。”
您有一个很好的问题！
我想这将取决于我，并且我同意问题注释中的"that's a bit of apples and oranges."。
根据某些维基百科页面，它被认为是Greedy或Dynamic Programming (DP)。
但是，templatetypedef在评论中也有一个要点：“鉴于它在每个点上都做出了局部最优的决定，我将其与greedy挂钩。”
Dijkstra的算法和相关的A *搜索算法是用于图搜索和最短的可验证最优贪婪算法寻路。
将A *与贪婪的最佳第一搜索算法区分开的原因是它考虑了已经旅行的成本/距离g（n）。
Dijkstra算法的一些常见变体可以看作是A *的特殊情况，其中所有节点的启发式h（n）= 0；在反过来，Dijkstra和A *都是动态编程的特例。A *本身是branch and bound泛化的特例。
[我认为A *的主要范式是穷举搜索（或分支定界（b＆b），许多人认为穷举搜索和b＆b是两种不同的范式，但我认为b＆b只是一种实现和改进穷举搜索的技术），与其他穷举搜索一样，A *将探索整个解决方案空间（排除确定的解决方案比最优解决方案更糟）。贪婪只是一种附加技术，用于在最有希望的方向上导航搜索。
根据Wikipedia，greedy algorithm“是遵循在每个阶段做出局部最优选择的问题解决启发式方法的任何算法，并且不适用于A *（恕我直言，在其中列出A *是错误的Wikipedia页面的“示例”部分）。
为什么？
我对上述定义的理解是，“在每个阶段做出局部最优选择”意味着我们无视该状态下的其他选择-在贪婪的策略中，我们从不重新考虑先前做出的选择。
并且对于A *而言并非如此，如果该阶段的先前选择看起来不再“最有希望”，那么A *最终将探索在任何阶段做出的所有选择。的确，A *将以局部最优选择开始其详尽的探索。
我的论证基于直接，直观的映射，即从定义中的单词“ stage”和“ choice”映射到A *算法中的“ graph node”和“ graph edge”。但是，如果您要将“阶段”映射到“探索的子图”，则A *确实符合贪婪的条件-但是通过这种非直观的映射，即使广度优先也变得贪婪。