文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 动态规划基础
侵权投诉

动态规划基础

算法 动态规划

动态规划

(一)、动态规划的基本思想:

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

二、设计动态规划法的步骤:

1、找出最优解的性质,并刻画其结构特征;

2、递归地定义最优值(写出动态规划方程);

3、以自底向上的方式计算出最优值;

4、根据计算最优值时得到的信息,构造一个最优解。

步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤4可以省略,步骤3中记录的信息也较少;若需要求出问题的一个最优解,则必须执行步骤4,步骤3中记录的信息必须足够多以便构造最优解。

三、动态规划问题的特征:

动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构性质和子问题重叠性质。

1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。

2、重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

(二)、动态规划算法的基本步骤

设计一个标准的动态规划算法,通常可按以下几个步骤进行:

第1页

你可能喜欢

  • 动态规划算法
  • 动态规划经典
  • 运筹学动态规划
  • 矩阵连乘动态规划
  • matlab动态规划
  • C语言动态规划
  • 动态规划问题
  • 动态规划的优化

热门文档

相关文档

  • 动态规划基础

    动态规划基础_数学_自然科学_专业资料 暂无评价0人阅读0次下载举报文档 动态规划基础_数学_自然科学_专业资料。今日推荐 180份文档 ...

  • 动态规划基础

    ACM动态规划基 础计071 贾双帅 QQ:214564749 动态规划基础什么是动态规划? ? 动态规划有什么特点? ? 如何动态规划?讲具体问题 ? 动态规划学习进度 ? 简单练习...

  • 动态规划基础和建模

    动态规划基础和建模山东省潍坊第一中学 秦政 clavichord 前言 ? 动态规划是统筹学的重要内容 ? 动态规划是OI的重要内容 ? 据不完全统计,每次考试动态规划起码有一...

  • 动态规划基础

    动态规划基础动态规划基础隐藏>> 动态规划动态规划-DP 内容: 内容: 引例 动态规划的概念与原理 例题分析 一、引例【引例1、上楼梯】 引例1 上楼梯】一个...

  • 动态规划基础

    动态规划基础 动规动规隐藏>> 动态规划的重要性:涉及动态规划的各种竞赛题越来越多,每一年的NOI几 乎都至少有一道题目需要用动态规划的方法来解决 。 什么是...

  • 动态规划 基础版 pascal 详解

    动态规划 基础版 pascal 详解_城乡/园林规划_工程科技_专业资料。里面有很多例题 标程和详解 基础版Dynamic Programming 动态规划动态规划问题的数学描述 首先,例举...

  • 动态规划基础、进阶与优化

    动态规划基础、进阶与优化 隐藏>> 山东师大附中 陈键飞 前言 ? 自古以来就是NOIP的重要考察内容,在联赛中占的分 量大。 ? 对选手能力有一定要求,需要能够熟练...

  • 动态规划基础讲解及经典案例分析解答

    动态规划基础讲解及经典案例分析解答_理学_高等教育_教育专区。综合实践考核第九课 动态规划(I) 动态规划( ) 2012-4-26 1 数字三角形 1、问题描述 、 上图...

  • 动态规划基础讲稿

    动态规划算法正是利用了这种子问题的重叠性质,对每一个 子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多 地利用这些子问题的解。 3)、无后效性...

  • 动态规划阶段总结之基础篇[必看]

    动态规划阶段总结之基础篇 by Zc [序言] 动态规划是信息学竞赛中最重要的知识点之一, 不仅思维难度高, 而且变化多端, 新思想新方法层出不穷, 要求选手具有很...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email