递归算法、动态规划、0-1背包问题的总结

2017/06/02

递归算法

问题:通过分析和运行二叉树遍历的递归和非递归算法,体会和总结递归算法的主要内容。

解答:

递归模型的组成

一个递归模型是由“递归边界”和“递归体”两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。

递归求解的原理

把一个不能或者不好直接求解的“大问题”转化为一个或者几个“小问题”来解决;再把“小问题”进一步分解为更小的“小问题”来解决;如此分解,直到“小问题”可以直接求解,再逐一求值回归,最后到达递归的开始处。

递归的实现步骤

1) 执行到递归方法时保存现场

2) 传递递归调用参数

3) 执行递归代码段,并保存现场继续执行子方法

4) 递归返回时先回收局部变量,再恢复递归前现场

5) 逐层返回至递归开始处

递归算法求解问题的一般步骤

1) 分析问题、寻找递归关系

2) 找出停止条件,即递归出口

3) 设计递归算法、确定参数,即构建递归体

动态规划

问题:贪心法和动态规划法都是解决组合优化问题的有效策略,请根据所学知识分析总结二者的不同。

解答:

贪心算法和动态规划的不同点

贪心算法:依赖于当前已经做出的所有选择,采用自顶向下的解决方法。能够使用贪心算法来求近似最优解的问题需要具有两大性质:①最优子结构性质 ②贪心选择性质

贪心算法的应用: 单源最短路径问题、最小生成树、会场安排问题、数据压缩–哈夫曼编码等

动态规划:动态规划实质是分治思想和解决冗余。将原问题分解为多个子问题,通过计算出子问题的结果构造一个最优解。动态规划通过迭代法自底向上求解,动态规划将分解后的子问题理解为相互间有联系、有重叠的部分。能够使用动态规划来求最优解的问题需要具有三大性质:①最优子结构性质 ②重叠子问题性质 ③自底向上的求解方法

动态规划的应用: 最长公共子序列、最优二叉查找树、加工顺序问题、矩阵乘法等

简单总结

  • 求解策略不同:贪心算法采用自顶向下逐步逼近的方式,只考虑最近一步的最优解;动态规划采用的是自底向上合并子问题求解方式,并且子问题是不独立的(分治法没有解决冗余,子问题是相互独立的)。

  • 求得结果不同:贪心算法求得的是近似最优解;动态规划能够求得最优解。

0-1背包问题

问题:什么是0-1背包问题,0-1背包问题有哪些解决策略,对这些解决策略进行详细的比较和分析。

解答:

什么是0-1背包问题

给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内如何选择装入的物品使得总价格最高。

解决策略

1) 穷举法

2) 贪心法(要注意得到不一定是最优解!)

3) 动态规划法

4) 回溯法

5) 分支限界法

各个策略的求解思路

穷举法:用穷举法解决0-1背包问题,需要考虑给定n个物品集合的所有子集,然后找出所有总重量不超过背包重量的子集,计算每个子集的总重量,然后在他们中找到价值最大的子集。

贪心法:用贪心算法求解0-1背包问题,首先计算每种物品单位重量的价值;然后依照贪心选择策略,选择单位重量价值最高的物品依次装入背包,直到背包装不下物品剩余任意一物品位置。

动态规划:用动态规划求解0-1背包问题,关键是构造用于储存子问题的二维数组(或者用表的形式来展示)。求解n件物品放入W容量大小的问题,可以分解为求前n-1件物品放入容量为W-wn容量的背包时背包重量的最大值和放入第n件物品时背包重量之和。由于子问题无法求解,还能够继续分解,所以问题的实际求解过程是分析的逆过程:放入第一个物品的背包重量->放入前两个物品背包最大重量->放入前三个物品背包最大重量-> …->放入前n-1个物品->放入n个物品背包最大重量。

回溯法:使用回溯法求解0-1背包问题,首先定义问题的解空间为一颗深度等于物品数目n的子集树。然后从根节点开始,以深度优先的方式开始搜索,判断物品能够装入背包则进入左结点,否则将左结点剪枝进入右结点,在搜索的过程中同时利用限界函数进行剪枝,直达搜索结束即可得到最优解。

分支限界法:使用分支限界法求解0-1背包问题与回溯法类似,首先也要定义问题的解空间树,但是搜索的方法则采用广度优先搜索的方式搜索解空间树,在搜索的过程中同时利用限界函数进行剪枝,直达搜索结束即可得到最优解。

5种求解0-1背包策略的比较

算法 时间复杂度 优点 缺点
穷举法 O(2n) 对于n比较小,穷举方法简单易懂 当n比较大时,时间复杂度以指数增长,求解速度慢
贪心法 O(n) 可以达到局部最优解,用时少 往往得不到最优解,得到的是近似最优解
动态规划 O(min{nW,2n}) 可求得最优决策序列 速度较慢
回溯法 O(n2n) 相对于分支限界法思路更加容易理解 时间复杂度较高
分支限界法 O(2n) 速度较快,易求解 占用的内存较大,效率不高

Post Directory