algorithm - A*(A星)寻路算法是一种什么样的算法范式/算法设计范式？

Question

我不确定A*(A星)寻路算法是一种什么样的设计范式。根据Anany Levitin的《Introduction to the Design & Analysis of Algorithms》一书的题目，我认为设计范式是一种贪心技术，因为这个算法是Dijktra算法和greedy best first这种贪心技术的结合。但我不确定这是否是一个好的推理。

编辑:根据 Emma 的评论，她给了我维基百科的链接，其中说“Dijkstra 和 A* 是动态规划的特例。A* 本身是分支定界推广的特例。” link .但在其他维基百科中link说“Dijkstra 算法和相关的 A* 搜索算法是可验证的图搜索和最短路径查找的最佳贪婪算法。”

Answer 1

你的问题问得好!

Greedy is setteld!!!

我想这要视情况而定，我同意 "that's a bit of apples and oranges."在问题的评论中。

您的特定问题的答案可能是 here或 here .

被认为是Greedy或 Dynamic Programming (DP) ，根据一些维基百科页面。

然而，templatetypedef评论中也有一个很好的观点:“我会把它标记为 greedy，因为它在每个点都做出局部最优决策。”

---

贪心

Dijkstra's algorithm and the related A* search algorithm areverifiably optimal greedy algorithms for graph search and shortestpath finding.

---

动态编程

What sets A* apart from a greedy best-first search algorithm is thatit takes the cost/distance already traveled, g(n), into account.

Some common variants of Dijkstra's algorithm can be viewed as aspecial case of A* where the heuristic h(n) = 0 for all nodes; inturn, both Dijkstra and A* are special cases of dynamic programming.A* itself is a special case of a generalization of branch and bound.

引用

• A* search algorithm

• Algorithmic paradigm