动态规划算法应用与其在时间效率上的优化

《动态规划算法应用与其在时间效率上的优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、声明尸明本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本学位论文中；除了加以标注和致谢的部分外，不包含其他人已经发表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均●已在论文中作了明确的说明。研究生签名：年月目学位论文使用授权声明南京理工大学有权保存本学位论文的电孚和纸质文档，可以借阅或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对于保密论文，按保密的有关规定和程序处理。．研究生签名：年月日

2、硕士论文动态规划算法应用及其在时间效率上的优化引言动态规划(DynamicProgramming)是运筹学的一个分支，是求解决策过程(DecisionProcess)最优化的数学方法。20世纪50年代初美国数学家R．E．Bellman等人在研究多阶段决策过程(MultistepDecisionProcess)的优化问题时，提出了著名的最优化原理(PdncipleofOptimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming

3、[¨，这是该领域的第一本著作。动态规划问世以来，在城市规划【2】、经济管理【3】【4】【5】、生产调度№】【7】、工程技术和最优控制等方面得到了广泛的应用。例如神经网络【8】【9】【101[11】【12】【13】、生物有机体DNA的相似程度分析【14】、最短路线【15】【161、库存管理【171、资源分配【18】【19】、资产投资[20]12¨、证券交易阎、经营决策1231、企业生产物流控制【24】、农业灌溉瞄1126]、施工计划安排【27】【2引、单一品种项目的生产批量问题【29】、设备更新、最优化设计【301[31】【321133113

4、4】【35】、学习方法【361、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。动态规划主要用于求解以时间划分阶段的动态过程的优化问题，而且一些与时间无关的静态规划【3刀(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。在计算机算法设计方法中，动态规划技术是比较基本，但又比较抽象，难于理解的一种。它建立在最优原则的基础上，采用动态规划方法，可以优雅而高效地解决许多用贪心技术或分治技术无法解决的问题。因此，动态规划技术越来越成为解决许多重要的应用问题的关键技术。例如，用动态规

5、划解决O．1背包问题、图像数据压缩、矩阵连乘【38】、不等式证明【391、有向图最短路径【15】【161、无交叉子集、多目标跟踪【40】、元件折叠以及最长公共子序列【41】【42】【43】等应用问题。另外，在语音识别领域，应用动态规划技术的动态时间伸缩算法DTW取得了很大成功，当词汇表较小以及各个词条不易于混淆时，DTW可以有效地解决孤立词识别时说话速度不均匀的难题，从而自20世纪60年代末期掀起了语音识别研究的热潮。动态规划技术是基本算法设计技术中较难掌握但也是极其重要的一种方法，它的应用领域非常广泛，除了本文提到的一些问题之外，动态规划

6、还用于解决字符串搜索问题、手写字符识别问题、网络的无交叉布线、电路元件折叠和旅行商问题等各种实际应用问题，因此，掌握动态规划技术对提高计算机算法设计和分析水平及解决实际计算问题具有至关重要的作用和意义。近年来，除了基本的动态规划设计方法之外，随机动态规划【删、基于Pipeline的一类动态规划并行算法【451、离散型动态规划[461、动态规划顺序算法【47】f481、多目标动引言硕士论文2态规划时段轮换并行算法[491、灰色动态规划【501、多约束动态规划【5l】、马尔可夫动态规划【521、线性动态规划【53】、模糊优选动态规划【54115

7、51、动态规划逆序算法【56】、大型动态规划的分解算法【57】、动态规划的单增量搜索算法f581、多目标动态规划分层解法与Pareto最优解【”J等很多方面都得到了长足的发展。本文在撰写过程中参考了大量的文献资料，尽量使得行文能够充分展现动态规划所涉及的诸多方面并进行深入讨论，通过大量的算法设计实例阐述包括动态规划的理论基础、实际应用、优化改进在内的几大方面的问题。硕士论文动态规划算法应用及其在时间效率上的优化1绪论动态规划是算法设计的一种重要手段，在各行各业的程序设计中被应用得越来越普遍。因此，如何更深入地了解动态规划，从而更为有效地运用

8、算法设计的这个有力武器，是一个值得深入研究的问题。要掌握动态规划的应用技巧，就要了解它的各方面的特点。本章内容将从三个方面进行简单阐述：1、动态规划的本质2、动态规划的设计与实现