2. 计算机
  3. 关于动态规划的描述，不正确的是( )。

关于动态规划的描述，不正确的是( )。

admin2019-08-25  24
问题 关于动态规划的描述，不正确的是(        )。
选项 A、动态规划是解决多阶段决策过程最优化解的一种常用算法思想
B、动态规划的实质是分治思想和解决冗余，与分治法和溯回法类似
C、在处理离散型问题时，动态规划比线性规划效果更好
D、一个标准的动态规划算法包括划分阶段和选择状态两个步骤
答案B
解析 动态规划：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
    基本思想：若要解一个给定问题，需要解其不同部分(即子问题)，再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
    分治与动态规划：
    共同点：二者都要求原问题具有最优子结构性质，都是将原问题分而治之，分解成若干个规模较小(小到很容易解决的程序)的子问题。然后将子问题的解合并，形成原问题的解。
    不同点：分治法将分解后的子问题看成相互独立的，通过用递归来做。动态规划将分解后的子问题理解为相互间有联系，有重叠部分，需要记忆，通常用迭代来做。
    问题特征：
    最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
    重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。
转载请注明原文地址:https://kaotiyun.com/show/dIUZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

信息系统项目管理师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)