A*（A星）寻路算法是一种什么样的算法paradigm/algorithm设计范式？
What kind of algorithm paradigm/algorithm design paradigm is A* (A star) pathfinding algorithm?
我不太清楚A*（A星）寻路算法是一种什么样的设计范式。根据Anany Levitin的书"Introduction to the Design & Analysis of Algorithms"的题目，我认为设计范式是一种贪心技术，因为这个算法是Dijktra算法和greedy best first这两种贪心技术的结合。但我不确定这是否是一个好的推理。
编辑：根据 Emma 的评论，她给了我维基百科的 link，其中说“Dijkstra 和 A* 是动态规划的特例。A* 本身是分支和泛化的特例边界。” link。
但是在另一个维基百科中 link 说 "Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms for graph search and shortest path finding."
你问得好！
贪心已定！！！
我想这要视情况而定，我同意问题评论中的 "that's a bit of apples and oranges."。
根据某些维基百科页面，它被认为是 Greedy or Dynamic Programming (DP)。
但是，templatetypedef also has a good point in the comment: "I would have pegged it as greedy 考虑到它在每个点都做出局部最优决策。"
贪婪
Dijkstra's algorithm and the related A* search algorithm are
verifiably optimal greedy algorithms for graph search and shortest
path finding.
动态规划
What sets A* apart from a greedy best-first search algorithm is that
it takes the cost/distance already traveled, g(n), into account.
Some common variants of Dijkstra's algorithm can be viewed as a
special case of A* where the heuristic h(n) = 0 for all nodes; in
turn, both Dijkstra and A* are special cases of dynamic programming.
A* itself is a special case of a generalization of branch and bound.
参考
我认为A*的主要范式是穷举搜索（或分支定界（b&b），很多人认为穷举搜索和b&b是两种不同的范式，但我认为b&b只是一种实现和改进穷举的技术search)，像其他穷举搜索一样，A* 会探索整个解决方案space（排除确定的比最优解更差的解决方案）。贪婪只是一种附加技术，用于在最有希望的方向上导航搜索。
不贪心
根据维基百科，greedy algorithm "is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage"，这不适用于 A*（恕我直言，在该维基百科页面的示例部分列出 A* 是错误的）。
为什么？
我对上述定义的理解是，"making the locally optimal choice at each stage" 意味着我们忽略了该状态下可能的其他选择——在贪婪策略中，我们从不重新考虑之前做出的选择。
而对于 A* 则不然，A* 最终会探索在任何阶段做出的所有选择，如果该阶段的先前选择不再看起来 "most promising"。确实，A* 将以局部最优选择开始其详尽的探索。
我的论证基于直接、直观的映射，即定义中的单词 "stage" 和 "choice" 映射到 A* 算法中的 "graph node" 和 "graph edge" .但是，如果你想将 "stage" 映射到 "subgraph explored"，那么 A* 确实符合贪婪的条件——但使用这种非直观的映射，即使广度优先也会变得贪婪。
我不太清楚A*（A星）寻路算法是一种什么样的设计范式。根据Anany Levitin的书"Introduction to the Design & Analysis of Algorithms"的题目，我认为设计范式是一种贪心技术，因为这个算法是Dijktra算法和greedy best first这两种贪心技术的结合。但我不确定这是否是一个好的推理。
编辑：根据 Emma 的评论，她给了我维基百科的 link，其中说“Dijkstra 和 A* 是动态规划的特例。A* 本身是分支和泛化的特例边界。” link。 但是在另一个维基百科中 link 说 "Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms for graph search and shortest path finding."
你问得好！
贪心已定！！！
我想这要视情况而定，我同意问题评论中的 "that's a bit of apples and oranges."。
根据某些维基百科页面，它被认为是 Greedy or Dynamic Programming (DP)。
但是，templatetypedef also has a good point in the comment: "I would have pegged it as greedy 考虑到它在每个点都做出局部最优决策。"
贪婪
Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms for graph search and shortest path finding.
动态规划
What sets A* apart from a greedy best-first search algorithm is that it takes the cost/distance already traveled, g(n), into account.
Some common variants of Dijkstra's algorithm can be viewed as a special case of A* where the heuristic h(n) = 0 for all nodes; in turn, both Dijkstra and A* are special cases of dynamic programming. A* itself is a special case of a generalization of branch and bound.
参考
我认为A*的主要范式是穷举搜索（或分支定界（b&b），很多人认为穷举搜索和b&b是两种不同的范式，但我认为b&b只是一种实现和改进穷举的技术search)，像其他穷举搜索一样，A* 会探索整个解决方案space（排除确定的比最优解更差的解决方案）。贪婪只是一种附加技术，用于在最有希望的方向上导航搜索。
不贪心
根据维基百科，greedy algorithm "is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage"，这不适用于 A*（恕我直言，在该维基百科页面的示例部分列出 A* 是错误的）。
为什么？
我对上述定义的理解是，"making the locally optimal choice at each stage" 意味着我们忽略了该状态下可能的其他选择——在贪婪策略中，我们从不重新考虑之前做出的选择。
而对于 A* 则不然，A* 最终会探索在任何阶段做出的所有选择，如果该阶段的先前选择不再看起来 "most promising"。确实，A* 将以局部最优选择开始其详尽的探索。
我的论证基于直接、直观的映射，即定义中的单词 "stage" 和 "choice" 映射到 A* 算法中的 "graph node" 和 "graph edge" .但是，如果你想将 "stage" 映射到 "subgraph explored"，那么 A* 确实符合贪婪的条件——但使用这种非直观的映射，即使广度优先也会变得贪婪。