Dijkstra算法属于贪心算法还是动态规划？
·
Dijkstra算法属于贪心算法，以下根据个人理解进行分析，如有理解不当之处，还请不吝赐教！
使用动态规划有两个必要条件：
- 最优子结构：整体的最优解对应着每个子问题的最优解
- 无后效性：已经求解的子问题不受后续决策影响
另外，通过将子问题的解储存起来供后续求解使用，可以大大提高运行效率。
再看Dijkstra算法，假设我们要求解节点s到x的最短路径。如果以每一步寻找源节点最近节点为子问题，则不满足无后效性。可参考上图第二行前两张图，在前一个子问题我们找到z节点是距离s的最近节点，按照动态规划的逻辑，我们可以在此子问题最优解的基础上找到到节点x的最短路径。然而下一问题的解则抛弃了z节点转向了t节点，最后证明s->y->t->x才是最短路径。
假如我们改成以求解最短路径末尾的上一节点为子问题，则面临根本无法求解子问题的情况，因为我们无法预先知道哪个节点距离源节点s是最近的。
综上，迪杰克斯特拉算法属于贪心算法而非动态规划算法。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
2
0- 0
已为社区贡献2条内容
所有评论(0)