Thursday, April 3, 2014
I'm taking CS 3102 this semester and I teamed up with friend to create a Traveling-Salesperson Art solver for our term project. You can check out the code here: https://github.com/mrranderson/TSP-Art
For those who don't know, the Traveling-Salesperson Problem (TSP) is an interesting problem in computer science: given a set of points, what is the shortest possible path that visits every point? Finding an exact solution to this problem is incredibly difficult because it typically requires testing every combination of points to find the shortest path.
We approached the problem by using a heuristic: start at a random point and then construct the path by going to the next closest point. Despite not being optimal, this works surprisingly well. After the initial path was created, we then parsed it again to remove intersections between edges. The image at the top of this post is the result of running our code on the following image of Gandhi:
We're quite happy with the result of our work and we have posted it all to Github. The program is written in Java and structured to be easily importable into Eclipse. Try downloading the code and giving it a whirl!