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

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

1、南京理工大学硕士学位论文动态规划算法应用及其在时间效率上的优化姓名：吴涛申请学位级别：硕士专业：计算机应用技术指导教师：孙兴华20080101硕士论文动态规划算法应用及其在时间效率上的优化摘要算法设计是软件设计的灵魂内容，动态规划作为相对成熟的算法设计技术，不断地被运用到工农业生产、经济、军事、工程技术等很多方面，显示出其高效、实用的性能和宽阔的应用前景。本文对动态规划所涉及的诸多方面进行了深入的研究，通过大量的程序设计实例阐述了包括动态规划的理论基础、实际应用、优化方法在内的几大方面的问题。具体包括：一、从动态

2、规划的本质入手，介绍了多阶段决策问题、阶段与状态、决策与策略、最优化原理与无后效性、最优指标函数和规划方程等一些专有名词的定义；利用一些常见的实例阐述了动态规划在设计与实现时的多样性、模式性和技巧性等特点；通过与一些常见算法的比较，讲解了动态规划与这些算法的区别和联系，突出了使用动态规划时的最优化、高效率和高消费等特性。二、从三个具体问题的解决过程中可以看出，动态规划是必不可少的有力工具。通过问题描述、样例分析、算法设计、问题实现、测试结果等几个步骤详细讨论了动态规划在应用中的实现过程和思考方法，体现出在应用中相

3、应的实践指导意义。三、鉴于动态规划在简单设计后还存在很大的时间冗余，从构成其时间复杂度的三个方面：状态总数、每个状态转移的状态数、每次状态转移的时间进行优化，使得动态规划在时间效率上得到了进一步的提升，以期面对并解决更大数据规模的问题。不仅给出了优化的理论依据和具体方法，而且还给出了五个引用实例在优化前后的实验运行对比结果。最后，总结全文，分析了动态规划的应用和优化在面对不同问题时需要进一步完善的地方，并指出了今后工作的研究方向。关键词：动态规划，状态转移，时间复杂度，优化AbS仃act硕士论文AbstractT

4、hedesignofthealgorithmisthemaincontentofsoftwaredesign．Asamaturetechniqueofalgorithmdesign，dynamicprogrammingiswidelyusedinindustry,agriculture，economy,military,engineeringandsomeotherfields，whichindicatesthatitisefficientandpracticalandithasabrightfuture．The

5、dissertationdealswitllmanyaspectsofdynamicprogramming．Byusingmanyexamplesofprogramming，itgivesadetailedexplanationofdynamicprogramming’Srationale，applicationandoptimizationmethod．Thedetails1istedasfollows：First．throughtheintroductionofitsessence，itintroducest

6、hedefinitionofsometermssuchasmultistagedecision-making，stageandstate，decision-makingandstrategy,optimalityprinciple，non—aftereffect，optimaltargetfunction,programmingequationandSOon．Byusingsomecommonexamples，itgivesafulldescriptionofthediversity,thepattemandth

7、eartificeofdynamicprogrammingindesigningandapplication．Bycomparingwithsomecommonalgorithms，itexplainstheirdifferencesandrelationshipsandemphasizesitscharacteristics⋯optimized，efficient，andconsumptive．Second，throughsolvingthreeproblems，wecanfinddynamicprogramm

8、ingisanecessity．Withthehelpofthefollowingsteps，likeproblemdescribing，sampleanalyzing，algorithmdesigning，problemsolvingandresulttesting，itgivesafullexplanationoftheimplementationprocessand