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