我不确定A*(A星)寻路算法是一种什么样的设计范式。根据Anany Levitin的《Introduction to the Design & Analysis of Algorithms》一书的题目,我认为设计范式是一种贪心技术,因为这个算法是Dijktra算法和greedy best first这种贪心技术的结合。但我不确定这是否是一个好的推理。
编辑:根据 Emma 的评论,她给了我维基百科的链接,其中说“Dijkstra 和 A* 是动态规划的特例。A* 本身是分支定界推广的特例。” link . 但在其他维基百科中link说“Dijkstra 算法和相关的 A* 搜索算法是可验证的图搜索和最短路径查找的最佳贪婪算法。”
最佳答案
你的问题问得好!
Greedy is setteld!!!
我想这要视情况而定,我同意 "that's a bit of apples and oranges."在问题的评论中。
被认为是Greedy或 Dynamic Programming (DP) ,根据一些维基百科页面。
然而,templatetypedef评论中也有一个很好的观点:“我会把它标记为 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.
引用
关于algorithm - A*(A星)寻路算法是一种什么样的算法范式/算法设计范式?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62164040/