动态规划法与分治法的区别 共同点： 将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的 解得到原问题的解。 不同点： 1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是 相互独立的； 而分治法中子问题相互独立。 2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问 题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较 高； 而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复 求解，故产生指数增长的时间复杂度，效率较低。 动态规划法与贪心法的区别 共同点： 都要求问题具有最优子结构性质。 不同点： 1、求解方式不同： 动态规划法：自底向上； 贪心法：自顶向下； 2、对子问题的依赖不同： 动态规划法：依赖于各子问题的解，所以应使各子问题最优，才能保 证整体最优； 贪心法：依赖于过去所作过的选择，但决不依赖于将来的选择，也不 依赖于子问题的解。 分枝限界法与回溯法的异同 分枝限界法与回溯法的共同点 都是在问题的状态空间树上搜索问题解的算法。 都用活结点表实现, 都可用约束函数剪去不含答案结点的分枝, 都可用 限界函数剪去不含最优解的分枝。 分枝限界法与回溯法的不同点 求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所 有可行解；而分支限界法的求解目标则是找出满足约束条件的一个可行 解，或某种意义下的最优解。 搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分枝限界法 则以广度优先或最小耗费优先的方式搜索解空间树。 对当前扩展结点的扩展方式不同：回溯法中的每个活结点可能多次成为 当前扩展结点，纵深方向扩其一个孩子，然后再回溯后扩展其他孩子； 而分支限界法中每一个活结点只有一次机会成为扩展结点，一次产生所 有孩子结点，自身成为死结点，之后无需再返回该结点处。