TRAVELING SALESMAN PROBLEM SOLUTION PROCESSING SYSTEM USING PARALLEL COMPUTER

摘要

PURPOSE: To determine a traveling salesman problem at high speed by using the communication network between adjacent cells and to determine an optimum solution, regarding a parallel computer. ;CONSTITUTION: Each cell 1 is provided with a message transmission means using that the route length between two cities of a traveling salesman problem is proportional to the communication time between cells, adding cell information when a message is received and transmitting the message to an adjacent cell via a network. The start cell transmitting the message at first is provided with a message monitoring means defining a message as the one via a shortest route and terminating a route search processing when whether the received message is the one via all the cities or not is monitored and the message returning to the start cell via all the cities at the earliest time is detected.;COPYRIGHT: (C)1996,JPO