《图论》课程专题论文--中国邮递员问题各种算法的对比分析

《《图论》课程专题论文--中国邮递员问题各种算法的对比分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、论文编号2008SX2011—002附录2《图论》课程专题论文论文题目：中国邮递员问题各种算法的对比分析班级：2008级数学与应用数学组长：马利巍姓名马利巍陈世红周子婷石静余庭学号P081513092P081513090P081513091P081513095P081513120成绩分工情况构思论文框架，进行论文摘要部分、以及内容撰写，对论文内容进行审定工作构思论文框架，进行论文主体内容撰写，对论文归纳总结，并进行论文文字敲定工作构思论文框架，进行论文主体内容撰写，总结论文，并进行论文文字敲定工作构思

2、论文框架，对论文内容审定，对论文进行归纳总结，以及论文格式排版工作构思论文框架，进行论文文字敲定，以及论文打印工作2011年12月27日42论文评价指标与鉴定意见论文题目中国邮递员问题各种算法的对比分析完成人马利巍陈世红周子婷石静余庭班级2008级数学与应用数学指标论文评价（对表格中的各栏，用“√”表示意见）优良中差论文选题基础理论与专门知识语言的表达水平创新性学术价值应用价值总体评价A（86—100分）B（70—85分）C（60—69分）D（0—59分）鉴定意见成绩评阅人职称专业42摘要本文基于无向

3、图的传统中国邮递员问题,给出了相应的显式整数规划模型,进一步讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型；并研究了随机中国邮递员问题,建立了相应的确定型等价模型。并可以利用奇度数结点的配对来进行求解。根据此思想给出了一种新的求解思路——通过去掉原始图中的偶度数结点并利用最小生成树来确定奇度数结点的配对。提出了“虚拟权值”和“虚拟节点”的概念,给出了中国邮递员问题的一种基于DNA计算的求解算法。新算法首先利用多聚酶链式反应技术来排除非解,从而得到中国邮递员问题的所有可行解；然后

4、,结合基于表面的DNA计算方法与荧光标记等技术,最终从所有可行解中析出最优解。通过各种算法分析比较表明,新算法具有易于解读、编码简单等特点。关键字：中国邮递员问题整数规划最优化模型奇度数结点最小生成树DNA计算多聚酶链式反应42AbstractBasedonthetraditionalChinesetofigurewithoutthepostmanproblem,Thecorrespondingdisplayintegerprogrammingmodel，furtherdiscussedbasedon

5、adirectedgraphofthegeneralizedChinathepostmanproblem，thecorrespondingdisplayintegerprogrammingmodel；AndthetraditionalChinathepostmanproblem，establishedthecorrespondingequivalentmodelthatcanandcanuseodddegreeofnodestosolvingmatching。Accordingtothisthough

6、tgivesanewmethodforsolvingthinking—byremovingtheoriginalgraphofthedegreeandusethenodeaccidentallyminimumspanningtreetodeterminethedegreeofthenode′spairing。Putforwardthe“virtualweights”and“virtualnode”，givenChinaapostmanofDNAcomputingalgorithmisbasedon。F

7、irstthenewalgorithmismoreMeiliantogethertoexcludethetechnologyofreactionsolution，andthengotthepostmanallfeasiblesolutionstoproblems；Andthen，basedonthesurfacewithDNAcalculationmethodsandfluorescentmarkers，andfromallthefeasiblesolutionofeventuallygettheop

8、timalsolution。Throughthecomparisonofthealgorithmanalysisshowthatthenewalgorithmiseasytoread，codesimplefeatures。Keywords：ThepostmanproblemofChinaIntegerprogrammingOptimizationmodelOdddegreenodeMinimumspanningtreeDNAcalculationMore