Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections
✍ Scribed by Chang-Sung Jeong; Myung-Ho Kim
- Publisher
- Elsevier Science
- Year
- 1991
- Tongue
- English
- Weight
- 459 KB
- Volume
- 17
- Category
- Article
- ISSN
- 0167-8191
No coin nor oath required. For personal study only.
✦ Synopsis
Jeong, C.S. and M.H. Kim, Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections, Parallel Computing 17 (1991) 221-228 In this paper, we present a fast parallel simulated annealing algorithm for solving traveling salesman problem(TSP) on SIMD machines with linear interconnections among processing elements. Simulated annealing is a generally applicable algorithm for solving combinatorial optimization problems by generating a sequence of moves at decending values of a control parameter. In our algorithm for TSP, the move operation can be executed in proportional to the time taken to broadcast a bit in one processing element (PE) to all the other PE's. Therefore, if a control unit has the broadcasting capability as is often the case with the SIMD machine, the move operation can be done in constant time and the whole simulated annealing algorithm has the time complexity only proportional to the number of the moves.