动态规划算法时间效率优化策略研究

发布时间：2017-08-19 21:20

  本文关键词：动态规划算法时间效率优化策略研究

  更多相关文章： 动态规划 时间效率优化 状态 状态转移

【摘要】：二十世纪五十年代,美国数学家理查德贝尔曼(R.E.Bellman)根据一类多阶段决策优化问题的特点,提出了最优化原理即无论问题的初始状态如何,问题以后的决策相对于初始状态都是最优策略,最优化原理是动态规划的基础。动态规划的基本思想就是将待求解的问题划分成若干子问题,通过将子问题逐一解决从而解决整个问题。动态规划思想可以有效地解决一类多阶段决策优化问题。动态规划是一种算法设计思想。在过去的五十多年里,动态规划在各个领域中得到了广泛的应用。例如最短路径、项目群资源优化、资产的投资决策、字符串匹配、设备更新、地图导航、水资源的调度分配等问题。在适用的情况下,动态规划可以高效率地解决一类动态决策问题,因此,无论是在理论还是在实践上对动态规划算法的研究都具有重要的意义。本文主要研究了动态规划的理论基础,及其时间效率优化等几个方面的内容。具体包括:(1)从动态规划算法的基础理论入手,概述了动态规划中的术语,如阶段、状态、多阶段决策、指标函数、状态的无后效、重叠子结构等一些专有名词,并归纳了动态规划中常见的子问题模型。探讨了动态规划与常见算法的比较,通过与其它算法的比较凸显了动态规划在解决实际问题时空间消耗大,全局最优以及时间效率高等特点。(2)探究动态规划在时间效率上的优化。现有的研究一般针对具体问题的特点设计优化措施,当问题不同时,相应的优化措施就失去作用。论文从影响动态规划算法时间复杂度的因素出发,从影响其时间效率的三大方面:问题中需要计算的状态个数、状态转移时涉及的状态数、状态转移的时间进行优化。优化时实现三者的平衡,从而在整体上提升算法的时间效率,使其能够适用于数据规模更大的问题。(3)为了验证动态规划算法时间效率优化措施的有效性,将动态规划方法运用于经典的组合优化难题——背包问题。首先分析了解决0/1背包问题和完全背包问题的经典动态规划算法;接着利用动态规划的优化措施改进原有的动态规划算法;然后通过实验得出不同动态规划算法在解决背包问题时的时间效率。实验结果表明本文提出的改进算法在一定程度上降低了时间复杂度。
【关键词】：动态规划 时间效率优化 状态 状态转移
【学位授予单位】：中南民族大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221.3
【目录】：

• 摘要7-8
• Abstract8-10
• 第1章 绪论10-14
• 1.1 选题的背景与研究的意义10-11
• 1.2 国内外研究现状11-12
• 1.3 本文的研究内容12
• 1.4 本文的组织安排12-14
• 第2章 动态规划算法思想14-25
• 2.1 动态规划算法的本质14-20
• 2.1.1 多阶段决策问题14-15
• 2.1.2 动态规划算法的术语15-16
• 2.1.3 动态规划算法适用的条件16-19
• 2.1.4 动态规划算法设计的模式性19
• 2.1.5 常见的子问题模型19-20
• 2.2 动态规划与其它算法的比较20-23
• 2.2.1 动态规划与分治的比较20-21
• 2.2.2 动态规划与贪心的比较21-22
• 2.2.3 动态规划与搜索的比较22-23
• 2.3 本章小结23-25
• 第3章 动态规划算法在时间效率上的优化25-36
• 3.1 动态规划算法在时间复杂度上优化的必要性25
• 3.2 动态规划算法的时间效率分析25-26
• 3.3 状态总数的优化26-27
• 3.3.1 双向动态规划26-27
• 3.3.2 改进状态的表示27
• 3.4 每次状态转移所涉及的状态数的优化27-34
• 3.4.1 四边形不等式与决策量的优化27-30
• 3.4.2 合理组织已求解的状态30-32
• 3.4.3 运用贪心思想优化动态规划算法32-34
• 3.5 状态转移时间的优化34-35
• 3.6 本章小结35-36
• 第4章 动态规划优化措施在背包问题中的应用研究36-55
• 4.1 0/1 背包问题36-45
• 4.1.1 问题描述36
• 4.1.2 问题的动态规划算法36-38
• 4.1.3 动态规划算法改进38-41
• 4.1.4 实验与分析41-45
• 4.2 完全背包问题45-54
• 4.2.1 问题描述45
• 4.2.2 问题的动态规划算法设计45-46
• 4.2.3 动态规划算法改进46-49
• 4.2.4 实验与分析49-54
• 4.3 本章小结54-55
• 第5章 总结与展望55-57
• 5.1 总结55
• 5.2 展望55-57
• 参考文献57-60
• 致谢60-61
• 附录A 攻读学位期间发表的学术论文61

