简答题

动态规划的基本思想是什么?

正确答案

动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。
贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择;
而分治法中的各个子问题是独立的(即不包含公共的子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。
不足之处:如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。
因此,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解。

答案解析

相似试题
  • 算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么?

    简答题查看答案

  • 动态规划算法的基本思想是将待求解问题分解成若干(),先求解(),然后从这些()的解得到原问题的解。

    填空题查看答案

  • 动态规划算法的基本要素是()和()。

    填空题查看答案

  • 动态规划算法的基本要素是()、()。

    填空题查看答案

  • 动态规划法的基本原理是()

    多选题查看答案

  • 动态规划算法的两个基本要素是()性质和()性质。

    填空题查看答案

  • 动态规划法的思想是把大问题归结为大量不同规模子问题,而子问题的求解采用一次计算并保存,以后查表的方法来解决,从而节约计算量。因此可以说,动态规划方法是以空间换时间的方法。

    判断题查看答案

  • ()是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。

    填空题查看答案

  • 简述动态规划算法的基本步骤。

    简答题查看答案