The Travelling Salesman Portrait

I have noticed even people who claim everything is predestined, and that we can do nothing to change it, look before they cross the road (Stephen Hawking)

Imagine a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge is finding the route which minimizes the total length of the trip. This is the Travelling Salesman Problem (TSP): one of the most profoundly studied questions in computational mathematics. Since you can find a huge amount of articles about the TSP in the Internet, I will not give more details about it here.

In this experiment I apply an heuristic algorithm to solve the TSP to draw a portrait. The idea is pretty simple:

  • Load a photo
  • Convert it to black and white
  • Choose a sample of black points
  • Solve the TSP to calculate a route among the points
  • Plot the route

The result is a single line drawing of the image that you loaded. To solve the TSP I used the arbitrary insertion heuristic algorithm (Rosenkrantz et al. 1977), which is quite efficient.

To illustrate the idea, I have used again this image of Frankenstein (I used it before in this other experiment). This is the result:

You can find the code here.

9 thoughts on “The Travelling Salesman Portrait

  1. I follow your R-bloggers post. Love it.
    Today you wrote “A simple definition of laminar flow is when a fluid flows through a pipe in parallel layers with no disruptions between these layers” Look at wikipedia Kármán vortex street for an example of laminar flow. Laminar flow is not turbulent flow where turbulent flow is chaotic.

  2. Hi Antonio,

    Thank you for sharing your code.

    I was trying to reproduce your plot but am having some issue with the code. I think its when you use row_number() it gives me an error.

    data.frame(id=solution) %>%
    mutate(order=row_number()) -> order

    so i updated your code to

    data.frame(id=solution) %>%
    dplyr::mutate(order=row_number()) -> order

    and am able to generate the plot but my plot looks like a lot of lines and no where close to frakenstein. Any idea what could be the issue. Thanks.

    Regards,
    Atmajit

  3. Hi,

    I have the following error message:

    data.frame(id=solution) %>%
    + mutate(order=row_number()) -> order
    Error in rank(x, ties.method = “first”, na.last = “keep”) :
    argument “x” is missing, with no default

    any idea of whats wrong?

    Best regards and many thanks for your code

  4. Cool! But I think this post is a trap to get nerds to say “Frankenstein is the name of the scientist, not the monster”, and I won’t be falling for that.

Leave a Reply

Your email address will not be published. Required fields are marked *