Simon translated Travelling Salesperson Coding Challenge from JavaScript into Processing (Java)

Travelling Salesperson 3 May 2017

On Tuesday and Wednesday, Simon ventured upon a serious quest – he translated Daniel Shiffman’s multi-part Traveling Salesperson Coding Challenge from JavaScript into Processing (Java).

The travelling salesman problem (TSP) asks the following question: If you have a list of cities and you absolutely have to visit every city on the list exactly once, what is the shortest possible route you can take? It’s a classical problem on combinatorial optimization and is widely studied in theoretical computer science (where, given a length L, the task is to decide whether the graph has any tour shorter than L). The TSP has many applications in planning, manufacture of microchips, astronomy and even in DNA sequencing (where cities are DNA fragments).

Simon and I have read about this problem in a Dutch children’s book (Telduivel) where it was stated that if a salesperson has to visit 25 cities and thus there are 25! possible routes to take, no modern computer can handle calculating the shortest one. Simon decided to check what the maximum number of characters was for a long in Java, and it turned out to be 19 (while 25! equals to 15.511.210.043.330.985.984.000.000 and exceeds that maximum). In his TSP example, Daniel Shiffman uses only 10 cities and 10! equals to merely 3.628.800, so that worked out fine.

Wikipedia says that even though the problem is computationally difficult, a large number of algorithms are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%.[1]

Simon noticed that even with his modest number of 10 cities, Processing (Java) ran faster than p5.js (JavaScript).

In the first two videos he starts and explains the project, in the later videos he applies additional algorithms to enhance accuracy.

 

Lexicographic Order Algorithm, one algorithm to iterate over all the permutations of an array:

 

Genetic Algorithm:

 

 

In the following video, Simon explains what crossover is and how he plans to implement it within the Genetic Algorithm file in order to get even more exact results. (He later got stuck when introducing crossover into his Processing code).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s