欧氏平面上货郎问题的一个多项式时间近似方案的改进与实现

论文摘要

NP-Hard优化问题的近似算法设计一直是计算机科学的重要内容。货郎问题（Traveling Salesman Problem，简称“TSP”）是计算机算法理论历史上的经典问题。在过去几十年中，它成为许多重要算法思想的测试平台，同时也促使一些新的理论领域的产生，比如多面体理论和复杂性理论。货郎问题：给定n个结点和任意一对结点{i，j}之间的距离为di，j，要求找出一条闭合的回路，该回路经过每个结点一次且仅一次，并且该回路的费用最小，这里的费用是指每段路径的距离和。货郎问题求解其精确解是NP难的，并且求解任意常数因子近以度的解也是NP难的。若将问题限定在欧氏平面上，就成为欧氏平面上的货郎问题。但是，即使是欧氏平面上的货郎问题也是NP难的。Arora在1996年使用随机平面分割和动态规划方法给出了欧氏平面上TSP问题的第一个多项式时间近似方案。本文首先介绍丁使用随机平面分割和动态规划设计欧氏平面上货郎问题多项式时间近似方案的方法，同时提出一种新的构造方法，使应用于该算法的“补丁定理”中的常数g由常数6改进到常数3，并给出明确证明。通过改进g的值，使算法中m，r的值减小，从而使算法的执行时间得到改善。最后，我们用Java语言实现了该算法，并用国际上通用的TSPLIB中的3个不同规模的实例对算法进行测试。通过对实验结果的分析，指出可以从可以以下两个方面对算法进一步改进：1，在动态规划过程中采用剪枝技术，并找出了两类不需要存储和计算的实例情况，使算法的时间性能和空间性能得到改善。2设计动态规划过程的并行算法。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 TSP的发展历史
• 1.2 TSP的应用和价值
• 1.3 本文的篇章组织
• 第2章 TSP问题近似算法的研究进展
• 2.1 近似算法的基本概念
• 2.2 多项式时间近似方案
• 2.3 TSP问题
• 2.4 TSP问题一些近似算法
• 2.4.1 最近邻算法NN
• 2.4.2 基于最小生成树的算法MST
• 2.4.3 最小权匹配算法MM
• 2.5 欧氏平面上的货郎问题
• 2.5.1 欧氏平面
• 2.5.2 欧氏平面上货郎问题的算法
• 2.6 本章小结
• 第3章 欧氏平面上TSP问题的多项式时间近似方案及改进
• 3.1 随机平面分割的相关概念
• 3.2 欧氏平面上TSP问题的算法
• 3.3 算法的改进
• 3.4 本章小结
• 第4章 程序实现与实例测试
• 4.1 程序实现
• 4.1.1 算法的流程
• 4.1.2 算法中主要的类
• 4.2 实验数据及测试结果
• 4.3 实验结果分析
• 4.4 本章小结
• 第5章 结论与展望
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表