旅行售货员问题 毕业论文

《旅行售货员问题 毕业论文 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要旅行售货员问题是一个古老而典型的组合优化问题。对该问题合理而有效的解法不但有重要的理论和学术意义，同时对众多工程实际中的应用提供了重要的指导意义。这篇论文首先对问题进行了大体的陈述，对其进行了数学描述。在此基础上,本文对问题进行了进一步的定义。论文介绍了五种算法的基本概念、原理、意义及发展现状。这五种算法包括动态规划法、分支界限法、回溯法、遗传算法和微粒子算法。并展示了部分算法的部分数学过程。关键词：旅行售货员问题；遗传算法；微粒子算法；回溯法-I-SeveralSolutionstoTravelingSalesmanProble

2、mAbstractTravelingsalesmanproblemisanoldandtypicalhardcombinatorialoptimizationproblem,itsvalidandeffectivesolutionsnotonlyhasimportanttheoreticalandacademicvalues,butalsohasimportantguidingsignificanceformanypracticalengineeringapplications.Theessaystartswiththegeneral

3、accountof,explainsthemathematicaldescriptionof.Ontheoriginalbasis,theessaymadethroughclassificationof;Theessayintroducedthebasicconcept,principle,procedureandsignificanceoffivetypesofalgorithm,includingdynamicprogramming,branchboundingmethod,backtrackingmethod,Genetical

4、gorithm,ParticleSwarmOptimization.Italsodisplayedsomemajorprocessinmathematicways..KeyWords：TravelingSalesmanProblem;GeneticAlgorithm;BacktrackingAlgorithm-III-目录摘要IAbstractII引言11旅行售货员问题的研究现状21.1旅行售货员问题概述21.2旅行售货员问题的数学描述31.3旅行售货员问题的分类41.4前人的工作51.4.1精确算法51.4.2启发式算法51.5本章

5、小结52精确算法求解策略及优化算法62.1动态规划法解旅行售货员问题62.1.1动态规划思想简介62.1.2动态规划求解旅行售货员问题62.2分支限界法解问题62.3回溯法解旅行售货员问题82.3.1回溯法思想简介82.3.2回溯法求解履行商问题82.3.3回溯法的不足92.3.4回溯算法的改进92.4三种精确算法的比较102.4.1动态规划法和回溯法的比较102.4.2分支限界法和回朔法的比较113遗传算法解决旅行售货员问题123.1启发式算法简介123.2遗传算法介绍123.2.1遗传算法发展123.2.2遗传算法自身特点133.

6、2.3遗传算法总结133.3基本遗传算法求解旅行售货员问题14-III-4微粒子算法简介154.1微粒子算法历史154.3微粒子算法结合旅行售货员问题155旅行售货员问题的应用16结论17参考文献18附录Ａ　旅行售货员问题的最小耗费分枝定界算法19附录Ｂ　旅行售货员问题的回溯法22致谢24-III-学院学士学位论文引言旅行售货员问题(TravelingSalesmanProblem)，是计算机算法中的一个经典的难解问题，已归为完备问题(Nonpolynomial)类。围绕着这个问题有各种不同的求解方法，已有的算法如动态规划法，分支限界

7、法，回溯法等，这些精确式方法都是指数级的，根本无法解决目前的实际问题，贪心法是近似方法，而启发式算法不能保证得到的解是最优解，甚至是较好的解释。所以我认为很多问题有快速的算法(多项式算法)，但是，也有很多问题是无法用算法解决的。事实上，已经证明很多问题不可能在多项式时间内解决出来。但是，有很多很重要的问题他们的解虽然很难求解出来，但是他们的值却是很容易求可以算出来的。这种事实导致了完全问题。凡是在多项式复杂程度内可以求出最优解的问题，称为问题，其它的则是问题。在算法问题上，假如一个问题是问题，我们通常认为它是“简单的”，对于一个问题，

8、通常认为它是“复杂的”。表示非确定的多项式，意思是这个问题的解可以用非确定性的算法"猜"出来。如果我们有一个可以猜想的机器，我们就可以在合理的时间内找到一个比较好的解。完全问题学习的简单与否，取决于问题的难易程度。因为有