论文部分内容阅读
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设计动态规划过程的并行算法。