动态规划算法综述

科技・探索・争鸣　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ　Ｖｉｓｉｏｎ　科技视界　动态规划算法综述　张莹　（天津师范大学计算机与信息工程学院，中国天津３００３８７）　

【摘要】本文通过系统的介绍动态规划算法的基本概念、基本思想、适用情况分析、基础求解步骤、实现的说明和算法的基本框架，对动态　规划算法进行了总结和概述。　【关键词】算法；动态规划；最长公共予序列　

１　动态规划基本概念　在现实生活中，有一类活动的过程，由于它的特殊性．可将过程分　成若干个互相联系的阶段，在它的每一阶段都需要做出决策．从而使　整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确　定。它依赖于当前面临的状态，叉影响以后的发展。当各个阶段决策确　定后．就组成一个决策序列　因而也就确定了整个过程的一条活动路　线　这种把一个问题看作是一个前后关联具有链状结构的多阶段过程　就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。这种　多阶段最优化决策解决问题的过程就称为动态规划　

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

几个步骤：初始状态—决策ｌ一决策２……—一决策ｎ一结束状态。　４．１划分阶段　按照问题的时间或空间特征．把问题分为若干个阶段。在划分阶　段时．注意划分后的阶段一定要是有序的或者是可排序的．否则问题　就无法求解　４．２确定状态和状态变量　将问题发展到各个阶段时所处于的各种客观情况用不同的状态　表示出来。当然，状态的选择要满足无后效性。　４．３确定决策并写出状态转移方程　因为决策和状态转移有着天然的联系．状态转移就是根据上一阶　段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转　移方程也就可写出　但事实上常常是反过来做．根据相邻两个阶段的　状态之间的关系来确定决策方法和状态转移方程。　４．４寻找边界条件　给出的状态转移方程是一个递推式，需要一个递推的终止条件或　边界条件　

一般．只要解决问题的阶段、状态和状态转移决策确定了，就可以　写出状态转移方程（包括边界条件）　实际应用中可以按以下几个简化　的步骤进行设计：　（１）分析最优解的性质，并刻画其结构特征。　（２）递归的定义最优解。　（３）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优　值。　（４）根据计算最优值时得到的信息，构造问题的最优解。　

３动态规划适用的情况　５动态规划实现的说明　任何思想方法都有一定的局限性．超出了特定条件．它就失去了　作用。同样．动态规划也并不是万能的。适用动态规划的问题必须满足　以下三点：　３．１最优化原理（最优子结构性质）　

一个最优化策略具有这样的性质．不论过去状态和决策如何。对　前面的决策所形成的状态而言．余下的诸决策必须构成最优策略。简　而言之．一个最优化策略的子策略总是最优的。一个问题满足最优化　原理又称其具有最优子结构性质　３．２无后向性　将各阶段按照一定的次序排列好之后．对于某个给定的阶段状　态．它以前各阶段的状态无法直接影响它未来的决策．而只能通过当　前的这个状态。换句话说。每个状态都是过去历史的一个完整总结。这　就是无后向性．又称为无后效性。　３－３子问题的重叠性　动态规划算法的关键在于解决冗余．这是动态规划算法的根本目　的　动态规划实质上是一种以空间换时间的技术．它在实现的过程中，　不得不存储产生过程中的各种状态．所以它的空间复杂度要大于其它　的算法　选择动态规划算法是因为动态规划算法在空间上可以承受，　而搜索算法在时间上却无法承受．所以舍空间而取时间。　

４求解的基本步骤　动态规划所处理的问题是一个多阶段决策问题．一般由初始状态　开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一　个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最　优的活动路线）。动态规划的设计都有着一定的模式，一般要经历以下　

动态规划的主要难点在于理论上的设计，也就是上面４个步骤的　确定．一旦设计完成．实现部分就会非常简单。使用动态规划求解问　题．最重要的就是确定动态规划三要素：　（１）问题的阶段。　ｆ２）每个阶段的状态　（３）从前一个阶段转化到后一个阶段之间的递推关系。　递推关系必须是从次小的问题开始到较大的问题之间的转化，从　这个角度来说．动态规划往往可以用递归程序来实现，不过因为递推　可以充分利用前面保存的子问题的解来减少重复计算。所以对于大规　模问题来说．有递归不可比拟的优势，这也是动态规划算法的核心之　处。　确定了动态规划的这三要素．整个求解过程就可以用一个最优决　策表来描述．最优决策表是一个二维表，其中行表示决策的阶段，列表　示问题状态．表格需要填写的数据一般对应此问题的在某个阶段某个　状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的　过程就是根据递推关系．从１行１列开始，以行或者列优先的顺序，依　次填写表格．最后根据整个表格的数据通过简单的取舍或者运算求得　问题的最优解　

６动态规划算法基本框架　代码如下所示：　ｎ，ｍ）＝ｍ　｛　ｎ一１，ｍ），ｆ（ｎ－１，ｍ－ｗ［ｎ１）＋Ｐ（ｎ，ｍ））　ｆｏｒＯ＝ｌ；ｊ＜：ｍ；ｊ＿ｊ＋１）／／第一个阶段　ｘｎ啪＝初始值；　（下转第１５８页）　

