《动态规划算法.doc》由会员分享，可在线阅读，更多相关《动态规划算法.doc（17页珍藏版）》请在金锄头文库上搜索。
1、站内导航: 程序设计 o 数据结构与算法 o Java o 游戏开发 开源动态 o 软件发布信息 o 国际新闻 o 国内新闻 开源软件 o 文本编辑 o 桌面与多媒体 o 网络软件 o 数据库 o 应用服务器 操作系统 开源文章 网络协议与安全 开源专题导航 o Linux OS o BSD 操作系统 o 嵌入式开发 o 网站开发 o 开源人物志 o 图书推荐 Google 相关主题推荐 站内排行前50热点文章 GDB调试精粹及使用实例 STL中map用法详解 负载均衡软件比较(Hapr. 头文件的重复引用 递归函数的调用过程 TCP三次握手/四次挥手详解 贪心策略的理论基础. BMH算法原理
2、与实现（模. 排列组合与回溯算法 DP动态规划 Android线程模型 Linux socket编程之套接字 Linux内核中的红黑树 linux下使用minicom的几. Java开源Html解析类库 enum类型的本质 memcached server LRU . linux设置环境变量的方法 android核心模块及相关. linux源代码包（.tar.g. L.A.M.P配置过程 在ubuntu9.10下安装QT4. C/C+程序员常见面试题. gcc编译过程概述 python的memcache和jso. 应用程序二进制接口-ABI linux内核编译问题 Java多线程实现简单实例
3、Python程序员常用的IDE. brk和sbrk详述 优化C语言代码(程序员必. python非贪婪,多行匹配. 函数指针传递和全局指针. Unix操作系统的历史演变 网络编程之C10K问题 发行版发布：CentOS 5.4 在windows中构建gtk开发. i+循环与i-循环的执行. 关于Qvariant类-万能的. Debian sudo 设置 busybox1.15.x 交叉编译 关于僵死进程zombie 递归思想的妙用 判断链表是否存在环并找. Android Porting Exper. 关于/etc/bashrc和$HOM. 翻译Django初窥 Python list的排序
4、Django实现大数据量分页. Debug方式取代printf满. 中国源码网:开放源代码 & 编程 注册会员 会员登录 设为首页 加入收藏 代码工厂下载手机编程 论坛English编程手册 窗体顶端输入您的搜索字词 提交搜索表单 Webyuanma.org窗体底端当前位置: 首页 程序设计 数据结构和算法 算法动态规划法LDAP介绍 vfork,fork,exec函数的区别 算法动态规划法作者： 来源：zz 发表时间：2007-05-09 浏览次数： 13740 字号：大中小中国源码网内相关主题链接 整数的质因数分解算法 动态规划:背包问题 DP动态规划 BMH算法原理与实现（模式匹配） 排
5、列组合与回溯算法 A*高效搜索算法 Rainbow Table破解算法 数据交换的特殊算法-经典面试题 算法动态规划法 运用之妙，存乎一心一、引言 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957
6、年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划法的定义：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经
7、过筛选，以每一步都是最优解来保证全局是最优解，这种求解方法称为动态规划法。动态规划是所有算法设计方法中难度最大的一种。二、动态规划的基本思想一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出
8、的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程
9、中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。一般来说，适合于用动态规划法求解的问题具有以下特点：1、可以划分成若干个阶段，问题的求解过程就是对若干个阶段的一系列决策过
10、程。2、每个阶段有若干个可能状态3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。4、在任一个阶段，最佳的决策序列和该阶段以前的决策无关。5、各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递推关系（即动态转移方程）。动态规划法所处理的问题是一个多阶段最优化决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线。在学习动态规划法之前，我们先来了解动态规划的几个概念1、 阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。2、 状态：某一阶段的出发位置称为状态。3、 决策：从某
11、阶段的一个状态演变到下一个阶段某状态的选择。4、 状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。动态规划算法的基本步骤设计一个标准的动态规划算法，通常可按以下几个步骤进行：划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决
12、策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：标准动态规划的基本框架1. 对fn+1(xn+1)初始化; 边界条件2.
13、 for k:=n downto 1 do 3. for 每一个xkXk do4. for 每一个ukUk(xk) do begin5. fk(xk):=一个极值; 或6. xk+1:=Tk(xk,uk); 状态转移方程7. t:=(fk+1(xk+1),vk(xk,uk); 基本方程(9)式8. if t比fk(xk)更优 then fk(xk):=t; 计算fk(xk)的最优值 end; 9. t:=一个极值; 或10. for 每一个x1X1 do11. if f1(x1)比t更优 then t:=f1(x1); 按照10式求出最优指标12. 输出t;但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：分析最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 根据计算最优值时得到的信息，构造一个最优解。 步骤(1)-(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题
