- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
ACM论文 张辰轩态规划ACM论文 张辰轩动态规划
动态规划【目录】
一。引言二。动态规划的基本思想三。动态规划算法的基本步骤四。动态规划的适用条件五。动态规划的实例分析六。动态规划的技巧——阶段的划分和状态的表示七。动态规划实现中的问题八。动态规划与其他算法的比较九。动态规划的理论模型一。引言动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming,这是该领域的第一本著作。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。二。动态规划的基本思想一般来说,只要问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择;而分治法中的各个子问题是独立的 (即不包含公共的子子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。因此,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解。三。动态规划算法的基本步骤设计一个标准的动态规划算法,通常可按以下几个步骤进行:1。划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性),否则问题就无法用动态规划求解。2。选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。确定决策并写出状态转移方程:之所以把这两步放在一起,是因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。3。写出规划方程(包括边界条件):动态规划的基本方程是规划方程的通用形式化表达式。一般说来,只要阶段、状态、决策和状态转移确定了,这一步还是比较简单的。动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计算,实现的大体上的框架如下:标准动态规划的基本框架对fn+1(xn+1)初始化;????????????????????????????? △ 处理边界条件for k ← n downto 1 do?? for 每一个xk∈Xk do????? for 每一个uk∈Uk(xk)????????? do fk(xk) ← 一个极值????????????????? △ ∞或-∞??????
您可能关注的文档
- 64m主跨连续梁施方案64m主跨连续梁施工方案.doc
- 600MW脱硫培训材教材.doc
- 65普法内容111.doc
- 601家长会发言稿.doc
- 67教师工作量管理统系统.doc
- 6Aunit 7教.案..doc
- 6B Unit 2.doc
- 67六层砖混施工组设计67六层砖混施工组织设计.doc
- 6B Unit 7试卷6B Unit 7测试卷.doc
- 50本好书推荐50好书推荐.doc
- 学习活动三+《逻辑的力量之采用合理的论证方法》课件-2024-2025学年统编版高二语文同步备课精选课件(选择性必修上册).pptx
- Unit 4 Friends Forever Understanding Ideas Click for a Friend 课件-2024-2025学年高一上学期英语外研版(2019)必修第一册.pptx
- 《大学之道》课件-2024-2025学年统编版高二语文同步备课精选课件(选择性必修上册).pptx
- Unit 2 Let's talk teens Wordlist 课件-2024-2025学年高中英语牛津译林版(2020)必修第一册.pptx
- 函数的概念(第二课时)课件-2024-2025学年高一上学期数学人教A版(2019)必修第一册.pptx
- 学习活动二+《逻辑的力量之运用有效的推理形式》课件-2024-2025学年统编版高二语文同步备课精选课件(选择性必修上册).pptx
- Unit 1 Science and Scientists Reading for Writing 课件-高中英语同步备课系列(人教版2019选择性必修第二册).pptx
- 事件的相互独立性、条件概率与全概率公(课件)-2025年高考数学一轮复习.pptx
- Unit 1 Teenage Life 一轮复习课件-2025届高三英语人教版(2019)+必修第一册.pptx
- 2024届高考语文复习:二轮复习作文教学备考+课件.pptx
文档评论(0)