作者简介：．￣（１９９１－－），女，汉族，新疆昌吉人，天津师范大学计算机与信息工程学院２０１３级计算机应用技术在读硕士研究生，研究方向为生物信息学。　’２６　Ｉ科技视界ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎ。　。ｇｙ　Ｖｉｓｉ。ｎ　科技・探索？争Ｉ乌　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ　Ｖｉｓｉｏｎ　科技视界　测温时将温度计插入测温管中，并￣ａＰＪＪｎｖ．ｚ覆盖．以免受外界气　温影响。测温计至少在管中停留３－５ｒｎｉｎ后读数．读数前应按住酒精柱　顶部位，迅速取出并记下读数，夜间读数需携带电筒。多人配合；测温　时须有监理见证　测温后须将测温孔再次堵上．保温材料覆盖成原状。　项目质检员、工长每天要检查现场测温、保温情况。发现问题及时　处理。　测温记录应真实、及时、准确、签字齐全，须项目总工审核后交资　料员归档。　现场测温记录具体由技术员负责。专职测温员必须经过培训．了　解冬施砼的性质、测温要求，对现场覆盖不严、温差过大、砼温度过高　或过低等不正常现象要有很灵敏的反应．并及时向经理部有关人员和　技术负责人反映实际情况　３．３．５砼试块的制作与养护　砼同配合比、连续浇筑超过１０００ｍ３时按每２００ｍ３取一次样。不足　１０００ｍ３的同配合比砼按每１００ｍ３取一次样的原则进行．取样组数比　常规多不小于两组．用来检查受冻前的临界强度和转人常温２８天后　的砼强度．试验数据应归档：　３．３．６后浇带的保护及施工　砼浇筑完毕后沿后浇带两侧砌起两皮砖．上面覆盖１５厚多层板　与５０Ｘ　１００木枋钉好的盖板，防止污水及垃圾等杂物进入后浇带，污染　钢筋。详见图１后浇带保护做法。　

４工程技术保证措施　

４．４加强周转材料　的管理．抵抗墙的模　板必须平直　４．５严格按设计图　纸要求施工．外模安　装用经纬仪和线锤　检查．保证抵抗墙的　垂直度误差．底板埋　管的中心偏差均小　于设计要求　４．６设立专人做好　测量放线工作．并做　测量记录、备查。　４．７雨季施工．应　采取防雨措施．夏季　砼施工时要做好覆　盖工作．现场准备必　要的材料和设备　４．８施工中严格执　行三检制．明确谁施　工．谁自检．谁负责　的原则　４．９对每道工序进行技术交底，督促、检查和验收，前道工序不合格，　不得进行下道工序的作业，对关键工序应重复交底，并进行重点验收。　４．１０所有原材料进场必须附有出厂合格证或质量证明文件。钢筋、　钢筋连接、砼应按照有关规定进行复试及见证取样试验。所有材料复　试合格后方可用于工程　４．１１砼进场后要进行坍落度检测．每区浇筑砼．首车必须进行坍落　度检测。同时每车采用目测的方式进行检测．如发现不满足要求的要　退场。并增加坍落度检测次数。　４．１２确定底板工程质量控制要点如下：底板轴线、肋梁位置放线，柱　插筋、滚轧直螺纹质量及端部保护帽是否完好，底板后浇带模板安装　质量。砼的测温和保温养护控制。　４．１３在进行底板施工前．应先由测量员对所有测量放线进行校核检　查．特别是检查影响工程质量的关键部位（轴线、柱接头、梁轴线不居　中等部位）．而且测量人员要定期检查平面控制网和高程控制网，以减　少误差．并用红油漆进行标识。经技术员、质量员检查合格后，再报监　理审核合格后方可进行下道工序施工　４．１４在钢筋绑扎施工前．质量检查人员应对钢筋型号、间距、搭接长　度、锚固长度、保护层厚度和机械连接的位置等方面对照施工图纸、图　集、规范等的相应要求进行严格检查。　大体积混凝土底板施工是一个繁杂而反复的过程．只要我们按照　工序要求．以科学的态度去组织施工，一定能保质、保量完成施工任　务。ｅ　

ｆ参考文献ｌ　４．１开工前要落实各级人员岗位责任制，要明确主管领导抓技术；现　［１］ＧＢ５０２０４—２００２混凝土结构工程施工质量　收规范『ｓ】．　

场设立专职技术负责人。使责任制度落实到个人。　［２］建筑施工手册ｆ　．５版缩印版．　４．２做好施工图与方案的技术交底，施工中要认真检查执行情况。　［３］ＧＢ５０２０４—２００２混凝土结构工程施工质量验收规范『ｓ】．　４－３现场设专人做好技术档案管理工作．做好Ｆｔ常设计文件、签证、　变更等的收集整理工作．做好隐蔽记录和施工日记。　［责任编辑：刘帅】　

（上接第１２６页）ｆｏｒ（ｉ＝ｎ一１；ｉ＞＝１；ｉ＝ｉ一１）／／其他ｎ一１个阶段　ｆｏｒ（ｊ＝ｌ；ｊ＞：ｆ（ｉ）；ｊ＝ｊ＋１）／／ｆ（ｉ）－￣ｉ有关的表达式　ｘｉ［ｊ］＝ｊ＝ｍａｘ（或￣ｉｎ）（ｇ（ｘｉ—ｌ［ｊｌ：ｊ２］）……．，ｓ（ｘｉ一１【ｊｋ：ｊｋ＋ｌ】）ｌ；　

ｔ＝ｇ（ｘｌ［ｊｌ：ｊ２］）；，／由子问题的最优解求解整个问题的最优解的方案　

ｆｏｒ（ｉ＝２；ｉ＜＝ｎ－１；ｉ＝ｉ＋１）　｛　ｔ＝ｔ－ｘｉ－ｌ［ｊｉ］；