请选择时期:
怀孕准备 怀孕 分娩 宝宝0-1岁 宝宝1-3岁 宝宝3-6岁

动态规划的基本要素(动态规划四要素)

来源: 最后更新:22-07-07 02:37:28

导读:动态规划的基本要素,1、最优子结构。当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。2、重叠子问题。可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。

动态规划的基本要素如下:

  

  1、最优子结构。当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。在动态规划算法中,利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

  

  2、重叠子问题。可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要此子问题时,只要简单地用常数时间查看一下结果。通常,不同的子问题个数随问题的大小呈多项式增长。因此,用动态规划算法通常只需要多项式时间,从而获得较高的解题效率。

  

  

标签: 基本要素  标签  简介  动态  

免责声明:本文系转载,版权归原作者所有;旨在传递信息,其原创性以及文中陈述文字和内容未经本站证实。

本文地址:http://www.bbbaike.com/baike/zonghe/372882.html

声明: 本站文章均来自互联网,不代表本站观点 如有异议 请与本站联系 联系邮箱:kefu#bbbaike.com (请把#替换成@)

关于我们 | 广告服务 | 网站合作 | 免责声明 | 联系我们| 网站地图

© 2022-2024 宝宝百科网 all rights reserved. 沪ICP备2023005727号-4