最优聚丛原理与聚丛法求解旅行商问题

Optimal Clumping Principle and Clumping Method to Solve Traveling Salesman Problem

最优聚丛原理是解决算法集和演算集极小化问题、NP完全问题的一个基本的计算复杂性原理 ,引入了稠密、有洞算法概念。以此为基础 ,提出了GED聚丛法 ,它是几何算法G、生态算法E和判定问题D的近似演算等三方面合力求解旅行商问题 (TSP)的方法。给出了求解TSP流程及实例 ,计算结果验证了该原理和方法的正确性和精巧性。

This paper advances the optimal clumping principle which is the basic principle of computation complexity for solving the minimizing problems of the algorithm sets and calculus sets and the NP-complete problems. Two ideas, i.e. dense algorithm and cavernous algorithm, are introduced. Based on the above principle and ideas, a clumping method with geometric algorithm, ecological algorithm and decision problem approximate calculi to solve traveling salesman problem is presented. The arithmetic process is detailed in this paper. Experimental results show the validity of the principle and the exquisiteness of the method.\;