若干算法设计模式的研究与应用

《若干算法设计模式的研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要自动程序设计一直是计算机科学的一个奋斗目标，而算、法【lJ是程序的灵魂，是解决问题的关键，是程序设计的基础和难点，要实现程序设计的自动化首先应该实现算法设计的自动化。但算法设计是一项创造性的劳动，因此要实现自动程序设计的目标目前还存在很多困难。在长期的算法和程序设计实践中，人们总结出来了一些常用而有效的算法设计方法：贪心法、分而治之法、动态规划法、回溯法和分枝定界法，很多问题均可以使用它们进行求解。因此，我们期望通过对这些算法设计方法的深入研究，抽取每种方法在求解问题时的共同规律，利用泛型程序设计的思想，构造上述五类常用算法设计方

2、法的算法设计模式。当面临一个具体问题求解时，只需根据该问题的特点和性质，对算法设计模式进行实例化，即可生成问题的求解程序，不仅可以降低程序开发的难度，而且可以对推动算法设计自动化研究探索一条有效的途径。因此本文主要工作包括：1、对贪心法、分而治之法、动态规划法、回溯法、分枝定界法进行了深入研究，并对这五种算法设计方法分别进行抽象，形成对应的算法设计模式，这是本文研究的重点与难点。2、以本文抽象出的五种算法设计模式为基础，构造相应的算法设计模板。3、以若干典型问题为例，说明上述所得算法设计模板的使用方法。实践证明，本文开发的五种算法设计

3、模板具有较好的可重用性，使用它们开发应用程序，能有效地降低程序开发的难度，提高程序开发效率。同时由于它们经过许多实例测试保证了其可靠性，从而提高了以它们为基础所开发的应用程序的可靠性。关键词：算法；算法设计方法；算法设计模式；泛型程序设计AbstractAutomaticprogramminghasbeenastruggletargetinthefieldofcomputerscience．Algorithmsarethesoulofprograms，thekeyofproblemsolution，thebasisanddifficu

4、ltyofprogramming．Therealizationofautomaticprogrammingdependsontherealizationofautomationofalgorithmdesign．Becausealgorithmdesigniscreativelabor,themarcmanydifficultiesintherealizationofautomaticprogramming．Inthelong-termpracticeaboutalgorithmandprogramdesign，peoplehaves

5、ummarizedsomefrequently-usedandeffectivealgorithmdesignmethods：Greedy,DivideandConquer,DynamicProgramming，BacktrackingandBranchandBound．BecausemanyprogramsCallbesovledbythem，weexpectextractingthecomtmollnessofeachalgorithmbylucubrationaboutitandconstructitsalgorithmdesi

6、gnpatternbygenericmechanism．Whenwewanttosolveaproblem，itsprogramCanbegeneratedbyinstantiationofitscorrespondingalgorithmdesignpattern．Itcannotonlydebasethedifficultyoftheprogramdevelopment，butalsoprovidealleffectiveapproachfortheresearchofautomationofalgorithmdesign．The

7、mainworksinthispaperinclude：1、BasedontheresearchaboutGreedy,DivideandConquer,DynamicProgramming，Backtracking，BranchandBound，weabstractthesefivealgorithmsintoalgorithmdesignpatterns．Thisisthekeystoneanddifficultyoftheresearchinthispaper．‘2、Basedonthefivealgorithmdesignpa

8、tterns，thealgorithmdesigntemplatesarerealized．3、Theusageoftheabovealgorithmdesigntemplatesareshownbysometypica