I’ve added a new interesting command tsp
to the G’MIC stdlib today, allowing to compute “acceptable” solutions to the wellknown 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
How does this work ? Basically, you provide a set of N unordered kdimensional points (as an image Nx1x1xk
), and the command tsp
reorder 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” suboptimal solution is computed instead).
The algorithm is a combination of a greedy nearest neighbor search, followed by 2opt. 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 antialiased
Here is the result I get, invoking then $ gmic test_tsp2d
:
Looks good ?
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:

If I consider a set of 3D points (quantized colors in the RGB cube), rather than 2D points:
What do you think ? Do you have cool idea for using it ?