TSP问题的一种快速近似算法及应用

给出求解度约束最小生成树(DCMST)问题的一种快速近似算法．在此基础上．又给出求解TSP问题的一种快速近似算法，并在微机上实现且其数值试验的效果良好．最后，将求解TSP问题的近似快速算法作一些改进．应用于遗传算法的初始种群生成并进行数值实验．结果表明，用文中算法生成的初始种群．比起一般方法产生的初始种群性能有很大改进．该算法可以加速遗传算法的寻优速度．

A Fast and Approximate Algorithm For Solving Travelling Salesman Problem and Its Applicalion

A fast and approximate algorithm is given at first for solving the problem of minimum spanning tree with constraint of degree. On this basis, a fast and approximate algorithm is then given for solving travelling salesman problem (TSP); and is implemented on a micro-computer, with a good effect as shown by enormous numerical tests. This fast and approximate algorithm for solving TSP is applied finally to generating initial population of genetic algorith after a little modification; and the improved algorithm is tested numerically. As indicated by experimental results, the initial population generated by this algorithm inproved greatly as compared with the performance of the initial population generated by the conventional method; and furthermore, this algorithm will accelerate the optimum search of genetic algorithm.