多重集的全排列算法研究暨分类-毕业论文.doc

《多重集的全排列算法研究暨分类-毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、多重集的全排列算法研究暨分类摘要本文介绍一种新式的，经过优化了的多重集全排列算法TWDRI。同时，本文也分析了所有的多重集全排列算法并按照算法的实现机制进行了分类。为了公平起见，本文通过经验总结出一套模拟和比较算法的机制，并很好地应用在了TWDRI与其他同类算法的性能比较里面。值得庆幸的是，TWDRI确实能够为多重集的全排列和纯排列处理提供理想的速度。论文剩余的部分将研究格雷编码在多重集全排列领域中的应用。并总结了从格雷编码第一次被应用到此领域一直到现在的应用情况和评论，以及一些相关的问题，其中有些问题一直到现在还是处于未解决阶段。在最后，将展望一

2、下多重集全排列算法的一些可能的发展前景，将从目前正在进行的甚至到未来可能的发展方向做个综述，希望以后可以为这个领域进行进一步的研究打下基础。关键词TWDRI算法算法比较全排列格雷编码IIAbstractThethesisisgoingtointroduceTWDRI,anewoptimizedpermutationalgorithmofmultiset.Atthesametime,almostallthealgorithmsofpermutationofmultisetareanalyzedandclassifiedduetotheirinnerp

3、rinciples.Tobeequitable,weemploymethodologysummarizedfromexperiencetosimulateandcomparedataofTWDRItootherwellknown/unknownalgorithmsinthisfield.Wearepleasedtoseeidealspeedinbothpuresetandmultisetpermutationprocessing.Intheremainderofthisthesis,wepaymainattentiontoGraycodeappli

4、edinthesaidfield.WefocusonitsdevelopmentprogressstatusfromwhenGraycodefirstintroducedintothisfieldtothenewestapplicationandcomments,andsomeopenproblemswouldbeissuedwhichhavenotbeenresolveduntilnow.Intheend,expectpossibledevelopmentprospectandsummarizedirectiondevelopingandfutu

5、reofpermutationofmultiset,withthehopeofconstructingbasisforpossiblefuturefurtherstudiesinthissaidfield.KeywordsTWDRI;multiset;pureset;permutation;Graycode;algorithmII目录第一章绪论11.1课题背景和存在的问题11.1.1排列历史11.1.2纯排列算法的历史11.1.3多重集的全排列算法的历史21.1.4排列中的格雷码21.2论文的主要内容21.3论文的组织结构3第二章已有的排列算法的分

6、析总结和分类42.1基本概念42.2分析总结与分类7第三章新式的高性能的排列算法——TWDRI163.1算法流程图163.2算法的时间复杂度分析173.3算法的应用和特点18第四章排列算法中的格雷码应用研究204.1初步的发展204.2新世纪的发展21第五章测试、模拟与比较245.1基于随机输入的平均时间计算模型245.2计算模型的推导过程245.3模拟之后的比较结果265.3.1多重集排列算法的时间和内存开销比较265.3.2多重集算法在纯排列的情况下的时间和内存开销比较285.3.3TWDRI算法和其它纯排列算法的时间和内存比较29VI5.3.

7、4TWDRI算法与其它多重集排列算法的比较趋势分析30第六章总结与展望32致谢36参考文献37VIContentsChapter1Introduction11.1BackgroundandProblems11.1.1HistoryofPermutation11.1.2HistoryofPuresetPermutationAlgorithm11.1.3HistoryofMultisetPermutationAlgorithm21.1.4GrayCodeinPermutation21.2Mainresearch21.3OutlineofThesis3C

8、hapter2Analyse,summariseandclassifyexistentpermutationalgorit