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

Optimal Parallel Heuristic Algorithm for Travelling Salesman Problem

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

Abstract: 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.