【相似文献】

中国期刊全文数据库 前10条

1 李菲;肖洪祥;;基于神经动态规划算法的最优路径选择[J];桂林工学院学报;2009年01期

2 罗宗俊;;高维0-1瓶颈问题的动态规划算法[J];数值计算与计算机应用;2013年01期

3 周静;;运用动态规划算法解决最大价值路线图问题[J];硅谷;2013年15期

4 李乐园;林诒勋;;电力网调度时间表问题的动态规划算法[J];河南科学;1988年02期

5 徐绪松;工序问题的动态规划算法[J];武汉大学学报(自然科学版);1994年05期

6 赵钰;徐涛;陈红军;;炮兵营火力分配的二阶动态规划算法[J];四川兵工学报;2009年09期

7 陈捷;;基于动态规划算法的最值问题分析[J];电脑与信息技术;2013年06期

8 廖慧芬;邵小兵;;动态规划算法的原理及应用[J];中国科技信息;2005年21期

9 刘莹;;改进的动态规划算法在最优航线选择中的应用[J];邵阳学院学报(自然科学版);2007年01期

10 王雪瑞;秦勤;李建;;Possible Winner问题参数算法研究及核心化[J];湘潭大学自然科学学报;2012年04期

中国重要会议论文全文数据库 前2条

1 顾文彬;高梅国;;基于改进动态规划算法的雷达微弱目标检测[A];中国航空学会信号与信息处理专业全国第八届学术会议论文集[C];2004年

2 唐玲娜;唐雪飞;叶昌伟;;动态规划算法正序实现及其改进[A];2008'中国信息技术与应用学术论坛论文集（二）[C];2008年

中国重要报纸全文数据库 前1条

1 PALADIN;动态规划算法设计[N];电脑报;2003年

中国硕士学位论文全文数据库 前10条

1 许虎;基于动态规划算法的网瘾戒除辅助活动规划系统的研究与实现[D];东北大学;2013年

2 刘昭;基于DP算法插电式柴电混合动力汽车控制策略研究[D];重庆交通大学;2015年

3 李强;动态规划算法时间效率优化策略研究[D];中南民族大学;2015年

4 丁伟军;结合近似动态规划算法的串行生产系统风险管理研究[D];清华大学;2011年

5 张玉斌;迭代动态规划算法及并行化研究[D];中国石油大学;2008年

6 吴涛;动态规划算法应用及其在时间效率上的优化[D];南京理工大学;2008年

7 李前兴;工业过程迭代动态规划算法研究[D];浙江大学;2011年

8 农健恒;同尺寸物品装箱的动态规划算法[D];广西大学;2014年

9 杜君;MPP环境中面向动态规划算法的混合并行系统的研究[D];天津大学;2014年

10 杨再新;高频雷达运动目标多帧检测技术研究[D];哈尔滨工业大学;2014年

，

本文编号：703041