货郎担问题最优并行启发式算法

Optimal Parallel Heuristic Algorithm for Travelling Salesman Problem

本文给出了满足三角不等式的货郎担问题的并行启发式算法，在ＳＩＭＤＣＲＥＷＰＲＡＭ并行机上该算法使用Ｏ（ｎ２／ｌｏｇ２ｎ）台处理器需Ｏ（ｌｏｇ２ｎ）时间，这里ｎ是给定城市的个数，因而该并行算法是最优的。

This paper presents a parallel heuristic algorithm for travelling salesman problem satisfying triangle inequality. This algorithm uses O(n2/log2n) processors and O(log2n)time on SIMD CREWPRAM, where n is the number of given cities, so it is optimal.