4P In Action!

Watch a 4P Hardware Simulator show how to solve the Traveling Salesman Problem in 4P

Video Support Information

The Traveling Salesman Problem

For more information on the Traveling Salesman Problem click the button below.



Learn More about the TSP

TSP Implementation Technical Specification

In our current implementation shown in the video we require the input to be formatted as described.  First the wake bit consisting of a single 1 followed by a single zero.  Then 8 sets of 32 bits for all 8 cities corresponding to the integral distance from each city to all 8 cities including itself.  These distances are listed at the end of this writing to help the viewer examine the video.  Finally we require that the distances are selected such that the longest total summation does not overflow 31 bits.  Presently, the 32nd bit is unused and must always be zero to ensure proper timing.  Finally, as described in the video, the steinhaus johnson trotter algorithm for indexing the cities remains unimplemented due to budgetary constraints.  The basic indexing infrastructure is working and the algorithm is completely designed waiting for funding to complete implementation.  Here is the list of the randomly generated city distances as they are fed into the 4P TSP: 

[0][36343][60391][61240][6536][35746][78705][43284] 

[36343][0][94908][32971][40008][56778][48940][50166]

 [60391][94908][0][121576][59958][48261][139034][67522]

[61240][32971][121576][0][61978][88692][17465][83130] 

[6536][40008][59958][61978][0][40712][79367][49556] 

[35746][56778][48261][88692][40712][0][105451][19457] 

[78705][48940][139034][17465][79367][105451][0][98601] 

[43284][50166][67522][83130][49556][19457][98601][0]