Travelling Salesman Problem

Software G'MIC
1

I’ve added a new interesting command tsp to the G’MIC stdlib today, allowing to compute “acceptable” solutions to the well-known Travelling Salesman Problem. This command should be available after an update (so $ gmic update is your friend!).
I’m just starting to have some fun with it, so I’m happy to share :slight_smile:

How does this work ? Basically, you provide a set of N unordered k-dimensional points (as an image Nx1x1xk), and the command tsp re-order the points so that the path passing from these ordered points is tried to be minimal (as you may know, this is extremely hard to get the optimal, so a “reasonnable” sub-optimal solution is computed instead).
The algorithm is a combination of a greedy nearest neighbor search, followed by 2-opt. This has the advantage of being relatively fast to compute, does not require complex data structure for the implementation, and works for all dimensions.

So, here we go !
Doing it in 2D, is simple as:

test_tsp2d : 
   64,1,1,2 rand. 0,1023 round.  # Create a set of 2d points in range [0,1023]^2
   tsp. 200                       # Order them according to shortest possible path

   # Now we have a solution, let display it !
   1024,1024,1,3   # Create canvas where we will draw stuffs

   repeat {0,w}    # Loop over all points.
     circle. {0,I[$>]},15,0.5,255,0,255 # Each point as a purple filled circle
   done

   repeat {0,w}    # Draw the segments
     line. {0,boundary=2;[I[$>],I[$>+1]]},1,255,255,255 # Each segment as a white line
   done

  r2dx 75%  # Make the rendering a bit smaller and anti-aliased

Here is the result I get, invoking then $ gmic test_tsp2d :

tsp_test_000001
tsp_test_000001768×768 17 KB

Looks good ? :smiley:

Playing with this command is fun. Here are some examples I’ve generated in a few minutes of coding:

  • If I choose the points to be located on the edges of a picture:

    tsp_lena
    tsp_lena768×768 464 KB

  • If I consider a set of 3D points (quantized colors in the RGB cube), rather than 2D points:
    tsp3d

What do you think ? Do you have cool idea for using it ?

6 Likes
3

I love the graphics. Excellent!

The algorithm (with variations) is useful for more than cool graphics, or despatching itinerant vendors. It is also used when joining images at the least-visible cut line between them (“minimum error boundary cut”), and seam-carving (aka “liquid rescaling”), and tiling images invisibly, and other purposes.

In the traditional “travelling salesman” form, each trip between two towns on a route has a cost (eg time or distance), and the goal is to find the route that passes through all the towns with the minimum total cost.

A related problem is to find the minimum-cost route between any two specified towns (eg Toronto and Mexico City), or between any two towns in specified sets (eg any town in Canada and any town in Mexico).

And that problem can be reframed as: given an image of known lightness at each pixel, find the path between any two specified pixels (or pixels in specified sets) that has the total darkest path.

See Dark paths.

1 Like
4

I like traveling salesman plots. Cool that you are adding this one to G’MIC. Have used TSP program for several years to create TS plots for renters. If you ever port to the GIMP plugin, please give us a heads up. :slight_smile: