试题详情
简答题简述贪心法和动态规划法思路的异同。
  • 贪心法和动态规划法都是用于解决多阶段决策的最优化问题。基本的求解思路，都是 把一个复杂的问题分解为若干子问题，通过对子问题求解的一系列的决策或选择，最后得到原问题的解。但是，两者的决策方法不相同。贪心法总是把原问题分解为一系列较为简单的局部最优选择，每一步选择都是在当前状态下做出的最优选择，同时扩展了当前的部分解，直到求得问题的完整解。这个贪心选择过程是以自顶向下的方式进行的，即从原问题出发，每做一步贪心选择都把问题简化为规模更小的子问题，直到对规模最小的子问题做出贪心选择。动态规划法中，分解成的子问题具有两个特点。其一，子问题之间往往不是互相独立的，而是有重叠的部分，这种重叠关系通过动态规划函数表现出来，为了避免对重叠部分的重复计算，以表格形式保存每一步对子问题的求解结果，当需要再次求解已经解决的子问题时，只要做简单的查表操作即可。其二，每个子问题对应决策过程的一个阶段，每步所做的决策往往依赖于相关子问题的解，因此，只有在解决了相关的子问题之后，才能做出决策或选择。正因为此，其求解子问题时，通常以自底向上的方式进行，即从求解最后分解得到的子问题开始，逐层向前，最后求得原问题的解。

  • 关注下方微信公众号，在线模考后查看

热门试题