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

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

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

著录项

作者
李强;
展开▼
作者单位

中南民族大学;

展开▼
授予单位中南民族大学;
学科计算机应用技术
授予学位硕士
导师姓名蓝雯飞;
年度 2015
页码
总页数
原文格式 PDF
正文语种中文
中图分类算法理论;
关键词
动态规划; 时间效率; 优化设计;

相似文献

中文文献
外文文献
专利

1. 一种改进时间效率的动态规划算法的设计与实现 [J] . 张振球 . 电子制作 . 2019,第024期
2. 动态规划算法的时间效率改进 [J] . 蓝雯飞 ,吴子莹 ,李强 . 中南民族大学学报（自然科学版） . 2016,第002期
3. 以总加权完工时间为目标的两台机越库排序的动态规划算法 [J] . 马东彦 ,陈峰 . 上海交通大学学报 . 2007,第5期
4. 长江集装箱多式联运路径优化动态规划算法 [J] . 李俊 ,梁晓磊 ,赵胜 . 计算机工程与设计 . 2021,第011期
5. 以总加权完工时间为目标的两台机越库排序的动态规划算法 [C] . 马东彦 ,陈峰 . 第六次中国物流学术年会 . 2007
6. 动态规划算法应用及其在时间效率上的优化 [A] . 吴涛 . 2008

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

目录

摘要

著录项

相似文献

相关主题

期刊订阅