几种算法的异同
2021-01-30 05:16
标签：共同点 广度优先 状态 贪心法 函数 str 实现 选择 获得 共同点： ? 将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。 不同点： ? 1）适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的；而分治法中子问题相互 独立。 ? 2）动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答 案，故可获得多项式级时间复杂度，效率较高；而分治法中对于每次出现的子问题均求解，导致同样的子 问题被反复求解，故产生指数增长的时间复杂度，效率较低。 ? 共同点： ? 都要求问题具有最优子结构 ? 不同点： ? 1）求解方式不同 ? 动态规划：自底向上 ? 贪心法：自底向下 ? 2）对子问题的依赖不同 ? 动态规划：依赖子问题的解，所以应使各子问题最优，才能保证整体最优 ? 贪心法：依赖于过去所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解 ? 相同点：都是在状态空间树上搜索问题解的算法；都是活结点表实现，都可以用约束函数剪去不含答案结点的 分枝，都可用限界函数剪去不含最优解的分枝 ? 不同点： 几种算法的异同 标签：共同点 广度优先 状态 贪心法 函数 str 实现 选择 获得 原文地址：https://www.cnblogs.com/alivinfer/p/12821669.html1. 分治法和动态规划的异同：
2. 动态规划和贪心法的异同：
3. 分枝限界法和回溯法的异同：